基础知识要求:
Java: 方法、for循环、if else语句、数组
Python: 方法、for循环、if else语句、列表
题目:
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.'
表示。
示例 1:
输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","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"]] 解释:输入的数独如上图所示,唯一有效的解决方案如下所示:
提示:
board.length == 9
board[i].length == 9
board[i][j]
是一位数字或者'.'
- 题目数据 保证 输入数独仅有一个解
思路解析:
这个解题思路是一个典型的回溯算法在数独求解问题上的应用,它非常直观且易于理解。下面是对这个解题思路的总结:
- 初始化:
- 提供一个初始的数独板(在这个例子中是通过一个二维列表表示的)。
- 如果数独板没有完全填充(即含有
.
作为占位符),则需要进行求解。
- 定义
is_valid
函数:- 这是一个辅助函数,用于检查在给定位置
(row, col)
填入数字num
是否有效。 - 检查包括:当前行、当前列以及所在的3x3宫格内是否已存在该数字。
- 这是一个辅助函数,用于检查在给定位置
- 定义
solve_sudoku
函数:- 这是求解数独的核心函数,它使用回溯法来尝试填充每一个空格。
- 对于数独板上的每一个空格(即值为
.
的位置):- 尝试填入数字1到9。
- 如果填入某个数字后,数独仍然有效(通过
is_valid
函数检查),则继续递归地求解剩余的空格。 - 如果递归求解成功(即找到了一个解),则返回True。
- 如果递归求解失败(即当前数字不合适),则回溯,将该空格重新置为
.
,并尝试下一个数字。
- 如果尝试完所有数字后仍然没有找到解,则返回False。
- 如果所有空格都成功填充,则返回True,表示找到了一个解。
- 求解与输出:
- 调用
solve_sudoku
函数来求解数独。 - 如果求解成功,则打印出解出的数独板;否则,输出“无解”。
- 调用
Java代码示例:
public class SudokuSolver { // 检查数字在行、列和3x3宫格内是否有效 public static boolean isValid(char[][] board, int row, int col, char num) { // 检查行 for (int i = 0; i < 9; i++) { if (board[row][i] == num) { return false; } } // 检查列 for (int i = 0; i < 9; i++) { if (board[i][col] == num) { return false; } } // 检查3x3宫格 int startRow = 3 * (row / 3); int startCol = 3 * (col / 3); for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (board[i + startRow][j + startCol] == num) { return false; } } } return true; } // 递归求解数独 public static boolean solveSudoku(char[][] board) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') { for (char num = '1'; num <= '9'; num++) { if (isValid(board, i, j, num)) { board[i][j] = num; // 递归尝试下一个空格 if (solveSudoku(board)) { return true; } // 回溯 board[i][j] = '.'; } } // 尝试完所有数字都不可行,说明当前空格无解,返回false return false; } } } // 所有空格都填满了,说明找到解了 return true; } // 主函数,用于测试 public static void main(String[] args) { char[][] board = { {'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'} }; if (solveSudoku(board)) { // 格式化输出 for (char[] row : board) { for (char num : row) { System.out.print(num + " "); } System.out.println(); } } else { System.out.println("无解"); } }
}
Python代码示例:
def is_valid(board, row, col, num): # 检查行中是否已存在该数字 for i in range(9): if board[row][i] == num: return False # 检查列中是否已存在该数字 for i in range(9): if board[i][col] == num: return False # 检查3x3宫格中是否已存在该数字 start_row = 3 * (row // 3) start_col = 3 * (col // 3) for i in range(3): for j in range(3): if board[i + start_row][j + start_col] == num: return False return Truedef solve_sudoku(board): for i in range(9): for j in range(9): if board[i][j] == '.': for num in ['1', '2', '3', '4', '5', '6', '7', '8', '9']: if is_valid(board, i, j, num): board[i][j] = num if solve_sudoku(board): return True # 如果当前数字不合法,回溯 board[i][j] = '.' # 尝试完所有数字都不可行,说明无解 return False # 所有空格都填满了,说明找到解了 return True # 示例输入
board = [["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] # 转换为二维列表
board = [list(map(str, row)) for row in board] # 求解数独
if solve_sudoku(board): # 格式化输出 for row in board: print(row)
else: print("无解")