解数独分析

无情 阅读:135 2020-10-22 16:40:11 评论:0

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

 

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

解:还是用回溯法,代码量看着有点多,其实挺简单

class Solution { 
public: 
    void solveSudoku(vector<vector<char>>& board) { 
        //每一行里1-9使用的数字 
        vector<vector<bool>> vec_row_b(9,vector<bool>(10,false)); 
        //每一列 
        vector<vector<bool>> vec_col_b(9,vector<bool>(10,false));
//这里可以优化下,二维数组就够了,int b = (i / 3 ) * 3 + j / 3; box[b][n] vector
<vector<vector<bool>>> vec_box_b(3,vector<vector<bool>>(3,vector<bool>(10,false))); for(int i_row=0;i_row<board.size();i_row++) { for(int j_col=0;j_col<board[0].size();j_col++) { if(board[i_row][j_col]-'0'>=1&&board[i_row][j_col]-'0'<=9) { int num=board[i_row][j_col]-'0'; vec_row_b[i_row][num]=true; vec_col_b[j_col][num]=true; vec_box_b[i_row/3][j_col/3][num]=true; } } } RecuSolveSudu(board,vec_row_b,vec_col_b,vec_box_b,0,0); } bool RecuSolveSudu(vector<vector<char>>&board,vector<vector<bool>>vec_row,vector<vector<bool>> vec_col,vector<vector<vector<bool>>>vecc_box,int row,int col) { //一行的校验结束 if(board[0].size()==col) { col=0; row++; //所有的校验结束 if(row==board.size()) { return true; } } //空白的循环才有意义 if(board[row][col]=='.') { //遍历这一行一列未使用的数 for(int i=1;i<=9;i++) { bool can_used=!(vec_row[row][i]||vec_col[col][i]||vecc_box[row/3][col/3][i]); if(can_used) { board[row][col]='0'+i; vec_row[row][i]=true; vec_col[col][i]=true; vecc_box[row/3][col/3][i]=true; if(RecuSolveSudu(board,vec_row,vec_col,vecc_box,row,col+1)) { //返回true了 就说明找到答案了 ,立刻返回 return true; } //否则回溯回来 继续尝试 board[row][col]='.'; vec_row[row][i]=false; vec_col[col][i]=false; vecc_box[row/3][col/3][i]=false; } } } else { return RecuSolveSudu(board,vec_row,vec_col,vecc_box,row,col+1); } return false; } };

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

扫一扫关注我们,了解最新精彩内容