解数独问题可以只用一层for循环

[zeal-up]

解数独问题可以看成每次递归解决一个空格，也就是从1-9中选择一个输入填入当前空格，然后递归进去下一个空格。判断行列小正方格中是否出现也可以使用3个二维数组解决，避免使用for循环。代码如下：

// #37 解数独
class Solution {
private:
	vector<vector<int>> usedRowNum = vector<vector<int>>(9, vector<int>(9));
	vector<vector<int>> usedColNum = vector<vector<int>>(9, vector<int>(9));
	vector<vector<int>> usedQurNum = vector<vector<int>>(9, vector<int>(9));
	vector<vector<char>> result;
	bool solveSudoIter(vector<vector<char>>& board, int curRow, int curCol) {
		if (curRow == 9)
		{
			result = board;
			return true;
		}
		if (board[curRow][curCol] != '.') {
			return solveSudoIter(board, curRow + (curCol + 1) / 9, (curCol + 1) % 9);
		}
		for (int num = 0; num < 9; num++) {
			if (usedRowNum[curRow][num] == 1) continue;
			if (usedColNum[curCol][num] == 1) continue;
			int curQur = 3 * (curRow / 3) + curCol / 3;
			if (usedQurNum[curQur][num] == 1) continue;
			

			//push
			usedRowNum[curRow][num] = 1;
			usedColNum[curCol][num] = 1;
			usedQurNum[curQur][num] = 1;
			board[curRow][curCol] = '1' + num;

			// iter
			bool ifFound = solveSudoIter(board, curRow + (curCol + 1) / 9, (curCol + 1) % 9);
			if (ifFound) return true;

			//pop back
			usedRowNum[curRow][num] = 0;
			usedColNum[curCol][num] = 0;
			usedQurNum[curQur][num] = 0;
			board[curRow][curCol] = '.';
		}
		return false;
	}
public:
	void solveSudoku(vector<vector<char>>& board) {
		for (int row = 0; row < 9; row++) {
			for (int col = 0; col < 9; col++)
			{
				if (board[row][col] == '.') continue;
				int curNum = board[row][col] - '1';
				usedRowNum[row][curNum] = 1;
				usedColNum[col][curNum] = 1;
				int curQur = 3 * (row / 3) + col/3;
				usedQurNum[curQur][curNum] = 1;
			}
		}
		solveSudoIter(board, 0, 0);
	}
};