LeetCode 37 Sudoku Solver

2021-03-13

数独を解いてくださいという問題。

最初にやってみたけどダメだった解き方

縦の並び、横の並び、3×3の領域にある数字から、入る数字が一意に定まるマスを探す
あればそのマスを埋める
空いているますがあれば1.に戻る

これは非常にバカな間違いで、数独においては必ずしもそうして数字が決められるわけではないのだった。

次に試した解き方

fillという関数を定義して、fill(board, 0, 0)を呼び出して全てのマスを埋める。
で、そのfillは次のようになる。(TypeScript)

function fill(board: string[][], x: number, y: number): boolean {
  // yが9ということは領域外===全てのマスを埋めることができたので成功
  if (y === 9) return true
  
  const nextX = x === 9 ? 0 : x
  const nextY = x === 9 ? y + 1 : y
  
  // 数字がすでに入っている場合
  if (board[y][x] !== '.') {
    // 次のマスに進む
    return fill(board, nextX, nextY)
  }
  
  // その場所に入れることができる全ての数字を列挙する
  for (const char of possibleChars(board, x, y)) {
    // 数字をそのマスに入れてみて次のマスに進み、そのまま最後のマスまで到達できたら成功
    board[y][x] = char
    if (fill(board, nextX, nextY)) return true
  }
  
  // どの数字もダメだった場合は、マスを空にして終了する
  board[y][x] = '.'
  return false
}

function possibleChars(board: string[][], x: number, y: number): Iterable<string> {
  // 省略
}

まあ要するにおける数字を手当たり次第に試していくというごく簡単なやり方であるが、
ダメな手を打つとその先で打つ手が無くなってしまうはずなので、意外とステップ数は爆発しないと思う。

だが、これを提出してみると再帰が深すぎてエラーになってしまった。
処理系がちょっと弱すぎないか...。
別の言語使えって話かもしれないが。

今のところLeetCodeは解ける問題は全部TypeScriptで解いているが、再帰が全然使えないので困っている。
(再帰を使わずにどうやって解くかというのを考えるのも楽しいけど。)

というわけで、基本的にはこのアルゴリズムで、再起を使わずにスタックを使って実装したものを提出したら合格した。

スタックのオブジェクトにIteratorを持たせておくことでループの状態をいい感じに保持できることに気づいた時は気持ちよかった。