合体数独を解く
数独
- 数独は、n×nマスのサブグリッドをn×n個あつめた正方形の盤面に、サブグリッドと行と列にn×n種類の記号がユニークとなるように配置するパズルです。
- 問題として盤面のいくつかのマスには手掛かりとなる記号が記入されており、それと矛盾しないような解が(通常)一意に存在します。
- 特にn=3の問題を集めた雑誌が広く流通しています。
合体数独
- 複数の数独が1つ以上のサブグリッドを共有している問題のことを、合体数独と呼ぶことにします。
- 合体数独を構成する通常の数独をサブ数独と呼びます。
- たまに雑誌などにも載っていることがあるようです。
アルゴリズム
基本的な方針
- 基本的なソルバーと同様に手筋を組み合わせて候補数を最小化し、これ以上最小化できなくなったら深さ優先探索を行います。
手筋を使った最小化
- 普通の数独の最小化ルーチンを流用して、合体数独の最小化ルーチンを作成します。
- 用いる手筋を以下に示します。
- hidden single
- naked single
- locked candidate (pointing, claiming)
- hidden subset
- naked subset
- 全体の最小化には、unique queueを使った以下のような幅優先探索を使います。
- unique queue QUEUEにすべてのサブ数独をpush
- while (QUEUEが空でない)
- QUEUEからサブ数独Sをpop
- サブ数独Sを最小化
- if (サブ数独Sが更新された)
- for s in (サブ数独Sとサブグリッドを共有するサブ数独)
- サブ数独Sがsと共有するサブグリッドを使って, sのサブグリッドを候補を削除
- if (sの候補が1つ以上消えた場合)
- QUEUEにsをpush
- for s in (サブ数独Sとサブグリッドを共有するサブ数独)
- 要するに、最小化を隣接するサブ数独に伝播させていきます。
探索アルゴリズム (仮置き)
- 上記の最小化でほとんどのn=3の問題は解けるようですが、探索アルゴリズムも一応組む必要があります。
- 空きマスを適当に探して適当に仮置きします。
- 普通の数独ソルバーと同じです。
表示アルゴリズム
- なにげに少し面倒なのが画面に表示する方法です。
- 各サブ数独の2次元の座標の情報をデータセットに含めれば良いのですが、その方法では2次元に埋め込めない問題は表現できなくなります。
- そのため、各サブ数独の連結性から表示場所を計算します。
- これも幅優先探索で求まります。
- 座標を計算したら、全体が収まるキャンバスを用意して書き込みます。
- この方法ならば、2次元埋め込み不可能な数独もリンクの接続性を自動的に無視して無理やり埋め込むことができます。
問題の難易度
- 非常に初歩的な、手筋による推論ルーチンを備えないdfsのみのソルバーで解く場合、計算量は空きマスの数に対して指数時間となります。
- そのため、そのようなソルバーで合体数独を解くのはかなり厳しいようです。
- しかし、まともな推論ルーチンを備えたソルバーならば十分高速に解くことができます。
- 空きマスの数に対して使える記号の数が増えないので、サブ数独の数に対して(候補の伝搬を行うソルバーで)指数時間かかるような問題を常に作れるかどうかはよくわかりません。
例
問題出典 (2023/12/4閲覧): https://innoludic.com/puzzle/sudoku/2015-03-13-02-21-43/sumo/659-sumo-7.html
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
| 8 | | | | 1 | | | | 5 | 8 | 7 |
| 3 | | 4 | | 0 | 8 | 7 | | 3 | | 6 |
| | 6 | 2 7 | | 4 | 7 | 5 | | 2 | | 5 |
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
| 3 6 | 5 4 | 1 | | | | | | 0 | 3 2 | |
| 5 | 3 | 8 | | | 6 1 | | | | | 1 |
| 8 | 1 | | | 3 2 | 7 5 | 8 | | 1 | | 7 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| | 5 | 3 | 6 | 8 | 3 0 | 2 | | 8 | 4 | |
| 7 | | 2 8 | | 6 | | 4 | 5 | 7 | 0 8 | 4 |
| | | 6 | 1 | | | 3 | | 4 | 5 | 0 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 5 6 | | 2 | | 5 | 8 | 6 |
| | 5 7 | | | 3 | | 7 |
| | 4 | | | | 4 | 1 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| | 5 4 | | 4 | | 8 1 | | 1 | 2 8 | | 3 |
| 0 1 | 7 | | 8 2 | 0 | 3 | | | | 2 | |
| 2 8 | 6 | | | | 4 | 7 | 3 | | | 1 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| | | 4 2 | | | 0 | | | 0 | 7 | 6 |
| 5 | 6 | 3 | | 2 | 1 | 4 | | 1 | 3 | 0 |
| 6 1 | | | | 6 | | | | | | 3 5 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| | 8 | 3 | 5 | 0 | | 5 | | | | |
| 6 | 0 | 8 | | 5 | 7 | 0 | 1 5 | | 0 5 | 4 |
| 7 | 1 | 5 | | | 3 | 8 2 | 3 | | 1 | |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| | 6 3 | 2 | | | | 7 2 |
| | | 8 | | 6 | 3 7 | 0 |
| | 8 7 | | | 0 | | 5 1 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 3 | 8 5 7 | 4 | | 3 | 2 | | | 6 4 | 0 | 5 3 |
| 0 | | | | | | 7 3 | | | 1 | |
| 4 | 3 | 2 7 | 0 6 | 4 | | 8 | 0 | | | 0 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 8 | 3 | 7 0 | | | | 3 2 | | | 8 | 6 |
| | 0 | | | | | | | | | 1 |
| 4 2 | | | | 3 | 0 | 1 8 | | 6 | 3 | 7 2 |
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
| 3 | 2 | | | 6 2 | 3 4 | 7 | | | 4 2 | 3 |
| | 1 | 6 2 | | 8 | 1 | | | 2 | 6 1 | |
| 1 | | | | | 7 | | | | 7 | 6 4 |
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
| 8 6 7 | 4 0 2 | 5 3 1 | | 1 7 3 | 0 4 5 | 2 8 6 | | 5 1 6 | 3 8 4 | 0 7 2 |
| 2 0 3 | 7 1 5 | 8 6 4 | | 0 5 6 | 3 8 2 | 7 1 4 | | 0 3 8 | 7 2 5 | 6 4 1 |
| 5 4 1 | 3 6 8 | 2 7 0 | | 8 2 4 | 1 7 6 | 3 5 0 | | 2 4 7 | 6 1 0 | 5 3 8 |
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
| 3 7 6 | 8 5 4 | 0 1 2 | | 5 1 0 | 8 2 3 | 4 6 7 | | 7 0 5 | 1 3 2 | 4 8 6 |
| 4 1 5 | 0 2 3 | 6 8 7 | | 7 4 8 | 6 0 1 | 5 2 3 | | 6 2 4 | 8 5 7 | 1 0 3 |
| 0 8 2 | 1 7 6 | 3 4 5 | | 6 3 2 | 7 5 4 | 8 0 1 | | 3 8 1 | 4 0 6 | 7 2 5 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 6 2 8 | 5 4 1 | 7 0 3 | 6 2 5 | 4 8 1 | 5 3 0 | 6 7 2 | 1 4 3 | 8 5 0 | 2 4 1 | 3 6 7 |
| 7 5 4 | 6 3 0 | 1 2 8 | 7 4 0 | 3 6 5 | 2 1 7 | 0 4 8 | 2 5 6 | 1 7 3 | 0 6 8 | 2 5 4 |
| 1 3 0 | 2 8 7 | 4 5 6 | 3 8 1 | 2 0 7 | 4 6 8 | 1 3 5 | 0 8 7 | 4 6 2 | 5 7 3 | 8 1 0 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 5 6 7 | 1 3 8 | 0 2 4 | | 7 5 1 | 8 3 2 | 6 0 4 |
| 3 4 0 | 2 5 7 | 6 1 8 | | 3 2 4 | 6 1 0 | 7 8 5 |
| 2 8 1 | 0 6 4 | 5 7 3 | | 8 6 0 | 4 7 5 | 2 3 1 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 7 3 6 | 5 4 0 | 8 1 2 | 4 0 3 | 7 5 6 | 8 2 1 | 4 0 3 | 7 6 1 | 5 2 8 | 1 4 7 | 6 3 0 |
| 0 1 4 | 2 8 7 | 6 3 5 | 8 7 2 | 1 4 0 | 7 5 3 | 2 8 6 | 5 0 4 | 3 1 7 | 6 2 0 | 5 4 8 |
| 2 5 8 | 1 3 6 | 0 7 4 | 5 1 6 | 8 3 2 | 6 0 4 | 5 1 7 | 3 2 8 | 0 4 6 | 3 5 8 | 1 7 2 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 3 8 7 | 0 5 1 | 4 2 6 | | 3 8 1 | 0 4 5 | 6 7 2 | | 8 3 0 | 5 7 4 | 2 6 1 |
| 4 2 5 | 7 6 8 | 3 0 1 | | 2 7 5 | 1 6 8 | 3 4 0 | | 1 5 2 | 8 6 3 | 7 0 4 |
| 6 0 1 | 4 2 3 | 5 8 7 | | 6 0 4 | 3 7 2 | 1 5 8 | | 6 7 4 | 0 1 2 | 3 8 5 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 5 4 0 | 8 7 2 | 1 6 3 | 7 4 5 | 0 2 8 | 4 1 6 | 7 3 5 | 8 4 6 | 2 0 1 | 4 3 6 | 8 5 7 |
| 1 6 2 | 3 0 5 | 7 4 8 | 2 6 0 | 5 1 3 | 2 8 7 | 0 6 4 | 1 5 2 | 7 8 3 | 2 0 5 | 4 1 6 |
| 8 7 3 | 6 1 4 | 2 5 0 | 1 3 8 | 4 6 7 | 5 3 0 | 8 2 1 | 0 7 3 | 4 6 5 | 7 8 1 | 0 2 3 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 4 8 1 | 6 5 3 | 2 7 0 | | 1 4 8 | 5 6 0 | 3 7 2 |
| 5 7 6 | 0 2 4 | 3 8 1 | | 2 5 6 | 3 1 7 | 8 4 0 |
| 3 0 2 | 8 7 1 | 6 4 5 | | 3 0 7 | 2 8 4 | 5 1 6 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 2 6 3 | 8 5 7 | 0 1 4 | 5 8 2 | 7 3 6 | 8 4 2 | 5 1 0 | 7 3 8 | 6 2 4 | 0 8 7 | 5 1 3 |
| 0 8 7 | 4 1 2 | 6 3 5 | 4 1 7 | 8 0 2 | 6 5 1 | 4 7 3 | 6 2 1 | 0 5 8 | 2 1 3 | 6 4 7 |
| 1 4 5 | 6 3 0 | 8 2 7 | 3 0 6 | 1 5 4 | 0 7 3 | 6 8 2 | 4 0 5 | 1 3 7 | 5 4 6 | 8 2 0 |
+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+
| 5 1 8 | 2 4 3 | 7 0 6 | | 4 8 0 | 1 6 7 | 3 2 5 | | 4 7 1 | 8 0 2 | 3 5 6 |
| 3 7 6 | 0 8 5 | 2 4 1 | | 2 1 5 | 4 3 8 | 7 0 6 | | 2 0 3 | 7 6 5 | 4 8 1 |
| 4 0 2 | 1 7 6 | 5 8 3 | | 3 6 7 | 2 0 5 | 1 4 8 | | 8 6 5 | 1 3 4 | 0 7 2 |
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
| 6 3 0 | 5 2 4 | 1 7 8 | | 6 2 1 | 3 8 4 | 0 5 7 | | 7 8 6 | 4 2 0 | 1 3 5 |
| 8 5 4 | 7 0 1 | 3 6 2 | | 0 7 8 | 5 1 6 | 2 3 4 | | 3 4 2 | 6 5 1 | 7 0 8 |
| 7 2 1 | 3 6 8 | 4 5 0 | | 5 4 3 | 7 2 0 | 8 6 1 | | 5 1 0 | 3 7 8 | 2 6 4 |
+---------+---------+---------+ +---------+---------+---------+ +---------+---------+---------+
389 microseconds
guesscount: 0