基礎知識要求：

Java： 方法、for循環、if else語句、數組

Python： 方法、for循環、if else語句、列表

題目：?

編寫一個程序，通過填充空格來解決數獨問題。

數獨的解法需?遵循如下規則：

1. 數字?1-9?在每一行只能出現一次。
2. 數字?1-9?在每一列只能出現一次。
3. 數字?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]?是一位數字或者?'.'
• 題目數據?保證?輸入數獨僅有一個解

思路解析：

這個解題思路是一個典型的回溯算法在數獨求解問題上的應用，它非常直觀且易于理解。下面是對這個解題思路的總結：

1. 初始化：
   • 提供一個初始的數獨板（在這個例子中是通過一個二維列表表示的）。
   • 如果數獨板沒有完全填充（即含有.作為占位符），則需要進行求解。
2. 定義is_valid函數：
   • 這是一個輔助函數，用于檢查在給定位置(row, col)填入數字num是否有效。
   • 檢查包括：當前行、當前列以及所在的3x3宮格內是否已存在該數字。
3. 定義solve_sudoku函數：
   • 這是求解數獨的核心函數，它使用回溯法來嘗試填充每一個空格。
   • 對于數獨板上的每一個空格（即值為.的位置）：
     • 嘗試填入數字1到9。
     • 如果填入某個數字后，數獨仍然有效（通過is_valid函數檢查），則繼續遞歸地求解剩余的空格。
     • 如果遞歸求解成功（即找到了一個解），則返回True。
     • 如果遞歸求解失敗（即當前數字不合適），則回溯，將該空格重新置為.，并嘗試下一個數字。
   • 如果嘗試完所有數字后仍然沒有找到解，則返回False。
   • 如果所有空格都成功填充，則返回True，表示找到了一個解。
4. 求解與輸出：
   • 調用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("無解")