## Saturday, December 5, 2015

### LeetCode 37 - Sudoku Solver

http://blog.csdn.net/linhuanmars/article/details/20748761
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.

```public void solveSudoku(char[][] board) {
if(board == null || board.length != 9 || board[0].length !=9)
return;
helper(board,0,0);
}
private boolean helper(char[][] board, int i, int j)
{
if(j>=9)
return helper(board,i+1,0);
if(i==9)
{
return true;
}
if(board[i][j]=='.')
{
for(int k=1;k<=9;k++)
{
board[i][j] = (char)(k+'0');
if(isValid(board,i,j))
{
if(helper(board,i,j+1))
return true;
}
board[i][j] = '.';
}
}
else
{
return helper(board,i,j+1);
}
return false;
}
private boolean isValid(char[][] board, int i, int j)
{
for(int k=0;k<9;k++)
{
if(k!=j && board[i][k]==board[i][j])
return false;
}
for(int k=0;k<9;k++)
{
if(k!=i && board[k][j]==board[i][j])
return false;
}
for(int row = i/3*3; row<i/3*3+3; row++)
{
for(int col=j/3*3; col<j/3*3+3; col++)
{
if((row!=i || col!=j) && board[row][col]==board[i][j])
return false;
}
}
return true;
}```

Recursively fill the empty cell with available number that make the sudouku board valid, if all numbers were not valid in this cell, backtrack to last cell and iteratively try next number until all cells are filled with number.
This is a kind of standard solution for all recursion problem. 1.Find the base case or terminating case.Usually was written in the fist line of the recursion function(if(...) ...return) 2. Iteratively try valid one and go to next cell, if the current trial doesn't work, reset the current trial to original value and try next possibility.  So the code always looks like :
helper(...,i+1);
setValue(original)/removeItem(i);
`````` public void solveSudoku(char[][] board) {
if(board==null || board.length==0 || board[0].length==0) return;
boolean[][] row= new boolean[9][9];
boolean[][] col= new boolean[9][9];
boolean[][] block=new boolean[9][9];
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[i][j]<='9' && board[i][j]>='1'){
int num=board[i][j]-'1';
int bnum=(i/3)*3+j/3;
if(row[i][num] || col[j][num] || block[bnum][num]) return;
row[i][num] = col[j][num] = block[bnum][num] =true;
}
}
}
helper(board,0,row,col,block);
}
public boolean helper(char[][] board, int ind, boolean[][] row, boolean[][] col, boolean[][] block){
if(ind==81) return true;
int i=ind/9;
int j=ind%9;
int b=(i/3)*3+j/3;
if(board[i][j]=='.'){
for(int k=1;k<=9;k++){
if((!row[i][k-1]) && (!col[j][k-1]) && (!block[b][k-1])){
board[i][j]=(char)('0'+k);
row[i][k-1] =col[j][k-1] =block[b][k-1]=true;
if (helper(board,ind+1,row,col,block)) return true;
else {
row[i][k-1] =col[j][k-1] =block[b][k-1]=false;
board[i][j]='.';
}
}
}
return false;
}
else return helper(board,ind+1,row,col,block);
} ``````

X. Inefficient?
https://discuss.leetcode.com/topic/11327/straight-forward-java-solution-using-backtracking
Try 1 through 9 for each cell. The time complexity should be 9 ^ m (m represents the number of blanks to be filled in), since each blank can have 9 choices. Details see comments inside code. Let me know your suggestions.
``````    public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}

public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell

if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}

return false;
}
}
}
return true;
}

private boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}``````
http://blog.csdn.net/zdavb/article/details/48165059

