sudoku solver

数独ソルバー

PHP で書かれたシンプルな Sudoku パズル ソルバー。

注: このプロジェクトはまだ建設中です。

インストール

プロジェクトのルートで次のコマンドを実行して、sudoku-solver をインストールします。

 composer install

用語

 Square      One of the m x n values on the puzzle board
Row         Horizontal M squares
Column      Vertical N squares
Region      An m x n subset of squares
Group       M/N number of squares in a row (horizontally or vertically) 

パズルを解くための戦略

このソルバーで使用される戦略は、Sudoku Dragon で説明されている戦略に基づいています。

戦略

パズルが解けるまで、戦略を繰り返し適用する必要があります。

1. 唯一の選択ルール

   • 各行、列、領域をスキャンして、グループ内の 1 つの選択肢を探します。

2. 単一可能性ルール

   • 交差する各行と列をスキャンして、グループ内の 1 つの選択肢を探します。

3. 正方形のみのルール

   • 2 つの空のセルを含む各行/列をスキャンします。
   • 欠落している 2 つの番号 A と B を特定します。
   • 交差する各行、列、または領域をスキャンし、オプション A を排除してみます。
   • 特定のセルでオプション A を削除できる場合は、そのセルにオプション B を入力します。
   • もう一方の空のセルにオプション A を入力します。

4. 3 つのうち 2 つの法則

   • 上から下に、一度に 3 行または 3 列をスキャンして、1 から始まる特定の数値を探します。

5. サブグループ除外ルール

   • TODO

6. ブルートフォース

   • 解決策が見つかるまですべてのオプションを試してください:)

リソース

• https://www.educative.io/edpresso/how-to-check-if-a-sudoku-board-is-valid
• https://puzzling.stackexchange.com/questions/158/how-many-minimal-clue-sudoku-puzzles-are-there
• https://www.technologyreview.com/s/426554/mathematicians-solve-minimum-sudoku-problem/