题目描述
编写一个程序,通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
Note:
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
思路
开始觉得是个很难的题,看了答主:代码随想录 的回答后,觉得思路简单清洗,代码也很容易理解,遂记录一下。
采用“回溯+递归”的方法,其中
1. 回溯:从第一个空格(‘.’)开始,选择一个复合规则的数字填入,再处理下一个空格,当填到某一个空格后无法继续进行时,则回溯到上一个步骤,更改上一个空格填的数字后再继续处理下一个空格。
2. 递归:当填了第一个空格后,剩下的待填写空格处理方式和第一个空格相同,因此继续调用该函数处理。
细节处理:
1. 判断填入的数字是否符合规则。
2. 递归函数的出口处理
代码
class Solution { public: void solveSudoku(vector<vector<char>>& board) { backTracking(board); } private: bool backTracking(vector<vector<char>>& board){ for(int i = 0; i < board.size(); i++){ //每一行 for(int j = 0; j < board[0].size(); j++){ //每一列 if(board[i][j] != '.') continue; for(char c = '1'; c <= '9'; c++){ //分别取数字1-9 if(isInplace(i, j, c, board)){ //判断填入改数字是否符合规则 board[i][j] = c; //符合规则,则修改该空格 if(backTracking(board)) //递归,处理修改后的新的数独问题 return true; board[i][j] = '.'; //当无法继续,则回溯,修改会空格 } } return false; } } return true; } //判断填入的数字是否符合规则 bool isInplace(int row, int col, char c, vector<vector<char>>& board){ for(int i = 0; i < 9; i++) if(board[row][i] == c) return false; for(int i = 0; i < 9; i++) if(board[i][col] == c) return false; int row3 = (row / 3) * 3; int col3 = (col / 3) * 3; for(int i = row3; i < row3 + 3; i++) for(int j = col3; j < col3 + 3; j++) if(board[i][j] == c) return false; return true; } };