LeetCode | Sudoku Solver

本文主要是介绍LeetCode | Sudoku Solver，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

数独问题，暴力深搜。
注意在找到解之后，要及时return，以及在第某一行无解的时候，要及时return，这样剪枝才不会导致超时。

class Solution {
public:int steps=0;void solveSudoku(vector<vector<char>>& board) {int m=board.size();if(m==0) return;int n=board[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]=='.') steps++;}}solveSudoku(0,board);}bool valid(vector<vector<char>>& board,int x,int y){for(int i=0;i<9;i++){if(i!=y && board[x][y]==board[x][i]) return false;}for(int i=0;i<9;i++){if(i!=x && board[x][y]==board[i][y]) return false;}for(int i=0;i<9;i++){if(i!=y && board[x][y]==board[x][i]) return false;}for(int i=3*(x/3);i<3*(x/3+1);i++){for(int j=3*(y/3);j<3*(y/3+1);j++){if((i!=x && j!=y) &&board[i][j]==board[x][y]){return false;}}}return true;}bool solveSudoku(int step,vector<vector<char>>& board){if(step==steps){return true;}//从第一行第一列开始，寻找为.的点for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(board[i][j]=='.'){//尝试1~9所有的数并看看有无冲突for(int k=1;k<=9;k++){board[i][j]=k+'0';if(valid(board,i,j) && solveSudoku(step+1,board))//及时退出return true;board[i][j]='.';}//及时退出return false;}}}return true;}
};

这篇关于LeetCode | Sudoku Solver的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---