月刊「理系への数学」数学パズルにトドメをさす?! 今月のFlash
第20回
2012年 1月号
裏ルールを探せ! 〜出題者は使ってはいけない〜
数独(ナンバープレイス)を機械的に解いてみる

目的

数独(ナンバープレイス/ナンプレ)を機械的に解く手法を体感し,またペンシルパズルを解く際の「試行錯誤」の正しい意味を理解しましょう。

数独のルール

・9×9のマトリックスの全てのマスに1から9までの数字が1つずつ入るようにします。

・同じ行や同じ列には同じ数字は入りません。

・太線で囲まれた3×3のブロックにも同じ数字は入りません。

操作方法

問題入力

問題のヒントの数字を設定するには,各マス内の小さい数字をクリックします。一度設定した数字を消すには,その数字と同じ小さい数字をもう一度クリックします。

例1〜例3のボタンをクリックすると,問題例をロードできます。問題例をエディットして使用することもできます。

ソルバーモードから入力画面に戻ると,前回解かせた問題からの編集となります。データを消して最初から入力するには,クリアボタンをクリックします。

ソルバー

入力画面から「入力終了」をクリックすると,ソルバーモードとなります。ここでは,手法1〜4のどこまでを使用するかのみを選択し,あとはプログラムが自動的に解くのを眺めるだけです。

「実行」ボタンではステップ毎に停止し,「連続実行」ボタンでは停止せずに実行を続けます。ただし,手法1が連続して使用される場面では,「手法1のみ」の設定の場合を除き,「実行」ボタンでも逐一停止しません。

各マスの,黒く消されていない小さい数字は,その時点でそのマスに入る可能性が残されている数字を表します。

パズル面下のボタンで,表示速度を変更できます。

試行錯誤モード

ソルバーにおいて,手法4まで使用して解けなかった場合のみ,試行錯誤モードとなります。このモードでは,確定していない各マスに残された可能性のうち1つを選んで,その仮定のもと手法4までを用いて解き進め,矛盾が生じたらその仮定を棄却する(各マスの可能性一覧から消す)ということを繰り返して,可能性を絞り込んでいきます。

試行錯誤により1つ可能性が消せた場合,1歩前進したことになるので,絞り込まれた可能性をもとにそこからあらためて手法4までを用いて推論を進めます。

ここでは,どの数字を仮定して試行錯誤を行うかを,手動で選択します。パズル面上の小さい数字をクリックして選択してください。

仮定をした上で解き進めている際に,矛盾なく全てのマスが埋まった場合,「正解の1つを発見した」ものとし,仮定なしで正解にたどり着きそれが唯一解であることが確認されない限り試行錯誤モードは継続します。ただし,異なる2つの解を発見した場合は,唯一解でないことが確定するので,その時点で終了します。

各手法について

詳細は本編記事で確認して下さい。

手法1

同じ行・列・ブロックの他のマスで既に確定している数字は入らないことから,そのマスに入る可能性のある数字を絞り込む手法。

ここでは,各マスから周囲の確定したマスを見るのではなく,数字の確定したマスから見て,その影響する範囲における可能性を消す処理を行っています。

手法2

各数字に着目し,ある行・列・ブロック内でその数字が入る可能性のあるマスが1つしかない場合,そこに必ず入る,という手法。

手法3

ブロックと行,ないし,ブロックと列が交差する3マスずつに着目し,ある3マスに必ず入ることがわかれば,その3マスが含まれるグループの他の6マスには入らないことがわかる,という手法。

手法4

同じ行(または列・ブロック)に属するnマスに入る可能性のある数字がn種類だけの場合,そのn種類はその行(または列・ブロック)の他のマスには入らない,という手法。

問題例について

いずれも唯一解のある問題です。例1は手法3までで答えにたどり着きますが,例2・例3は手法4まで使っても解けないので,「試行錯誤」により解く例としてご利用下さい。

なお,例3は,本編記事で例として取り上げた問題です。