Sudoku Solver -- LeetCode

這道題的方法就是用在N-Queens中介紹的常見套路。簡單地說思路就是循環處理子問題，對於每個格子，帶入不同的9個數，然後判合法，如果成立就遞歸繼續，結束後把數字設回空。大家可以看出代碼結構和N-Queens是完全一樣的。判合法可以用Valid Sudoku做為subroutine，但是其實在這裡因為每次進入時已經保證之前的board不會沖突，所以不需要判斷整個盤，只需要看當前加入的數字和之前是否沖突就可以，這樣可以大大提高運行效率，畢竟判合法在程序中被多次調用。實現的代碼如下：

public void solveSudoku(char[][] board) {
    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)
{
    boolean[] map = new boolean[9];
    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再強調一下哈，以上方法是一個非常典型的套路，大部分NP問題的都是可以這個方法，比如N-Queens，Combination
 Sum，Combinations等。