LeetCode 37 解数独

题目描述

编写一个程序，通过填充空格来解决数独问题。一个数独的解法需遵循如下规则：数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

题解

深度优先搜索

代码

class Solution { public:bool dfs(vector<vector<char>>& board,int index,int n,vector<vector<bool>>& row,vector<vector<bool>>& col,vector<vector<bool>>& squ,vector<pair<int,int>>& vec){if (index>=vec.size()) return true;int i=vec[index].first;int j=vec[index].second;for (int k=1;k<=n;k++){if (!row[i][k]&&!col[k][j]&&!squ[((i-1)/3)*3+(j-1)/3+1][k]){row[i][k]=true;col[k][j]=true;squ[((i-1)/3)*3+(j-1)/3+1][k]=true;board[i-1][j-1]=k+'0';if (dfs(board,index+1,n,row,col,squ,vec)) return true;board[i-1][j-1]='.';row[i][k]=false;col[k][j]=false;squ[((i-1)/3)*3+(j-1)/3+1][k]=false;}}return false;}void solveSudoku(vector<vector<char>>& board) {int n=board.size();if (n!=9) return ;vector<vector<bool>> row(n+1,vector<bool>(n+1)),col(n+1,vector<bool>(n+1)),squ(n+1,vector<bool>(n+1));vector<pair<int,int>> vec;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (board[i-1][j-1]!='.'){row[i][board[i-1][j-1]-'0']=true; // i行中已经有该数了col[board[i-1][j-1]-'0'][j]=true; // j列中已经有该数了squ[((i-1)/3)*3+(j-1)/3+1][board[i-1][j-1]-'0']=true; // 3*3宫内已经有该数了}else{vec.push_back({i,j});}}}dfs(board,0,n,row,col,squ,vec);} };

总结

以上是生活随笔为你收集整理的LeetCode 37 解数独的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。