学做网站从什么开始,做网站多少费用,电商软件开发费用,局域网内做网站基础知识要求#xff1a; Java#xff1a; 方法、for循环、if else语句、数组 Python#xff1a; 方法、for循环、if else语句、列表 题目#xff1a;
编写一个程序#xff0c;通过填充空格来解决数独问题。
数独的解法需 遵循如下规则#xff1a;
数字 1-9 在每一行…基础知识要求 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 9board[i].length 9board[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(无解)
