37. Sudoku Solver ----H. !!

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

 

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

 

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

A:

就是简单的回溯啊~~~~~~~~~ 你那样用手做的方法，很可能做不出来的。

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) { helper(board); }

private:
    bool helper(vector<vector<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(board, i, j) && helper(board))
                            return true;
                    }
                    board[i][j] = '.';
                    return false; // cannot set any valid value here
                }
            }
        }
        return true;
    }

    bool isValid(vector<vector<char>>& board, int row, int col) {
        char target = board[row][col];
        // check local 3*3
        int startRow = row / 3 * 3, startCol = col / 3 * 3;
        for(int i = startRow; i<startRow+3; i++){
            for(int j = startCol; j < startCol +3; j++){
                if(board[i][j] == target && !(i == row && j == col )){
                    return false;
                }
            }
        }
        // check row
        for(int j = 0; j<9; j++){
            if(j != col && board[row][j] == target)
                return false;
        }
        // check that coloum
        for(int i = 0; i<9; i++){
            if(i != row && board[i][col] == target)
                return false;
        }
        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！切记切记，最终情况！





Mistakes:
2:  在试完了所有的9种可能填的选项之后，应该直接返回false了，而不是等待其最后返回true.