Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'
.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
这题是解数独,这个嘛,我用的是递归写法,简单描述就是填写当前空格,递归下一格,遇到不行返回,不过逻辑写的不好,很多奇奇怪怪的细节的判断。
算法逻辑:
- 创建一个辅助函数,help(vector<vector<char> > & board,int i,int ii,int j,int jj),其中i为第几行,j 第几列,ii 小框中的第几行,jj 小框中第几列。
- help 函数4层for 循环遍历整个9*9 矩阵,说是4层,跟两次for 是一样的,i 和j 的步长是3,for(;i<9;i+=3),因为这4个变量的初始化在函数传入的时候,所以在其循环结束时候尾部赋0,其中一个不好的地方。
- 4层循环内部,首先判断当前格board[i+ii][j+jj]是否为数字,不然继续循环。
- 创建标记finish = false,标记接下来的填入(当前格为空)能否完成整个矩阵,用于控制跳出填写,和如果填写失败修复当前格为'.' 回溯。
- 遍历1-9 尝试填写,需要用到bool canIn=true,判断行,列,框中的情况,如果通过判断则修改当框为遍历的数字,递归下一格,输入当前格的i ii j jj,便可以,这是第二个不好的地方,判断没有写为外部函数,另外函数的参数设置导致了很多细节问题。
- 下层返回的值赋予 finish ,如果为false ,表示当前填写不行,继续遍历,如果为true,跳出填写的遍历。
- 结束遍历后判断是否已经填写整个矩阵,如果finish 为false,表示失败了,则当前格,然后返回false,成功先别返回。
- 外部4层循环结束返回true。
所以在外层循环后返回true,是假如例子上的情况,最后一个格不为空,那么按上面逻辑是不会进入内部的,而如果能够全部遍历完整个矩阵,那么表示没有在内部返回,等价于成功填写了。
之所以使用 ii jj,是为了可以方便处理3*3框,在能否填写的时候,需要注意跳过自身与自身判断,先判断行列,然后框的时候变可以跳过当前框所在的行列了。
1 #include2 #include 3 #include 4 using namespace std; 5 6 class Solution { 7 public: 8 void solveSudoku(vector > &board) { 9 help(board,0,0,0,0);10 }11 bool help(vector > & board,int i,int ii,int j,int jj){12 for(;i<9;i+=3){13 for(;ii<3;ii++){14 for(;j<9;j+=3){15 for(;jj<3;jj++){16 if(board[i+ii][j+jj]!='.') continue;17 bool finish = false;18 for(char c='1';c<='9'&&!finish;c++){19 bool canIn= true;20 for(int k=0;k<9&&canIn;k++){21 if(k!=i+ii&&board[k][j+jj]==c) canIn = false;22 if(k!=j+jj&&board[i+ii][k]==c) canIn = false;23 }24 for(int ti=0;ti<3&&canIn;ti++){25 if(ti == ii) continue;26 for(int tj=0;tj<3&&canIn;tj++){27 if(tj==jj) continue;28 if(board[ti+i][tj+j]==c) canIn = false;29 }30 }31 if(canIn==false) continue;32 board[i+ii][j+jj] = c;33 finish = help(board,i,ii,j,jj);34 }35 if(!finish){ board[i+ii][j+jj] = '.'; return false; }36 }37 jj = 0;38 }39 j=0;40 }41 ii=0;42 }43 return true;44 }45 };46 47 int main()48 {49 vector line;50 vector > board;51 line = { '5','3','.','.','7','.','.','.','.'};52 board.push_back(line);53 line.clear();54 line = { '6','.','.','1','9','5','.','.','.'};55 board.push_back(line);56 line.clear();57 line = { '.','9','8','.','.','.','.','6','.'};58 board.push_back(line);59 line.clear();60 line = { '8','.','.','.','6','.','.','.','3'};61 board.push_back(line);62 line.clear();63 line = { '4','.','.','8','.','3','.','.','1'};64 board.push_back(line);65 line.clear();66 line = { '7','.','.','.','2','.','.','.','6'};67 board.push_back(line);68 line.clear();69 line = { '.','6','.','.','.','.','2','8','.'};70 board.push_back(line);71 line.clear();72 line = { '.','.','.','4','1','9','.','.','5'};73 board.push_back(line);74 line.clear();75 line = { '.','.','.','.','8','.','.','7','9'};76 board.push_back(line);77 Solution sol;78 sol.solveSudoku(board);79 for(int i=0;i (cout," "));81 cout<