皆さん、ナンプレってご存知ですか？
正式にはナンバープレースといい、またの名を数独と言います。
9×9マスの中に、縦、横、ブロック単位で1~9の数字を重ならないようにすべて入れられればクリアとなります。
10年以上前、C言語でこのパズルを解くプログラムを作っていましたが、途中で挫折してプログラムもどこかにいってしまいました。
最近、JavaScriptのプログラミングが面白いので言語を変えてチャレンジしてみました。
よろしければお試しください。
実装したアルゴリズムについても本記事の後半に記載しています。
解ける問題
ダイソーで売っている上級編や名人編、↓の本に載っている問題はすべて解けました。
2つのナンプレが組み合わさったような変則的なものも、下記のようにすることで解くことができました。
- 本ページを2つ開く
- 片方に左のナンプレの問題を、もう片方に右のナンプレの問題を入力
- 左のナンプレをプログラムで解く
- 途中まで解けた結果を右のナンプレに反映
- 右のナンプレをプログラムで解く
- 途中まで解けた結果を左のナンプレに反映
- 3～6を繰り返す
今のところ入力してみた問題はすべて解けていますが、解けない問題があったら申し訳ありません。
ナンプレを解くプログラム
プログラムの使い方
マスに問題を入力し、「問題を解く」ボタンを押すと解答が表示されます。
入力はプルダウンリスト形式です。マスをクリックすると1~9の数字が表示され、選択して入力することができます。
「すべてのマスを消す」を押すとすべてのマスがクリアされます。
プログラム本体
実装したアルゴリズム
①基本
- 各マスごとに候補となる数字を記憶しておく
- 候補となる数字が1個になったらマスの数字を確定する
- 数字が確定したマスの縦 or 横 or ブロックに含まれるマスの候補から確定した数字を消す
- 縦 or 横 or ブロック内に数字Aを候補とするマスが1個しかなければ、そのマスをAに確定する
②各マスの候補を減らす方法1
- n個の数字について、それらの数字が候補になっているマスが縦 or 横 or ブロック内にn個だけの場合、これらのマスにn個以外の数字が入る可能性はないため、このn個のマスの候補からn個の数字以外を消す
例：
縦 or 横 or ブロック内に2,3,4が候補になっているマスと2,3,5が候補になっているマスがあるとします。
他のマスの候補には2と3が含まれていません。
そうなると、これらのマスにしか2,3が入らないので、2,3,4のマス、2,3,5のマスの候補から4と5は消すことができます。
③各マスの候補を減らす方法2
- あるブロックの縦 or 横の2マスまたは3マスでのみ候補になっている数字があったら、それらのマスが含まれる縦 or 横の他のブロックのマスの候補からその数字を消す
④各マスの候補を減らす方法3
- n個以下の同じ数字のみ候補になるマスがn個ある場合、その他のマスにはそれらの数字は入らないので候補から消す
例：
2,3,4のみが候補になっているマスが縦 or 横 or ブロック内に3つある場合、縦 or 横 or ブロックのそれ以外のマスに2,3,4は入らないので候補から消すことができます。
⑤強制的に数字を確定する方法
- 方法④までで解けない場合は、縦 or 横 or ブロック内で2つの数字だけ候補になっているマスを抽出する
- 抽出したマスの中から１つ選び、強制的にどちらかの数字を入れて①～④で解いてみる
- 解けなかったらもう一方の数字を入れて解いてみる
- 両方解けなかったら別のマスを選び、同様に解いてみる
大体の問題は④までの方法で解くことができます。ダイソーの問題の中に⑤がないと解けない問題がありました。
以上、ナンプレを解くプログラムを作ってみたというお話でした～
