じゃばのひまつぶし:ExcelVBAによる競馬ソフト自作教室とJRA-VAN登録ソフト(おずたんシリーズ)のサポートサイトです。
タラレバ倶楽部ページ<Excel VBAであれこれ作ろう>
<番外編:ナンプレ解析ソフトの作り方>
ソフトの概要
 
NumberPlace_1

(更新:2016-02-22)


本ページを閉じる場合は右上のクローズボタン[×]で閉じてください。

<注:このページは競馬ソフトとは関係ありません>

競馬ソフトの作成がはかどらず、気分転換にナンバーブレース(ナンプレ)の自動解析ソフトを作ってみました。
日本では「数独」がニコリ社の名称登録のためかナンバープレース(ナンプレ)と呼ばれることが多いですね。

ナンプレ解析ソフトはVectorなどにも沢山ありますが、本ソフトの解析スピードは速くありません(遅い)。
また解析方法も力ずくでごり押しするものでスマートなアルゴリズムではありません。
解析次々にが行き詰って最初からやリ直すのを繰り返し、ひょっとして完成しないかもというスリルを味わいながら、
最後に完成する様子をボケーと見ているのも面白いと自己満足しています。

EcelVBAで作ったプログラムをダウンロードできます。どんな感じで動くのかを記録した動画もあります。
ご興味のある方は使ってみてください。プログラムソースを公開しています。
また解析速度をアップするヒントも追記していますので、改良してみてください。
マクロのソース(コード)の概略を説明しています。グルーバル変数の意味とか
標準モジュールとは何かなどの基本的なVBAの説明は省略しています。

なお、本ソフトの使用によりいかなるトラブルに遭遇しても一切責任は負いません。
改変は自由ですが、無断商用利用はしないでください(ないと思いますが)。
このソフトの開発のきっかけ

数年前に高齢者仲間がやっていたナンプレを見て、おもしろそうだなと思い、私もやってみましたが、すぐに鉛筆でやるのが面倒になり、仲間からもらった「数独の科学」という資料を見て、これはプログラミング向きだなと思いました。
原型は数日でできましたが、仲間に知らせると「自分の頭でやらないと脳トレにならん」と言われそのまま数年・・・

最近また別の高齢者仲間がナンプレにはまっていると聞き、思い出して引っ張り出してきました。フィンランド人数学者(アルト・インカラ博士)の作った「世界一難しい数独」をやってみたら解けませんでした。ちょうど開発中の競馬ソフトがはかどっていなかったので、気分転換にと改良しました。その結果、博士の数独の問題2つの内1つは解けましたが、もう1つさらに難しい問題は解けませんでした。どうも解析にもっと工夫がいるなと思いましたが、仮定した数字を最低2つ入れたら解けることが分かったのでやめました。

本来の競馬ソフトに戻るためにこのプログラムの内容を公開することにしました。自己流プログラミングなのでスマートではありませんが、興味のある方に読んでいただければ幸いです。
本ソフトの開発環境
(1)Excel 2016。2010以降なら動作すると思います(2007は未確認)。
(2)OS:Windows10。Wndows7でもOKと思います。
(3)CPU:AMD Ryzen5、主メモリ8GB、HDD1TB(7200ppm)

ソフト及び動画のダウンロード

ソフト名:NumberPlaceSolver(約1MB)
動画名:NumPla_Video(24.6MB)/NumPla_Video圧縮(6.66MB)
参考にした資料やサイト(主なもの)
(1)"The Science behind Sudoku" https://www.cs.utexas.edu/~kuipers/readings/Sudoku-sciam-06.pdf
 私が仲間からもらったのは「数独の科学」という日本語訳のもの。上記サイトに最初の数値が17個、16個のサンプルがあります。

(2)「ダイソーナンプレブックシリーズ」(第1巻〜12巻)(数年前のもので今では新しいシリーズがあるようです)
 本ソフトはこのシリーズを念頭に作り、解説用にいくつか問題例を使用させてもらいました。

(3)「世界一難しい数独の紹介」 http://xn--pdf-j54ei15ebha115e5idf35iogd.com/wadai_sekaiichi.html
 この中にフィンランド人数学者(アルト・インカラ博士)が作った問題と東大・渡辺教授が作った問題2つがあります。

(4)フィンランド人数学者が作った「世界一難しい数独」(Rocket News24):https://rocketnews24.com/2012/07/03/22654/
 上記の博士が作った超難問があります。私のソフトではヒントなしではこの問題だけが自動解析できませんでした。

