❸単一候補検出(single candidate)

前回は解法のあらましと81マスの呼び方についてまとめました。

今回は解法のなかで基本中の基本と言われる『単一候補検出(Single Candidate)』を前回に述べたアルゴリズムを具現化し、実際にプログラミングして易しい課題を解いてみることにします。

また、マス目の呼び方を変更したので行・列・ブロック説明図を右に再掲します。

解法のおさらい

single candidateは行・列・ブロックを包括的に眺めて、1～9の数字で使われていない最後の数字を引き当てて空マスを埋める方法です。

人間の目で行・列・ブロックを観察すれば必ず引き当てることができますが、確定数字が簡単に8になる課題は少なく7個以内の時に、調査した状況を候補として管理します。

81個のマスを目で追い、状況を頭に記憶することは至難の技です。このような場面において論理的思考を働かせてプログラミングを完成させましょう。

上の課題において、single candidate解法を用いてピンク色RC26の空マスに適切な数字を埋め込むに当たり、関係する領域は2行、6列、2ブロックです。

2行では2, 6, 7, 8, 9が、6列では1, 3, 5, 7, 8が、2ブロックでは1, 2, 7, 8, 9が既に使われているので最後の候補として4が確定します。

確定したマスは次に解析が進んだときは既知情報として利用します。

候補数が2以上ならばこれらの情報を管理下に置いて次に進みます。この処理をすべてのマスに適用します。

81マスまで解析が進んだとき、新規に埋め込んだマスが0ならばSingle Candidateではもはや解けない状況になっており、別の解法に進まなければなりません。

上記動作結果は81個のうち、39マスに数字が埋まっている状態（残42）でスタートし、1回目の挑戦で21マスが埋まり2回目の挑戦で13マスが解決、3回目で2マス解決し残7になったところで限界を迎えた例を示しています。

動作例と操作方法

以下にはHTMLプログラムコードが埋め込まれており、question-reidai2が課題として与えられていて初期画面が表示されています。

開始ボタンをクリックすれば、Single Candidate解法により正解が得られ、赤色縁取り文字で空マスが選ばれた数字で埋め込まれます。

右上のスピード調整ボタンにマウスをかざすと実行速度を変更することができます。

選択ボタンをクリックし、ファイル選択ボタンを押してCSVファイルから81個のナンプレ数字を読み込むことができます。

選択ファイルは何度でも読み直すことが可能で送信ボタンを押して開始に進むことができます。ファイル選択ダイアログを使えばローカルファイルを指定することも可能です。

開始ボタン直下のスピーカ―ボタンをクリックするとピッという進行音をミュートにできます。

課題ファイルの書式

課題はCSV形式で作成し指定したファイルを読み込みます。

課題例

 0, 0, 3, 0, 0, 0, 9, 0, 0
 4, 0, 0, 9, 5, 6, 0, 0, 3
 0, 0, 5, 1, 0, 8, 2, 0, 0
 9, 7, 4, 5, 6, 0, 3, 0, 0
 2, 3, 8, 7, 4, 9, 0, 1, 6
 1, 0, 0, 0, 8, 2, 0, 9, 4
 0, 6, 0, 8, 2, 0, 0, 5, 0
 7, 0, 2, 4, 9, 5, 0, 3, 1
 5, 4, 9, 0, 1, 3, 0, 7, 2
チェック用課題-01

プログラミングについて

プログラミングはHTML(css, JavaScript)により記述され、コードファイルは6つに分割され、全体サイズは思いのほか大きく、まだ初期バージョンながら大作と言えましょう。

解法のアルゴリズムは前回に取り上げた『ナンプレさくさく』を参照しましたがプログラムコードはオリジナルです。言語処理系のJavaScriptには文字列操作など多彩な関数を所有しており、使い方を工夫すれば短いコードで目的を達することができます。

あとがき

single candidateは対象マスを取り巻く行・列・ブロック内だけの情報を制御する単純な方式です。難解な課題を解くことはできません。次回は9個からなる集団情報を眺めて、その特性を把握して適切な候補に絞る解法を追加する予定です。

二国同盟(Naked Pairs)

次回