LeetCode: Sudoku Solver

思路分析

经典的数独求解问题，思路被我给想复杂了。实际上应该这么考虑：每放下一个数字，就要检查当前的放置是否有效（写一个check函数），如果可以，就继续向下一个位置搜索；如果不行，则递归回溯，尝试放下一个数字。每次虽然都是要尝试全部9个数字，但是实际上出现剪枝的情况会非常多。而且也可以人肉做一个剪枝，即保存所有有效的放置方式来作为搜索对象。

代码

#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)

class Solution {
public:
    bool solveSudoku( vector<vector<char> > &board)
    {
        rep(i, 9)
        rep(j, 9) if ( board[i][j] == '.' ) {
            REP(k, 1, 10) {
                board[i][j] = '0' + k;
                if ( isValidSudoku(board, i, j) && solveSudoku(board) ) {
                    return true;
                }
                board[i][j] = '.';
            }
            return false;
        }

        return true;
    }
    bool isValidSudoku(vector<vector<char> > &board, int x, int y) {
        rep(row, 9) if ( row != x && board[row][y] == board[x][y] ) return false;
        rep(col, 9) if ( col != y && board[x][col] == board[x][y] ) return false;
        int start_row = (x / 3) * 3;
        int start_col = (y / 3) * 3;
        REP(row, start_row, start_row + 3)
        REP(col, start_col, start_col + 3) if ( row != x && col != y && board[row][col] == board[x][y] ) return false;
        return true;
    }
};