(5)ニコリ社「難問数独傑作選」(本体900円) 厳選された112問。まだ30問位しか試してませんが、すべて解けました。
 50問まで解けました(2019-05-15)。

本ソフトで上記サイトや書籍の問題をすべて解いた訳ではありませんが、(4)の問題以外はすべて解けました。
(4)は可能性のある数字を2つ仮定して当てはめて解けました。

数独の論文(下記はたまたま見かけたもので本ソフトの参考にしていませんが、改良には参考になるかも)
(1)「数独の数理モデル」(解き筋) 東京農大・是川氏ほかfile:///D:/MyDownloads/%E6%95%B0%E7%8B%AC/%E6%95%B0%E7%8B%AC%E8%AB%96%E6%96%87/IPSJ-WPRO2010009.pdf

(2)「数独パズルの難易度判定」大阪工業大学・土出氏ほか
file:///D:/MyDownloads/%E6%95%B0%E7%8B%AC/%E6%95%B0%E7%8B%AC%E8%AB%96%E6%96%87/1105_sudoku.pdf

プログラミングの参考サイト
「もりさんのプログラミング日記」 https://www.excel-prog.com/entry/2018/04/24/122207
私よりもずっとスマートなプログラミングです。ただダイソーのレベル1、2程度までの問題は解けますが、難易度の高い問題を解くには工夫が要りますが、考え方は参考になると思います。

サンプルとして引用させていただいたナンプレ問題
(1)レベル1〜7はすべてダイソーナンプレシリーズ(第1〜12巻)の問題です。各2問ずつ、1つは解答例あり、1つは問題のみです。いずれも本ソフトで解析できます。

(2)ニコリ社のサンプル(「難問数独 傑作選」の112問から1問)引用させてもらいました。30問位確認しましたが、すべて本ソフトで解析できました。

(3)"Sample"シートのサンプルは、「数独の科学」や上記参考サイトの問題例です。フィンランドのインカラ博士の作った世界一の難問2つの内1つだけ解けませんでした(仮数字を2つ入れれば解けます)。それと日本経済新聞の土曜日版に掲載されている問題を引用させてもらいました。いずれも本ソフトで解析できました。
本ソフトの完成版の初期画面は右図のような感じです。
(クリックすると拡大画面が表示されます)

本解説でのナンプレ表の各部分の呼び方
ナンプレ表あるいはエリア・・・9x9マスの表全体
「ブロック」・・・3X3マスの部分をブロックと呼び、左上から右下へ図のように1〜9番をつけます。
「行」・・・横方向のマス全体。
「列」・・・縦方向のマス全体。
「セル・・・各マス目

「行」候補数値表・・・その行に入る候補の数値列と個数を表示
「列」候補数値表・・・その列に入る候補の数値列と個数を表示
「ブロック候補数値表」・・・各ブロックに入る候補の数値列と個数を表示。
「空き数表」・・・残数があるブロック・行・列の数を表示。完成すると一番上の残数ゼロに「9・9・9」と入る。
「出現回数表」・・・各ブロックで入りうる数値の出現回数を表示。数字が1の場合はそのブロックでそこしか入らない数値があることを示し、黄色表示にする。
「ブロック組合せ表」・・・ブロックごとの候補数値の組合せを表示、少ない順に解析する。
「別表」・・・ナンプレ表の空白セルのコメントを展開(参考のみ)
「メモ欄」・・・解析途中の状態を表示。
初期画面
解析途中の画面例

サンプルはダイソーナンプレブックシリーズの第6巻、No79(レベル4)を使いました。最初の数値(初期値)は24個。

本ソフトでは、ナンプレ表の解析結果のみを表示するのではなく、ステップごとに進行していく状態を周辺の表に展開していきますので速度が遅くなりますが、次々に変わる状況や、手間取っているブロックなどの状況を目で追うことができます。
解析途中の画面例
解析結果の保存

"Top"シートのナンプレ表の内部をダブルクリックすると表と解析経過のメモ、ブロック組合せ表を別シートにコピー(保存)します。
(コピー先のシート名は[Level]を記入すると各レベルシートに、記入なければ"Sample"シート)

各シートにコピーしたナンプレ表をダブルクリックすると"Top"シートに転記できます。
保存シートの例
ナンプレ解析の考え方
ナンプレ表は同じブロック・行・列で1〜9までの数字が1か所しか当てはまる数字のないマス目を探していきます。当てはまる数字がなくなったら、空白に当てはまる数字の少ないブロックを基準に総当たりで(バックトラッキング法と言われる方法?)力ずくで数字を当てはめていき、行き詰ったら別のブロックを基準に同じことを繰り返す方法で行います。
ナンプレ表の解き方として、X-Wingとかソードフィッシュとかの解き方がありますが、本ソフトでは適用していません。

