回溯法解数独

原创

孟君

发布于 2023-09-29 08:14:42

3970

发布于 2023-09-29 08:14:42

文章被收录于专栏：孟君的编程札记孟君的编程札记

继上一篇博文《回溯法解小学数字填数练习（2）》，本文再来解一个数独的的题目。

其实，在小孩子的书本上能看到4阶、6阶以及9阶的数独。如：

本文，我们以解决9阶数独为示例。有了9阶解法思路，4阶和6阶只要调整一些逻辑即可实现。

解题思路

解数独是一个经典的回溯算法问题，一种解数独的思路如下：

1、定义一个9x9的二维数组来表示数独棋盘，用0表示未填写的空格。
2、创建一个解决一个处理方法，对入参进行基本的校验
3、创建一个递归函数，该函数用于尝试在当前位置填写一个数字，并继续递归地填写下一个位置，
直到填写完整个数独棋盘或出现冲突。
3、在每个位置尝试填写数字时，需要检查当前位置的行、列和3x3小九宫格是否已经存在相同的数字。
如果不存在冲突，就可以填写数字，然后继续递归地填写下一个位置。
4、如果填写过程中出现冲突，就需要回溯到上一个位置，尝试填写其他数字，
直到找到一个合适的数字或者回溯到某个位置无解。

接下来，我们就根据上述方法来写一个解数独的程序。

定义一个二维数组

定义一个二维数组int[][] board ，作为初始化的棋盘，如：还未填数的棋盘

int[][] board = new int[9][9]

再如：有部分已填数的棋盘：

		int[][] board = { 
							{ 0, 9, 7, 1, 8, 2, 0, 3, 4 }, 
							{ 0, 3, 2, 0, 0, 0, 8, 0, 0 }, 
							{ 0, 6, 1, 4, 9, 0, 2, 5, 7 },
							{ 7, 0, 8, 3, 4, 0, 0, 0, 0 }, 
							{ 0, 0, 4, 0, 0, 0, 5, 0, 0 }, 
							{ 9, 0, 0, 2, 0, 6, 0, 7, 0 },
							{ 2, 0, 0, 0, 6, 0, 0, 0, 0 }, 
							{ 0, 0, 0, 8, 0, 4, 9, 0, 5 }, 
							{ 0, 0, 9, 0, 0, 0, 0, 4, 6 } 
						};

定义一个方法

做一些参数验证，然后调用递归方法。如：

public static boolean solve(int[][] board) {
		/**
		 * <pre>
		 * 可以做一些基本的校验，比如数组是否为空，长度是否为9，每行是否有相同参数等
		 * </pre>
		 */
		... ... 
		
		//递归寻找结果
		return doSolveRec(board);
	}

在递归方法中实现逻辑

/**
	 * 1-9数独
	 * 
	 * @param board 数独棋盘内容
	 * @return
	 */
	private static boolean doSolveRec(int[][] board) {
		for (int row = 0; row < 9; row++) {
			for (int col = 0; col < 9; col++) {
				// 如果当前数字为0，则意味着还未放置数据
				if (board[row][col] == 0) {
					// 尝试填入1到9的数字
					for (int num = 1; num <= 9; num++) {
						/**
						 * 校验当前放入的num是否有效
						 */
						if (isValid(board, row, col, num)) {
							// 将填入的数字放入空格中
							board[row][col] = num;
							// 如果继续递归能够找到解决方案，则返回true
							if (doSolveRec(board)) {
								return true;
							} else {
								// 如果继续递归无法找到解决方案，则回溯（撤销填入的数字），并将空格重置为0
								board[row][col] = 0;
							}
						}
					}
					// 如果所有数字都尝试过了，但都无法满足条件，则返回false
					return false;
				}
			}
		}
		// 如果所有空格都被填满了，则说明已经找到了解决方案，返回true
		return true;
	}

合法性校验

