Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character
'.'
.You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
A:就是简单的回溯啊~~~~~~~~~ 你那样用手做的方法,很可能做不出来的。public class Solution { public void solveSudoku(char[][] board) { recursiveSolveSudoku(board); } private boolean recursiveSolveSudoku(char[][] board) { // recursive Solve Sudoku for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') { for (int k = 0; k < 9; k++) { board[i][j] = (char) ('1' + k); if (isValid(board, i, j) && recursiveSolveSudoku(board)) return true; board[i][j] = '.';// put the '.' back } return false;// !!!!!!!!!! cannot fill any char here } } } return true; } private boolean isValid(char[][] board, int row, int col) { // check if soduku is still valid after setting the value at (row,col) // position Set<Character> contained = new HashSet<Character>(); char ch; // check the line of (row,col) for (int j = 0; j < 9; j++) { ch = board[row][j]; if (contained.contains(ch)) return false; if (ch > '0' && ch <= '9') contained.add(ch); } // check the column of {row,col} contained = new HashSet<Character>(); for (int i = 0; i < 9; i++) { ch = board[i][col]; if (contained.contains(ch)) return false; if (ch > '0' && ch <= '9') contained.add(ch); } // check the small 3-by-3 square of {row,col} contained = new HashSet<Character>(); int outerI = row / 3; int outerJ = col / 3; for (int i = outerI * 3; i < outerI * 3 + 3; i++) { for (int j = outerJ * 3; j < outerJ * 3+3; j++) { ch = board[i][j]; if (contained.contains(ch)) return false; if (ch > '0' && ch <= '9') contained.add(ch); } } return true; } }
Mistakes:
1: 刚开始,就是用的手算的思路。但是,不用回溯,是不行的。 哎~~~~~~~~~~
2:ArrayList 调用remove方法时, 当我们想remove Object时,但是, 我们的object是Integer。这时候,我们就不能直接remove Integer, 需要先找到其的index,再remove
3: 同样的回溯, 你写的就是太慢, 别人写的,就快啊
原本,我们这样写
boolean[] findFlag = new boolean[10];
// check the line of (row,col)
for (int j = 0; j < 9; j++) {
char ch = board[row][j];
if (ch == '.')
continue;
int value = Integer.valueOf("" + ch);
if (findFlag[value]) {
return false;
} else {
findFlag[value] = true;
}
}
对手是用了HashSet --------------应该,我们以前的也没问题的。 代码里,少写了个+3
Learned:
1: Cannot create a generic array of ArrayList<Integer> 所以说,下面这句是不对的
ArrayList<Integer>[][] candidites = new ArrayList<Integer>[9][9];
2 -------------------下面是别人的东东----------------
做了这道题,对backtracking的理解又加深了一点点。
1 每个backtracking的题目,最好都有独立判断isValid的程序,这样架构清楚。同时,valid判断函数在这里可以稍微研究一下。只要当前要判断的位置上的数值和本行没有重复,本列没有重复,九宫格没有重复就可以。一旦重复立即返回,减少判断次数。
2 backtracking的递归函数,怎么能没有返回值呢?!因为要判断递归的方案正确与否,所以这里的递归一定是有返回值的(除非是combination那种没有正确错误概念的backtracking)!3 可以考虑“先放置,再判断”的方案。比如这里,首先判断当前位置是否为空,如果为空,那么放置一个元素,检查它是否正确。如果正确,就继续进行下面的递归 (也就是第29行 isValid&&solveSudoku的作用)。当函数返回错误之后,将刚刚的数值变为空,再进行下一次尝试即可。
4 所有的方案(k从1到9)完毕之后,应该返回错误,这个是不应该被忽略的。
5 最后一点需要注意的是,当i,j循环完毕之后,第36行应该返回true。这里实际上是最终/最底层的一次循环,表明已经解出了sudoku,返回true!切记切记,最终情况!
--------------------------------第二遍---------思路完全一样, 代码略有精简, 没有用Set, 仅仅就是比较 ch 的值。---------------
public class Solution { public void solveSudoku(char[][] board) { helper(board); } private boolean helper(char[][] board){ for(int i =0;i< 9;i++){ for(int j = 0;j<9; j++){ if(board[i][j] == '.'){ for(char ch = '1';ch<='9';ch++){ board[i][j] = ch; if(isValid(ch,i,j,board) && helper(board)) return true; board[i][j] = '.'; } return false; // cannot fill any char here } } } return true; } private boolean isValid(char ch, int row, int col, char[][] board){ // check that after inserting ch at position i,j, the board is still valid // check row for(int j = 0;j<9;j++){ if(j != col) if(board[row][j] == ch) return false; } // check column for(int i = 0; i<9; i++) if(i != row) if(board[i][col] == ch) return false; // check small square int i = row/3, j = col /3; board[row][col] = '.'; for(int ii = i*3;ii<i*3+3;ii++){ for(int jj = j*3;jj<j*3+3;jj++){ if(board[ii][jj] == ch){ return false; } } } board[row][col] = ch; return true; } }
-------------------------------第三遍--------------------
为了节省时间,试着用List of Set to check the possible directly, but no much speed improvement.
public class Solution { List<Set<Character>> row = new LinkedList(); List<Set<Character>> col = new LinkedList(); List<Set<Character>> subBox = new LinkedList(); public void solveSudoku(char[][] board) {// we know that board is 9-by-9 array // initialize the list of Sets for(int i =0;i<9;i++){ HashSet tmpRow = new HashSet<Character>(); for(int j =0;j<9;j++) tmpRow.add(board[i][j]); row.add(tmpRow); HashSet tmpCol = new HashSet<Character>(); for(int j =0;j<9;j++) tmpCol.add(board[j][i]); col.add(tmpCol); HashSet tmpBox = new HashSet<Character>(); subBox.add(tmpBox); } for(int i =0;i<9;i++) for(int j =0;j<9;j++) subBox.get(j / 3 + (i / 3) * 3).add(board[i][j]); helper(board); } private boolean helper(char[][] board){ for(int i =0;i<9;i++){ for(int j =0;j<9;j++){ if(board[i][j] !='.') continue; for(char ch = '1';ch<='9';ch++){ if(isValid(i,j,ch)){ board[i][j] = ch; // update list of Set row.get(i).add(ch); col.get(j).add(ch); subBox.get(j/3+(i/3)*3).add(ch); // DFS if(helper(board)) return true; board[i][j] = '.'; // clear the newly added value row.get(i).remove(ch); col.get(j).remove(ch); subBox.get(j/3+(i/3)*3).remove(ch); } } return false; } } return true; } private boolean isValid(int i, int j, char ch){ return !row.get(i).contains(ch) && !col.get(j).contains(ch) && !subBox.get(j/3+(i/3)*3).contains(ch); } }
Mistakes:
2: 在试完了所有的9种可能填的选项之后,应该直接返回false了,而不是等待其最后返回true.
No comments:
Post a Comment