第20回
2012年 1月号
|
裏ルールを探せ! 〜出題者は使ってはいけない〜
数独(ナンバープレイス)を機械的に解いてみる【改訂版】
|
|
|
操作方法問題入力問題のヒントの数字を設定するには,各マス内の小さい数字をクリックします。一度設定した数字を消すには,その数字と同じ小さい数字をもう一度クリックします。 例1〜例3のボタンをクリックすると,問題例をロードできます。問題例をエディットして使用することもできます。 ソルバーモードから入力画面に戻ると,前回解かせた問題からの編集となります。データを消して最初から入力するには,クリアボタンをクリックします。 ソルバー入力画面から「入力終了」をクリックすると,ソルバーモードとなります。ここでは, 「実行」ボタンではステップ毎に停止し,「連続実行」ボタンでは停止せずに実行を続けます。ただし,手法1が連続して使用される場面では,「手法1のみ」の設定の場合を除き,「実行」ボタンでも逐一停止しません。 各マスの,黒く消されていない小さい数字は,その時点でそのマスに入る可能性が残されている数字を表します。 パズル面下のボタンで,表示速度を変更できます。 試行錯誤モードソルバーにおいて, 試行錯誤により1つ可能性が消せた場合,1歩前進したことになるので,絞り込まれた可能性をもとにそこからあらためて ここでは,どの数字を仮定して試行錯誤を行うかを,手動で選択します。パズル面上の小さい数字をクリックして選択してください。 仮定をした上で解き進めている際に,矛盾なく全てのマスが埋まった場合,「正解の1つを発見した」ものとし,仮定なしで正解にたどり着きそれが唯一解であることが確認されない限り試行錯誤モードは継続します。ただし,異なる2つの解を発見した場合は,唯一解でないことが確定するので,その時点で終了します。 各手法について手法4までの詳細は本編記事で確認して下さい。 手法1同じ行・列・ブロックの他のマスで既に確定している数字は入らないことから,そのマスに入る可能性のある数字を絞り込む手法。 ここでは,各マスから周囲の確定したマスを見るのではなく,数字の確定したマスから見て,その影響する範囲における可能性を消す処理を行っています。 手法2各数字に着目し,ある行・列・ブロック内でその数字が入る可能性のあるマスが1つしかない場合,そこに必ず入る,という手法。 手法3ブロックと行,ないし,ブロックと列が交差する3マスずつに着目し,ある3マスに必ず入ることがわかれば,その3マスが含まれるグループの他の6マスには入らないことがわかる,という手法。 手法4同じ行(または列・ブロック)に属するnマスに入る可能性のある数字がn種類だけの場合,そのn種類はその行(または列・ブロック)の他のマスには入らない,という手法。 手法5あるn本の行に含まれるマス全体の集合をAとし,ある数字kに着目してAの中でkが入る可能性の残されているマスの集合をXとするとき,Xが,あるn本の列に含まれるマス全体の集合Bに含まれるならば,Bの中でX以外の箇所にkが入る可能性は除外できる,という手法。(参考:「稲葉直貴の難問ナンプレに挑戦」世界文化社) 問題例についていずれも唯一解のある問題です。 例1は,手法5まで使って初めて答えにたどり着く問題です。 例2は,2010年に「世界一難しい数独」として話題になった,フィンランドの数学者Arto Inkala氏が作成した問題です。これは,試行錯誤モードだけでも解けません。以下,本ツールを使って唯一解を探す方法を紹介します。 まず試行錯誤モードまで使って極力可能性を減らします。その時点で,例えば左上隅のマスに着目すると,まだ「1・6・9」の3つの数字に入る可能性が残されています。そこで,問題入力画面に戻り,左上隅のマスに最初から「1・6・9」のどれかを入れた問題としてあらためて解いて見ると,それぞれ試行錯誤モードまで行ったところで,そのうち2つについては矛盾が見つかり,1つのみが正解にたどり着きます。実際には左上隅に1を入れた問題が試行錯誤モードまでで解けるので,これが唯一解となります。(この左上隅に1を入れた問題も,かなり試行錯誤を繰り返さないと正解にたどり着かない難問です。) 例3は,本編記事で例として取り上げた問題で,手法5まで使っても解けませんが,「試行錯誤」により解ける例となっています。 |