LeetCode #37 Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

這題在旅行中嘗試解題，當初以為會像是自己解數獨題目哪樣單純，後來實際上跑測試資料才明白，有許多地方有多個選擇啊，原先寫的那套根本不能用……。

分析

先了解數獨規則，數字排列必滿足以下規則：

• 每一列 (row) 的數字必須包含 1-9，不能缺少也不能重複
• 每一行 (column) 的數字必須包含 1-9，不能缺少也不能重複
• 每一宮 (黑色框線區域，為 3x3 的九宮格)(box) 的數字必須包含 1-9，不能缺少也不能重複

如果每次挑出一空格，並展開完成該盤面的可能數字，嘗試展開所有解法路徑，可以畫成一個樹 (tree) 來思考：

其中必定存在一條從 root 到 leaf 的路徑，能將其盤面填滿，並且盤面上的所有數字，能滿足數獨的所有條件規則。（題目假設只有唯一解）

可以注意到的是，在決定空格能填什麼數字時，已經將不符合規則的數字排除，以減少後續的計算量 (即是 Pruning)。

在這次解法中並沒有建立額外記憶體空間，來儲存所有可能的正確解法 (因為題目考慮只有唯一解法)，且採用遞迴函數 (recursive-function) 來找解法，因此如果發現該數字無法解答，會倒帶 (roll-back) 回去原本的狀態，然後繼續測試下一種可能。

解法

使用 Go：

import (
   "context"
)

func solveSudoku(board [][]byte) {
   solve(board)
}

func solve(board [][]byte) bool {
   for x := 0; x < 9; x++ {
      for y := 0; y < 9; y++ {
         if board[x][y] == '.' {
            ctx, cancel := context.WithCancel(context.Background())
            for n := range possibles(board, x, y, ctx) {
               board[x][y] = n
               if solve(board) {
                  cancel()  // Avoid goroutine leak
                  return true
               } else {
                  board[x][y] = '.'  // Roll back
               }
            }
            return false
         }
      }
   }
   return true
}

func possibles(board [][]byte, x, y int, ctx context.Context) <-chan byte {
   c := make(chan byte)
   b := make([]bool, 10)
   
   // Row
   for xx := 0; xx < 9; xx++ {
      if n := board[xx][y] - '0'; n < 10 {
         b[n] = true
      }
   }
   
   // Column
   for yy := 0; yy < 9; yy++ {
      if n := board[x][yy] - '0'; n < 10 {
         b[n] = true
      }
   }
   
   // Box
   bx := (x / 3) * 3
   by := (y / 3) * 3
   for xx := 0; xx < 3; xx++ {
      for yy := 0; yy < 3; yy++ {
         if n := board[bx+xx][by+yy] - '0'; n < 10 {
            b[n] = true
         }
      }
   }
   
   // Use channel to output numbers (iterator pattern)
   go func() {
      defer close(c)
      for i := 1; i < 10; i++ {
         if !b[i] {
            select {
            case c <- (byte)('0' + i):
            case <-ctx.Done():
               return
            }
         }
      }
   }()
   
   return c
}