本文主要是介绍[力扣题解]37. 解数独,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:37. 解数独
思路
回溯法
代码
class Solution {
public:bool function(vector<vector<char>>& board){int i, j;char k;for(i = 0; i < 9; i++){for(j = 0; j < 9; j++){// 为空if(board[i][j] == '.'){for(k = '1'; k <= '9'; k++){if(right(board, i, j, k)){board[i][j] = k;if(function(board)){return true;}board[i][j] = '.';}}return false;}}}// 都填满了return true;}// 检验合法性bool right(vector<vector<char>>& board, int row, int col, char num){cout << "right start" << endl;int i, j;int start_i, start_j;// 行for(j = 0; j < 9; j++){if(j != col && board[row][j] == num){return false;}}// 列for(i = 0; i < 9; i++){if(i != row && board[i][col] == num){return false;}}// 九宫格start_i = (row / 3) * 3;start_j = (col / 3) * 3;for(i = start_i; i < start_i+3; i++){for(j = start_j; j < start_j+3; j++){if(!(i == row && j == col) && board[i][j] == num){return false;}}}return true;}void solveSudoku(vector<vector<char>>& board) {function(board);}
};
这里的回溯函数设计的很有趣,返回值为bool
,所以没有特地写回溯结束的逻辑;
确定当前元素所在九宫格的位置时,用
start_i = (row / 3) * 3;
start_j = (col / 3) * 3;
来表示九宫格的起点坐标;
function()什么时候return
- 对于一个为空的格子,
9
个数字都试完还不对,就return false
; - 如果所有格子都填满了,并且没有检查出错误,就
return true
; - 发现当这个格子填好之后,整个棋盘也填好了,就
return true
;
这篇关于[力扣题解]37. 解数独的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!