[LeetCode] 37. Sudoku Solver 刷題筆記

題目

題目有點長，直接放上 LeetCode 連結：
https://leetcode.com/problems/sudoku-solver/

簡單來說就是要做一個自動產生數獨解答的程式。
題目會輸入一個二維陣列，數獨題目空白的地方會用”.”代替，
我們則要將數獨的答案填完回傳。

輸入的數獨題目，一定會有一個唯一解，所以不需要考慮題目有錯誤或是多重解答的情況。

解題過程

1. 從第一個空白格開始找可能的數字填上（行列和九宮格皆不重複的數字）
2. 再找下一個空白格找可能的數字
3. 如果沒有可以填的數字，則回到上一格填寫的數字，填寫下一個可能的數字。
4. 如果上一格已經沒有可以填寫的數字了，再回到上上格以此類推。如果有找到可以填寫的數字，則從第 2 步驟繼續往下。
5. 直到所有空白格都填上數字即完成。

實際程式我使用遞迴的方式，如下：

function solveSudoku(board) {
  recurse(board);
  return board
}

function recurse(board) {
  for(let row = 0; row < 9; row++){
    for(let col = 0; col < 9; col++){
      // 如果該格為空白，找出可能的數字填上
      if(board[row][col] === "."){

        // 找出所有可能的數字
        const possibles = Array.from({length: 9}, () => true)

        // 刪除相同行列出現過的數字
        for(let i=0; i<9; i++){
          if(board[row][i] !== "."){
            possibles[Number(board[row][i])-1] = false;
          }
          if(board[i][col] !== "."){
            possibles[Number(board[i][col])-1] = false;
          }
        }

        // 刪除九宮格中出現過的數字
        const blockStart = Math.floor(row/3) * 3;
        const blockEnd = Math.floor(col/3) * 3;
        for(let k=blockStart; k<blockStart+3; k++) {
          for(let l=blockEnd; l<blockEnd+3; l++) {
            if(board[k][l] !== "."){
              possibles[Number(board[k][l])-1] = false;
            }
          }
        }

        // 嘗試每個可能的數字
        for(let m = 0; m<9; m++){
          if(!possibles[m]) continue;
          board[row][col] = (m+1).toString();

          // 找下一個數字
          if(recurse(board)){
            return true;
          }
          else{
            board[row][col] = ".";
          }
        }
        // 所有數字皆不符合，return false回到上一個數字
        return false;
      }
    }
  }
  return true;
}