http://www.jiuzhang.com/solutions/sudoku-solver/
http://www.cnblogs.com/springfor/p/3884252.html
```    public void solveSudoku(char[][] board){
solve(board);
}

public boolean solve(char[][] board) {
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++){
if(board[i][j] != '.'){
continue;
}
for(int k = 1; k <= 9; k++){
board[i][j] = (char) (k + '0'); // set value
if (isValid(board, i, j) && solve(board)){
return true;
}
board[i][j] = '.';// backtrack
}
return false;//\\
}
}
return true;//\\
}

public boolean isValid(char[][] board, int a, int b){
Set<Character> contained = new HashSet<Character>();
for(int j=0;j<9;j++){
if(contained.contains(board[a][j])) return false;
if(board[a][j]>'0' && board[a][j]<='9')
}

contained = new HashSet<Character>(); // or call set.clear()
for(int j=0;j<9;j++){
if (contained.contains(board[j][b])) {
return false;
}
if (board[j][b]>'0' && board[j][b]<='9') {
}
}

contained = new HashSet<Character>();
for (int m = 0; m < 3; m++) {
for (int n = 0; n < 3; n++){
int x = a / 3 * 3 + m, y = b / 3 * 3 + n;
if (contained.contains(board[x][y])) {
return false;
}
if (board[x][y] > '0' && board[x][y] <= '9') {
}
}
}

return true;
}```
http://cs-cjl.com/2016/09_29_leetcode_37_sudoku_solver
void solveSudoku(vector<vector<char>>& board) { dfs(board, 0); } bool dfs(vector<vector<char>>& board, const int pos) { if (pos == 81) { return true; } int x = pos / 9, y = pos % 9; if (board[x][y] != '.') { return dfs(board, pos + 1); } for (char i = '0'; i <= '9'; ++i) { board[x][y] = i; if (isValidSudoku(board) && dfs(board, pos + 1)) return true; } board[x][y] = '.'; return false; } bool isValidSudoku(vector<vector<char>>& board) { int col[9][9] = {0}, row[9][9] = {0}, rec[9][9] = {0}; for(int i = 0; i < 9; ++ i) { for(int j = 0; j < 9; ++ j) { if(board[i][j] != '.') { int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3; if(col[i][num] || row[j][num] || rec[k][num]) return false; col[i][num] = row[j][num] = rec[k][num] = 1; } } } return true; }

http://blog.csdn.net/u011095253/article/details/9158497
```    public boolean isValid(int v, int row, int col, char[][] board){
for(int i=0;i<9;i++){
if(board[row][i] - '0'==v) return false;
if(board[i][col] - '0'==v) return false;
int row_s = 3*(row/3) + i/3;
int col_s = 3*(col/3) + i%3;
if(board[row_s][col_s] - '0'==v) return false;
}
return true;
}```
http://huangyawu.com/leetcode-sudoku-solver-java/
`    ``private` `boolean` `isValid(``char``[][] board, ``int` `row, ``int` `col){`
`        ``for``(``int` `i=``0``; i<``9``; i++){`
`            ``if``(i!=row && board[i][col] == board[row][col]) ``return` `false``;`
`            ``if``(i!=col && board[row][i] == board[row][col]) ``return` `false``;`
`        ``}`
`        `
`        ``int` `r = row / ``3` `* ``3``;`
`        ``int` `c = col / ``3` `* ``3``;`
`        ``for``(``int` `i=``0``; i<``3``; i++)`
`            ``for``(``int` `j=``0``; j<``3``; j++){`
`                ``if``(r + i != row && c + j != col `
`                        ``&& board[r+i][c+j] == board[row][col])`
`                    ``return` `false``;`
`            ``}`
`        ``return` `true``;`
`    ``}`
https://leetcode.com/discuss/30482/straight-forward-java-solution-using-backtracking
Backtracking algorithms generally have exponential worst-case running time. However, the efficient pruning `isValid` makes it fast enough in practice :-)
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}
public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9 for each cell
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell

if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int i, int j, char c){
//Check colum
for(int row = 0; row < 9; row++)
if(board[row][j] == c)
return false;

//Check row
for(int col = 0; col < 9; col++)
if(board[i][col] == c)
return false;

//Check 3 x 3 block
for(int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
for(int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
if(board[row][col] == c)
return false;
return true;
}
https://leetcode.com/discuss/51308/two-very-simple-and-neat-java-dfs-backtracking-solutions
Dr. Donald Knuth’s Dancing Links Algorithm solves an Exact Cover situation. The Exact Cover problem can be extended to a variety of applications that need to fill constraints. Sudoku is one such special case of the Exact Cover problem.
NOTE:This is a very complicate solution.
http://huntfor.iteye.com/blog/2087778
DFS在找到一个结果的时候会继续回溯寻找下一个可能的结果，因此我又设置了一个全局变量来添加控制。这无疑让代码可读性变差
// only check condition(over) at first, no need check condition before every recursive call.

Determine whether a Sudoku has a unique solution
If you return a number instead of a boolean, you can destinguish between cases where there are 0, 1, or more than 1 solution(s).
To return all solutions: clone the matrix, and put it into list.