Sudoku Solver
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.
A sudoku puzzle...
...and its solution numbers marked in red.
这题跟N-Queens是一个套路，回溯法尝试所有解。
需要注意的区别是：
本题找到解的处理是return true，因此返回值为bool
N-Queen找到解的处理是保存解，因此返回值为void
对于每个空位'.'，遍历1~9，check合理之后往下一个位置递归。
由于这里路径尝试本质上是有序的，即1~9逐个尝试，因此无需额外设置状态位记录已经尝试过的方向。
注意：只有正确达到最终81位置（即成功填充）的填充结果才可以返回，若不然，将会得到错误的填充。
因此辅助函数solve需要设为bool而不是void
class Solution { public: void solveSudoku(vector<vector<char> > &board) { solve(board, 0); } bool solve(vector<vector<char> > &board, int position) { if(position == 81) return true; int row = position / 9; int col = position % 9; if(board[row][col] == '.') { for(int i = 1; i <= 9; i ++) {//try each digit board[row][col] = i + '0'; if(check(board, position)) if(solve(board, position + 1)) //only return valid filling return true; board[row][col] = '.'; } } else { if(solve(board, position + 1)) //only return valid filling return true; } return false; } bool check(vector<vector<char> > &board, int position) { int row = position / 9; int col = position % 9; int gid; if(row >= 0 && row <= 2) { if(col >= 0 && col <= 2) gid = 0; else if(col >= 3 && col <= 5) gid = 1; else gid = 2; } else if(row >= 3 && row <= 5) { if(col >= 0 && col <= 2) gid = 3; else if(col >= 3 && col <= 5) gid = 4; else gid = 5; } else { if(col >= 0 && col <= 2) gid = 6; else if(col >= 3 && col <= 5) gid = 7; else gid = 8; } //check row, col, subgrid for(int i = 0; i < 9; i ++) { //check row if(i != col && board[row][i] == board[row][col]) return false; //check col if(i != row && board[i][col] == board[row][col]) return false; //check subgrid int r = gid/3*3+i/3; int c = gid%3*3+i%3; if((r != row || c != col) && board[r][c] == board[row][col]) return false; } return true; } };
check的另一种实现方式如下：
bool check(vector<vector<char> > &board, int pos) { int v = pos/9; int h = pos%9; char target = board[v][h]; //row for(vector<char>::size_type st = 0; st < 9; st ++) { if(st != h) { if(target == board[v][st]) return false; } } //col for(vector<char>::size_type st = 0; st < 9; st ++) { if(st != v) { if(target == board[st][h]) return false; } } //subgrid int beginx = v/3*3; int beginy = h/3*3; for(int i = beginx; i < beginx+3; i ++) { for(int j = beginy; j < beginy+3; j ++) { if(i != v && j != h) { if(target == board[i][j]) return false; } } } return true; }
