回溯---数独

拼搏现实的明天。 2021-11-29 07:58 333阅读 0赞

### 数独 ###

[37. Sudoku Solver (Hard)][37. Sudoku Solver _Hard]

Empty cells are indicated by the character `'.'`.

![1652742-20190701162544773-1717879681.png][]  
![1652742-20190701162611582-1378792577.png][]

#### 题目描述： ####

设计一个程序，通过填补空出的格子，使其成为一个数独问题。数独游戏的规则是：

1.每一行中1-9的每个数字只能出现一次。

2.每一列中1-9的每个数字只能出现一次。

3.在一个3x3的矩阵中1-9的每个数字只能出现一次。

#### 思路分析： ####

根据数独的三个游戏规则，我们设置三个标记数组，分别记录每行，每列，每3x3矩阵中哪个数字已经被访问。然后利用回溯的思想进行填充。

#### 代码： ####

class Solution { public boolean[][]rowUsed=new boolean[9][10]; //记录每一行中已经填充的数字 public boolean[][]colUsed=new boolean[9][10]; //记录每一列中已经填充的数字 public boolean[][]cubeUsed=new boolean[9][10]; //记录每一个3x3方阵中已经填充的数据 public void solveSudoku(char[][]board){ for(int i=0;i<board.length;i++){ for(int j=0;j<board[0].length;j++){ if(board[i][j]=='.') continue; int num=board[i][j]-'0'; rowUsed[i][num]=true; colUsed[j][num]=true; cubeUsed[cubeNum(i,j)][num]=true; } } backtracking(0,0,board); } public boolean backtracking(int row,int col,char[][]board){ while(row<9&&board[row][col]!='.'){//查看是否填充完毕，如果填充完毕，最后row为9，那么返回true。 row=col==8?row+1:row; col=col==8?0:col+1; } if(row==9) return true; for(int num=1;num<=9;num++){ if(rowUsed[row][num]||colUsed[col][num]||cubeUsed[cubeNum(row,col)][num]) continue; board[row][col]=(char)(num+'0'); rowUsed[row][num]=true; colUsed[col][num]=true; cubeUsed[cubeNum(row,col)][num]=true;//标记num已经在该行该列，该cube中使用过。 if(backtracking(row,col,board)) return true; board[row][col]='.'; rowUsed[row][num]=false; colUsed[col][num]=false; cubeUsed[cubeNum(row,col)][num]=false; } return false; } public int cubeNum(int i,int j){ //根据元素的行号和列号，来确定其属于哪个3x3小方阵 int r=i/3; int c=j/3; return r*3+c; } }

转载于:https://www.cnblogs.com/yjxyy/p/11114838.html

[37. Sudoku Solver _Hard]: https://leetcode.com/problems/sudoku-solver/description/
[1652742-20190701162544773-1717879681.png]: /images/20211129/240fefdfd65044dfbf448d4928810fc1.png
[1652742-20190701162611582-1378792577.png]: /images/20211129/2e0a98b4ac7b4f6faf4de6e989d6dc0e.png