Sudoku Solver

Leave a comment

December 17, 2016 by oneOokay

典型的DFS。boolean solve(char[][] board):DFS recursive的函数返回可以是void,TreeNode和boolean 了。(还有之后的List和ArrayList)

public void solveSudoku(char[][] board) {
    solve(board);
}    
private boolean solve(char[][] board){ //recursive method        
    for (int i = 0; i < board.length; i ++){
//注意这里是board.length,而不一定是9.因为有简单的数独可能是3X3
        for (int j = 0; j < board[0].length; j ++){
           if (board[i][j] == '.') {//如果遇上'.',则对当前值开始替换
              for (char c = '1'; c <= '9'; c ++){
                 if (isValid(board, i, j, c)){
//先判定是否valid,这里的board还没有替换c.这里有效的减少了dfs
                     board[i][j] = c;//是一个valid board之后再找下一个空来填。
                     if(solve(board)) 
//这里应该是DFS走到最后一步填完了最后一个值。
此时如果为true的话就找到了解;如果为false的话,
那么说明前面有某个地方填错了,要换一个数填
                            return true;
                      else
                            board[i][j] = '.';
//这里把现在这个地方还原,回溯到上一层
                   }//end of if
               }//end of for
           return false; //对于当前的一个'.'试过了所有的值之后都没有得到
一个可行的解,也就说明前面填错了,开始回溯
            }
        }
        }
        return true;//这里是所有的值都填满了,不存在'.'了,所以是一个valid数独,
返回true
    }
    //在board的x,y上放入c,那么在此位置上的行和列和matrix block是否valid
private boolean isValid(char[][] board, int x, int y, char c){
    for (int i = 0; i < 9; i ++){
        if (board[x][i] !='.' && board[x][i] == c) return false;//行
        if (board[i][y] != '.' && board[i][y] == c) return false;//列
                
        if (board[3 * (x / 3) + i / 3][3 * (y / 3) + i % 3] != '.' 
&& board[3 * (x / 3) + i / 3][3 * (y / 3) + i % 3] == c) //注意这里不是'c'
           return false;
     }
     return true;
}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: