LeetCode第37之Sudoku Solver

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

主要思路：回溯法，每个‘.’的位置遍历“1-9”，如果满足则继续下一个位置，如果遍历完“1-9”仍不满足则将该位置改为‘.’,然后回溯到上一个位置。
缺点就是运行时间有点长。
C++代码：

#include <iostream>
#include <vector>
using namespace std;//打印board矩阵
void print_vec(vector<vector<char>> &board)
{for (vector<vector<char>>::iterator ita=board.begin();ita!=board.end();++ita){for (vector<char>::iterator itb=ita->begin();itb!=ita->end();++itb){cout<<*itb;}cout<<endl;}cout<<endl;
}class Solution {
private://falg指示是否找到解bool falg;
public://检查如果（i, j）的位置放数字n，第i行、第j列，以及（i,j）所在的块是否产生冲突bool isValid(vector<vector<char>> &board, int i, int j, int n){vector<bool> appear;//检查第i行是否满足appear.assign(9, false);//appear[n-1] = true;for (int k=0;k<9;++k){if (board[i][k] != '.'){int num = board[i][k]-'0';if (appear[num-1])return false;appear[num-1] = true;}}//检查第j列是否满足appear.assign(9, false);//appear[n-1] = true;for (int k=0;k<9;++k){if (board[k][j] != '.'){int num = board[k][j]-'0';if (appear[num-1])return false;appear[num-1] = true;}}//检查（i, j）所在的块是否满足appear.assign(9, false);int x = i-i%3;int y = j-j%3;for (int m=x;m<x+3;++m){for (int n=y;n<y+3;++n){if (board[m][n] != '.'){int num = board[m][n]-'0';if (appear[num-1])return false;appear[num-1] = true;}}}return true;}//给(i，j)的位置赋值void fun_try(vector<vector<char>> &board, int i, int j){//  print_vec(board);if (board[i][j] == '.'){for (int n=1;n<10;++n){board[i][j] = n+'0';if (isValid(board, i, j, n)){if (i == board.size()-1 && j == board.size()-1){//              print_vec(board);//答案已经找到falg =true;return;}if (j == board.size()-1){fun_try(board, i+1, 0);}else{//          print_vec(board);fun_try(board, i, j+1);}//如果答案已经找到则返回if (falg){return;}}}//回溯board[i][j] = '.';}else{if (isValid(board, i, j, board[i][j]-'0')){if (i == board.size()-1 && j == board.size()-1){//      print_vec(board);//答案已经找到falg =true;return;}if (j == board.size()-1){fun_try(board, i+1, 0);}else{fun_try(board, i, j+1);}//如果答案已经找到则返回if (falg){return;}}}}void solveSudoku(vector<vector<char>>& board) {falg = false;fun_try(board, 0, 0);}
};int main()
{Solution s;vector<vector<char>> board;vector<char> board0;board0.assign(9,'.');board0[0]='5';board0[1]='3';board0[4]='7';board.push_back(board0);board0.assign(9,'.');board0[0]='6';board0[3]='1';board0[4]='9';board0[5]='5';board.push_back(board0);board0.assign(9,'.');board0[1]='9';board0[2]='8';board0[7]='6';board.push_back(board0);board0.assign(9,'.');board0[0]='8';board0[4]='6';board0[8]='3';board.push_back(board0);board0.assign(9,'.');board0[0]='4';board0[3]='8';board0[5]='3';board0[8]='1';board.push_back(board0);board0.assign(9,'.');board0[0]='7';board0[4]='2';board0[8]='6';board.push_back(board0);board0.assign(9,'.');board0[1]='6';board0[6]='2';board0[7]='8';board.push_back(board0);board0.assign(9,'.');board0[3]='4';board0[4]='1';board0[5]='9';board0[8]='5';board.push_back(board0);board0.assign(9,'.');board0[4]='8';board0[7]='7';board0[8]='9';board.push_back(board0);print_vec(board);s.solveSudoku(board);print_vec(board);return 0;
}

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

---