Sudoku Solver

lc 37

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.

http://www.cnblogs.com/yuzhangcmu/p/4067733.html

Backtracking algorithms are adapted to solve the Sudoku that iterates all the possible solutions for the given sudoku. If the solutions assigned do not lead to the solution of Sudoku, the algorithm discards the solutions and rollbacks to the original solutions and retries again and hence the name backtrackin

典型DFS/递归/回溯/深搜题。对于DFS，说白了

1） 什么时候返回？在本题中，

1.当x>8或y>8 表示已经遍历完所有的格子，因此成功完成，返回true。

2.当下一个搜索（子搜索）返回true，说明已经找到，返回true。

3.如果测试过本轮的所有可能解，但无一是对的，说明无解，返回false。

4.如果当前空格不是空格，则改变x，y坐标后，继续下一个空格的尝试

2）DFS就是针对本轮的所有可能解进行逐一尝试，找到本轮的一个可能解后，这时要调用递归，基于本轮的解对下一轮（子问题）进行求解。如果下一轮（子问题）求解成功，则说明大功告成，及时返回true，停止之后的尝试。

否则如果下一轮（子问题）求解失败，则说明本轮的解不适合子问题，因此，必须换一个本轮的解，然后基于本轮的新解，继续尝试子问题。如果已经本轮所有的解都尝试过了，也都失败了，说明本问题无解，返回false。

当然在每次尝试子问题前和如果失败返回后，都要恢复原来的环境（撤销动作）。

所以，要想使DFS成功返回，条件就是找到满足本轮的解和这个解也要满足下一轮（子问题）。

另外：

1 每个backtracking的题目，最好都有独立判断isValid的程序，这样架构清楚。同时，valid判断函数在这里可以稍微研究一下。只要当前要判断的位置上的数值和本行没有重复，本列没有重复，九宫格没有重复就可以。一旦重复立即返回，减少判断次数。

2 backtracking的递归函数，怎么能没有返回值呢？因为要判断递归的方案正确与否，所以这里的递归一定是有返回值的（除非是combination那种没有正确错误概念的backtracking）

3 可以考虑“先放置，再判断”的方案。比如这里，首先判断当前位置是否为空，如果为空，那么放置一个元素，检查它是否正确。如果正确，就继续进行下面的递归（也就是第29行 isValid&&solveSudoku的作用）。当函数返回错误之后，将刚刚的数值变为空，再进行下一次尝试即可。

4 所有的方案（k从1到9）完毕之后，应该返回错误，这个是不应该被忽略的。

public class Solution {
    public void solveSudoku(char[][] board) {
        // 3:01
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }

        dfs(board, 0, 0);
    }

    public boolean dfs(char[][] board, int x, int y) {
        // 3:01
        // next row.
        if (y >= 9) {
            return dfs(board, x + 1, 0);
        }

        if (x >= 9) {
            return true;
        }

        // skip the number.
        if (board[x][y] != '.') {
            return dfs(board, x, y + 1);
        }

        // solve the current node.
        // BUG2: c start from 1 not 0.
        for (char c = '1'; c <= '9'; c++) {
            board[x][y] = c;
            if (isValid(board, x, y, c) && dfs(board, x, y + 1)) {
                return true;
            }
            board[x][y] = '.';
        }

        return false;
    }

    public boolean isValid(char[][] board, int x, int y, char c) {
        // the current row.        
        for (int i = 0; i < 9; i++) {
            if (y != i && c == board[x][i]) {
                return false;
            }
        }

        // the current col.        
        for (int i = 0; i < 9; i++) {
            // BUG1: should use board[i][y]
            if (x != i && c == board[i][y]) {
                return false;
            }
        }

        // the current block.
        int startX = x / 3 * 3;
        int startY = y / 3 * 3;
        for (int k = 0; k < 9; k++) {
            int indexX = startX + k / 3;
            int indexY = startY + k % 3;
            if (indexX == x && indexY == y) {
                continue;
            }

            if (board[indexX][indexY] == c) {
                return false;
            }
        }

        return true;
    }
}