Java 回溯法解数独

2022-09-27 08:09:34

题干:输入一个9*9二维数组表示数独,已经填入的数字用1-9表示,待填入的数字用0表示,试写一个算法解出数独并输出。
在这里插入图片描述
在这里插入图片描述
思路:容易想到回溯法,即以人的思维的解数独,遍历数组,如果是空白就从1-9依次选一个数判断本行、列、3*3宫格内是否有重复,如果有就进行下一个数字的选择;如果该数暂时满足条件,那么进行下一个格子的选择,递归的终止条件是遍历完所有格子。

代码分段演示

输入数组

Scanner sc=newScanner(System.in);int[][] board=newint[9][9];// 输入for(int i=0; i<9; i++){for(int j=0; j<9; j++){
        board[i][j]= sc.nextInt();}}

dfs回溯

(r, c)是当前正在判断的格子坐标,board[r][c] == 0判断这个格子是否还没有填数,如果没有,就从1-9依次选取一个数,先判断选的这个数是否合法,如果合法就做选择,并开始下一个格子的判断,决定完下一个格子之后就撤销选择(这是回溯法基本框架);如果该格子已填数,直接开始下一个格子的判断。终止条件就是r==9,也就是二维数组遍历完。

publicstaticvoiddfs(int[][] board,int r,int c){// 所有数填完了,输出if(r==9){for(int i=0; i<9; i++){for(int j=0; j<9; j++){System.out.print(board[i][j]+" ");}System.out.println();}return;}// 空白填数if(board[r][c]==0){// 从 1-9 中依次选数for(int k=1; k<=9; k++){// 先判断放进去是否满足条件再选择if(isValid(board, r, c, k)){// 做选择
	            board[r][c]= k;// 决定下一个格子next(board, r, c);// 撤销选择
	            board[r][c]=0;}}}// 非空白直接决定下一个格子elsenext(board, r, c);}

在二维数组中,下一个格子有两种可能:一是就在本行只需列+1即可,二是当前格子是本行最后一个,那么下一个格子就是下一行第一个。

// 递归下一个格子publicstaticvoidnext(int[][] board,int r,int c){if(c+1==9)dfs(board, r+1,0);elsedfs(board, r, c+1);}

判断是否满足条件

行和列的判断就不必细说了,关键是3*3宫格的判断,行 / 3 * 3列 / 3 * 3 就是所在的3*3宫格左上角格子的坐标,其中 / 是地板除法

// 判断是否合法publicstaticbooleanisValid(int[][] board,int r,int c,int val){// 列for(int i=0; i<9; i++){if(board[i][c]== val)returnfalse;}// 行for(int j=0; j<9; j++){if(board[r][j]== val)returnfalse;}// 3 * 3for(int x= r/3*3, i= x; i< x+3; i++){for(int y= c/3*3, j= y; j< y+3; j++){if(board[i][j]== val)returnfalse;}}returntrue;}

完整代码

publicstaticvoidmain(String[] args){solveSudoku();}publicstaticvoidsolveSudoku(){Scanner sc=newScanner(System.in);int[][] board=newint[9][9];// 输入for(int i=0; i<9; i++){for(int j=0; j<9; j++){
            board[i][j]= sc.nextInt();}}dfs(board,0,0);}// 回溯填数publicstaticvoiddfs(int[][] board,int r,int c){// 所有数填完了,输出if(r==9){for(int i=0; i<9; i++){for(int j=0; j<9; j++){System.out.print(board[i][j]+" ");}System.out.println();}return;}// 空白填数if(board[r][c]==0){for(int k=1; k<=9; k++){if(isValid(board, r, c, k)){// 做选择
                board[r][c]= k;// 决定下一个格子next(board, r, c);// 撤销选择
                board[r][c]=0;}}}// 非空白直接决定下一个格子elsenext(board, r, c);}// 递归下一个格子publicstaticvoidnext(int[][] board,int r,int c){if(c+1==9)dfs(board, r+1,0);elsedfs(board, r, c+1);}// 判断是否合法publicstaticbooleanisValid(int[][] board,int r,int c,int val){// 列for(int i=0; i<9; i++){if(board[i][c]== val)returnfalse;}// 行for(int j=0; j<9; j++){if(board[r][j]== val)returnfalse;}// 3 * 3for(int x= r/3*3, i= x; i< x+3; i++){for(int y= c/3*3, j= y; j< y+3; j++){if(board[i][j]== val)returnfalse;}}returntrue;}

顺便提供几个示例输入输出

输入:530070000600195000098000060800060003400803001700020006060000280000419005000080079

输出:534678912672195348198342567859761423426853791713924856961537284287419635345286179
输入:000500900604203000500060032000090400420105079009700100900006018200040005000000600

输出:732581964694273581518469732175698423426135879389724156947356218261847395853912647
输入:009748000700000000020109000007000240064010590098000300000803020000000006000275900

输出:519748632783652419426139875357986241264317598198524367975863124832491756641275983
  • 作者:来自大山深处的Doge_
  • 原文链接:https://blog.csdn.net/qq_45822970/article/details/117414590
    更新时间:2022-09-27 08:09:34