日別アーカイブ: 2022-06-24

Advanced Navigation

Advanced Navigationとは

ナンバープレイスを解くに当たって、当初81個のマス目に課題で指定された数字で埋め込まれている画面が表示されます。

適切な数を選んで81マスを埋め込むには、ナンプレのルールを適用した複数の候補数を上げて後に最適値に絞る作業をすることが定番になっています。候補数を上げることは問題を局所化し、空きマスを埋め込む大きなヒントになります。

多くのサイトでは、初期画面に候補数を埋め込む動作をアドバンスド ナビゲーション(Advanced Navigation)と呼んでいます。当サイトでもこの呼び方を踏襲します。

上図に示した例題はサイトに掲載された課題を上下左右反転したり平行移動して作ったものです。左右反転すれば正解も反転状態になるとは限りませんが、正解に至る過程はほぼ同一のようです。論理的な解明はこれからです。

当課題のナビゲーション

当サイトでは数独自動解法ソフトをJavaScriptを用いて開発中です。2番目のメニューナビを選ぶことによってナビゲーション画面が以下のように現れます。ソフトはかなり大きなサイズになっており公開は後々、行われる予定です。

大きな緑色字の数字は課題で与えられており、チョコレート色の小さな数字が候補数になります。1マスにおいて候補数の最大値は9個で上の図は初期確定数字が27個の例です。既知数として20個程度与えられる課題が多く候補数は2~7個ほどでしょう。候補数を絞り1つになった時が確定で大きい黒色の数字で表示されます。

確定状況は右のできごと欄に時間差を伴って表示され、ナンプレの解析に役立つよう配慮されています。

候補数の算出法

当サイトで採用している候補数の算出法を紹介します。81マスを0~80の番号を振って0から順に80まで繰り返します。上の図のピンクで示した4-5マスを例に説明します。説明上の行・列・ブロック番号は1~9に割り振り、ピンクのマスはrc45と表現して候補数決め方の具体例は以下の通りです。

行では8個の青色マス、列では8個の茶色マス、ブロックでは黄色の4マス、合計20マスを1組として検索します。20マスの中で1~9の数字のうち、1個も現れない数字が候補数になります。9種類の数字が表れた場合は不完全な課題として報告します。

1つのコマに対応する20個のデータは0~80コマ番号に依存し、あらかじめ求めておきテーブルとして参照します。

確定処理をしない

コマ番号0から80まで順に候補数を検索すると課題によっては候補数が1になることがあり、確定処理をすると当該マスの他、20マスに関わる検索をしなければなりません。

確定処理は再帰的な処理を施せば単純化できますが、すべて単一候補による解法だけで解ける課題はアドバンスドナビゲーションだけで終了することになり、既知数と確定数からなる完成画面になり途中図を得ることができなくなります。

そのため、アドバンスドナビゲーションにおいては候補数が1個になっても確定処理をせずに小さなサイズで右図のように表示されます。rc22, rc23, rc31, rc32に未確定の候補数が存在します。