/**
	 * 检查在给定位置放置一个数字是否有效
	 * 
	 * @param board 9 x 9 棋盘
	 * @param row   行号
	 * @param col   列号
	 * @param num   数字
	 * @return
	 */
	private static boolean isValid(int[][] board, int row, int col, int num) {
		// 检查行和列是否有重复数字
		for (int i = 0; i < 9; i++) {
			if (board[row][i] == num || board[i][col] == num) {
				return false;
			}
		}

		// 检查3x3的小方格是否有重复数字
		int startRow = row / 3 * 3;
		int startCol = col / 3 * 3;
		for (int i = startRow; i < startRow + 3; i++) {
			for (int j = startCol; j < startCol + 3; j++) {
				if (board[i][j] == num) {
					return false;
				}
			}
		}
		return true;
	}

判断是否有解，并打印结果

如果存在解决方案，则打印出棋盘

// 如果存在解决方案，则打印出棋盘
		if (SudokuSolver.solve(board)) { 
			SudokuSolver.printBoard(board);
		} else { 
			// 如果不存在解决方案，则输出提示信息
			System.out.println("无解");
		}

打印棋盘

	/**
	 * 打印9 x 9 数独棋盘
	 * 
	 * @param board
	 */
	public static void printBoard(int[][] board) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.println();
		}
	}

这样基本上一个解决数独的大致框架就定好了。

代码截图如下

SodokuSolver.java

Main.java

运行一下，我们可以看到数独的答案。

5 9 7 1 8 2 6 3 4 
4 3 2 6 7 5 8 1 9 
8 6 1 4 9 3 2 5 7 
7 5 8 3 4 9 1 6 2 
6 2 4 7 1 8 5 9 3 
9 1 3 2 5 6 4 7 8 
2 4 5 9 6 7 3 8 1 
1 7 6 8 3 4 9 2 5 
3 8 9 5 2 1 7 4 6

如果初始棋盘为空int[][] board = new int[9][9]，运行结果：

1 2 3 4 5 6 7 8 9 
4 5 6 7 8 9 1 2 3 
7 8 9 1 2 3 4 5 6 
2 1 4 3 6 5 8 9 7 
3 6 5 8 9 7 2 1 4 
8 9 7 2 1 4 3 6 5 
5 3 1 6 4 2 9 7 8 
6 4 2 9 7 8 5 3 1 
9 7 8 5 3 1 6 4 2

这样，给定一个棋盘，一个解数独的程序就写好了。

补充校验逻辑

那么问题来了，如果上述初始化一行有2个一样的数字，按照上述的逻辑判断，也能给出一个解。但是，这个解其实是错的。如：

所以，我们在去做递归方法之前，对入参进行基本的校验。

补充校验类

做些基本判断，比如：

判断棋盘是否为 9 x 9
检查每一行、每一列、每一个小砖块有没有重复的数字
... ...

import java.util.HashSet;
import java.util.Set;

public class SudokuValidator {

	public static boolean isValidSudoku(int[][] board) {

		if (board == null || board.length != 9 || board[0].length != 9) {
			return false;
		}

		/**
		 * 检查每一行、每一列、每一个小砖块有没有重复的数字
		 */
		for (int i = 0; i < 9; i++) {
			if (!isValidRow(board, i) || !isValidColumn(board, i) || !isValidSubgrid(board, i)) {
				return false;
			}
		}

		return true;
	}

	private static boolean isValidRow(int[][] board, int row) {
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < 9; i++) {
			if (board[row][i] != 0 && !set.add(board[row][i])) {
				return false;
			}
		}
		return true;
	}

	private static boolean isValidColumn(int[][] board, int col) {
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < 9; i++) {
			if (board[i][col] != 0 && !set.add(board[i][col])) {
				return false;
			}
		}
		return true;
	}

	private static boolean isValidSubgrid(int[][] board, int subgrid) {
		int rowOffset = (subgrid / 3) * 3;
		int colOffset = (subgrid % 3) * 3;
		Set<Integer> set = new HashSet<>();

		for (int i = rowOffset; i < rowOffset + 3; i++) {
			for (int j = colOffset; j < colOffset + 3; j++) {
				if (board[i][j] != 0 && !set.add(board[i][j])) {
					return false;
				}
			}
		}
		return true;
	}

}