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