解析手順
(1)各ブロックで1か所しか入らない数値を探し、そこを埋める(代入)。この場合は青字で表示します。

(2)各ブロック内で複数のマス目(セル)に入りうる候補数値の中で1か所にだけ入りうる数値を探して埋める。この場合は赤字で表示。

(3)1か所しか入らない数値がなくなるまで上記の(1)(2)を繰り返す。
青字・赤字の個数が多いほど一般的には解析が楽で、ダイソーナンプレシリーズのレベル1、2はここまでの手順で解ける問題が多いようです。

(4)候補数値が1つも探せなくなったら、各ブロックの残りの候補数値の組合せを全ブロックすべて計算し、組合せ数の少ないブロックを順番に解析する。

(5)解析は対象ブロックの空白セルに組合せ数値をあてはめ、他のブロックの空白も順次数値を当てはめて手順(1)〜(4)を繰り返す。この場合は緑字で表示。

(6)そのブロックの組合せ数がすべて失敗なら、別のブロックに移り、上記手順を繰り返す。

(7)全ブロックが矛盾なく埋まるとナンプレ表の欄外の各ブロック・各行・各列の候補数値表がすべて緑色になり「完成」です。

(8)全ブロックの候補数値の組合せを解析しても完成しない場合、あるいは所定の回数(デフォルト1万回)を超えても完成しない場合は失敗として表示します。

青字・赤字のセルは確定と考えるので、手順(4)以降でも消すことはありませんが、緑字のセルは候補数値の組合せで変わるので、適用する数値やブロックが変わるごとに消して書き換えます。
本ソフトの目標
(1)初期入力は手入力で行うが、解析は「自動」で最後まで行うソフトにする。

(2)完成したナンプレ表の問題はレベルごとに別シートに保存し、いつでも再実行できるようにする。

(3)次の一手を見つけるために解析をステップごとに行う「半自動解析」機能も付ける。
本ソフトのワークシート構成
ワークシートは12枚あります。
(1)"Top"シート・・・このソフトの操作を行う一番重要なシート。
「全表示クリア」「自動解析開始」「例題を初期に戻す」「半自動解析」「表示速度標準」のボタンがあります。

(2)”説明”シート・・・前述の解析途中の画面例です。

(3)"Special"シート・・・通常の解析で単純に当てはまる数値が見つからなくなった時にブロックごとの数値の組合せを展開します。

(4)"Level1-7"シート・・・ダイソーナンプレシリーズの本の難易度(1-7)を想定した区分けシート。解析結果を各レベルのシートにコピー(保存)し、後で再度実行することができます。

(5)"Sample"シート・・・特にレベルの不明な問題を保存するシート。
"Top"シートのボタン

"Top"シートの「表示速度標準」ボタンはクリックするたびに「表示速度中速」→「表示速度高速」→「表示速度標準」と切り替わります。
(説明は後述)

"Special"シートの「空白8個まで(デフォルト)」ボタンはクリックすると「空白9個も対象」と変わります。
(説明は後述)
本ソフトのモジュール構成
標準モジュールとして追加したものは右図の通りです。

標準モジュール
(1)Auto・・・自動解析マクロ
(2)Auto_Module・・・自動解析マクロの関連マクロ
(3)SemiAuto・・・半自動解析マクロと関連マクロ
(4)Special_Module・・・ブロック組合せ表関連マクロ
(5)UTL・・・共通マクロ
(6)WorksheetCommon・・・ワークシート共通マクロ
本ソフトの使い方

右図は初期の何も数値が入力されていない状態です(すでに前の数字が残っている場合は「全表示クリア」ボタンをクリックすれば初期状態になります)。

入力はすべて半角数字で行います。

(1)ナンプレ問題のレベルなどの情報
[Level]・・・ダイソーナンプレシリーズの難易度で言えば1〜7を入力。
[No]・・・ダイソーシリーズの問題番号
[Vol]・・・ダイソーシリーズの巻番号
これらは必ずしも入力しなくても構いませんが、結果の保存や後で再実行する際に手がかりになります。

(2)ナンプレ表に初期の数字を手入力します。
重複した数字や1〜9以外の数字があるかなどの入力チェックを行いますが、マス目の位置を間違って入力された場合は検知できません。

「自動解析開始」ボタンをクリックすると解析が始まります。


 Copyright(C):Jaba 2000-