怎么在Java中利用回溯算法解数独

本篇文章为大家展示了怎么在Java中利用回溯算法解数独，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

一、题干

输入一个9*9二维数组表示数独，已经填入的数字用1-9表示，待填入的数字用0表示，试写一个算法解出数独并输出。

二、思路

容易想到回溯法，即以人的思维的解数独，遍历数组，如果是空白就从1-9依次选一个数判断本行、列、3*3宫格内是否有重复，如果有就进行下一个数字的选择；如果该数暂时满足条件，那么进行下一个格子的选择，递归的终止条件是遍历完所有格子。

三、代码分段演示

输入数组

Scanner sc = new Scanner(System.in); int[][] board = new int[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，也就是二维数组遍历完。

public static void dfs(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;	        }	    }	}	// 非空白直接决定下一个格子	else next(board, r, c); }

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

// 递归下一个格子 public static void next(int[][] board, int r, int c) {     if (c + 1 == 9) dfs(board, r + 1, 0);     else dfs(board, r, c + 1); }

判断是否满足条件

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

// 判断是否合法 public static boolean isValid(int[][] board, int r, int c, int val) {     // 列     for (int i = 0; i < 9; i++) {         if (board[i][c] == val) return false;     }     // 行     for (int j = 0; j < 9; j++) {         if (board[r][j] == val) return false;     }     // 3 * 3     for (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) return false;         }     }     return true; }

四、完整代码

public static void main(String[] args) {     solveSudoku(); } public static void solveSudoku() {     Scanner sc = new Scanner(System.in);     int[][] board = new int[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); } // 回溯填数 public static void dfs(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;             }         }     }     // 非空白直接决定下一个格子     else next(board, r, c); } // 递归下一个格子 public static void next(int[][] board, int r, int c) {     if (c + 1 == 9) dfs(board, r + 1, 0);     else dfs(board, r, c + 1); } // 判断是否合法 public static boolean isValid(int[][] board, int r, int c, int val) {     // 列     for (int i = 0; i < 9; i++) {         if (board[i][c] == val) return false;     }     // 行     for (int j = 0; j < 9; j++) {         if (board[r][j] == val) return false;     }     // 3 * 3     for (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) return false;         }     }     return true; }

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

输入： 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 输出： 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9

输入： 0 0 0 5 0 0 9 0 0 6 0 4 2 0 3 0 0 0 5 0 0 0 6 0 0 3 2 0 0 0 0 9 0 4 0 0 4 2 0 1 0 5 0 7 9 0 0 9 7 0 0 1 0 0 9 0 0 0 0 6 0 1 8 2 0 0 0 4 0 0 0 5 0 0 0 0 0 0 6 0 0 输出： 7 3 2 5 8 1 9 6 4 6 9 4 2 7 3 5 8 1 5 1 8 4 6 9 7 3 2 1 7 5 6 9 8 4 2 3 4 2 6 1 3 5 8 7 9 3 8 9 7 2 4 1 5 6 9 4 7 3 5 6 2 1 8 2 6 1 8 4 7 3 9 5 8 5 3 9 1 2 6 4 7

输入： 0 0 9 7 4 8 0 0 0 7 0 0 0 0 0 0 0 0 0 2 0 1 0 9 0 0 0 0 0 7 0 0 0 2 4 0 0 6 4 0 1 0 5 9 0 0 9 8 0 0 0 3 0 0 0 0 0 8 0 3 0 2 0 0 0 0 0 0 0 0 0 6 0 0 0 2 7 5 9 0 0 输出： 5 1 9 7 4 8 6 3 2 7 8 3 6 5 2 4 1 9 4 2 6 1 3 9 8 7 5 3 5 7 9 8 6 2 4 1 2 6 4 3 1 7 5 9 8 1 9 8 5 2 4 3 6 7 9 7 5 8 6 3 1 2 4 8 3 2 4 9 1 7 5 6 6 4 1 2 7 5 9 8 3

上述内容就是怎么在Java中利用回溯算法解数独，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注亿速云行业资讯频道。