Sudoku Solver解题报告

该题可以用回溯法求解，对当前位置（x, y），首先求出满足条件的数字作为候选C，对C中的每一个元素Ci， 令board[x][y] = Ci，进行到下一个位置（x’, y‘），判断是否满足，如果不满足，则令board[x][y]等于下一个候选，直到遍历完所有的候选值。步骤：

1、如果当前位置不为空，进行到下一个位置；否则，执行步骤2

2、分别求出当前位置（x, y）所在行、列和块中已经出现的数字，记为C，如此便可得知在当前位置可能会出现的值（即数字1~9中除了C中的值除外的那些值）

3、对C中的每一个值Ci

令board[x][y] = Ci;

行进到下一个位置，如果返回true，说明已找到正确的解，返回true;

否则，令board[x][y] = '.';

Code:

bool solveSudoku_(vector<vector<char>> &board, int x, int y){
		if (board[x][y] != '.'){
			if (y < 8)
				return solveSudoku_(board, x, y + 1);
			else if (x < 8)
				return solveSudoku_(board, x + 1, 0);
			else  return true;
		};
		vector<bool> digit(10, false);
		for (int i = 0; i < 9; ++i){
			if (board[x][i] != '.')
				digit[board[x][i] - '0'] = true;
			if (board[i][y] != '.')
				digit[board[i][y] - '0'] = true;
		}
		int blockX = x / 3;
		int blockY = y / 3;
		for (int i = 0; i < 3; ++i){
			for (int j = 0; j < 3; ++j){
				if (board[blockX * 3 + i][blockY * 3 + j] != '.')
					digit[board[blockX * 3 + i][blockY * 3 + j] - '0'] = true;
			}
		}
		for (int i = 1; i <= 9; ++i){
			if (!digit[i]){
				board[x][y] = i + '0';
				bool b = false;
				if (y < 8)	b = solveSudoku_(board, x, y + 1);
				else if (x < 8) b = solveSudoku_(board, x + 1, 0);
				else  return true;
				if (b)	return true;
				board[x][y] = '.';
			}
		}
		return false;
	}
	void solveSudoku(vector<vector<char> > &board) {
		solveSudoku_(board, 0, 0);
		for (int i = 0; i < board.size(); ++i){
			for (int j = 0; j < board[i].size(); ++j){
				cout << board[i][j] << " ";
			}
			cout << endl;
		}
	}