三国同盟を実装する

今回はナンプレ解法の続きです。前回まで6つの解法を実装し新聞や週刊誌に掲載されたナンプレ課題を解くことに成功しました。それでは三国同盟解法を実際に実装する例をまとめます。

下、左の課題は前回のAI自動解法システムでは正答に至りませんでした。その右図には初回の候補数を表しています。3X3の4ブロック目で178による三国同盟が起きています。

ナンプレを解くには多くの解法を織り込んで総合力で候補数を1つに絞り確定していきます。AI自動解法で解けない課題が見つかったとき、課題に誤りがなければ自動解法が不十分だからです。どの部分が不足しているかを見極め対策を講じなければなりません。

実装のあらまし

『三国同盟』という解法は、「3つのマスに限定された3つの候補がある時、同一行の他の6マスにあるその候補は削除できる」という決まりです。 下図では行でなくブロックですが具体例で説明します。

178が①⑤⑥の3マスに限定され三国同盟が成立しているので他の6マスに混在している178を削除できます。削除により⑦マスは候補が１つになり4が確定し、⑧マスから4を削除できます。よってこのグループ単独で右図のように暫定決定します。

これからグループ（9マス）の三国同盟成立を判別する具体的な方法を箇条書きに列記します。

1. グループの中で確定マスは除外する
2. 内包数2～3のマスを選ぶ
3. 選択されたマス数>=3が条件
4. 上条件成立も未確定マスが3ならば対象外
5. 最後に選択マス数が3以上でも参照回数が2未満の数が含まれていれば除外
6. 選択されたマスの数字を123…に変換し普遍化する^{※変換方法は下記}
7. 普遍化された比較テーブルを検索して三国同盟成立を判別する
※マスの数字を123…に変換する方法
三国同盟は3つの数字を扱います。数字は1～9あってもすべて1，2，3に置き換えて動静を把握します。ここではこのことを普遍化と呼びます。三国同盟を成立させるためには最低でも二国からスタートすることに着目し数字の出現回数を調べ123…に変換して普遍化された比較テーブルを参照します

改訂されたAI自動解法による実行例

以下、準備中

1. 勃勃たる威風へ
2. 活気ある日本へ
3. AIでナンプレ難問を解く
4. 本記事の目的
5. 操作方法
6. ナンバープレース解法アルゴリズム
7. プログラミング言語について
8. 新しい解法の実装法
9. 解法の大きな流れ
10. プログラミングの基礎となる関連図

勃勃たる威風へ

はじめにこのような記事をまとめるに思い至った経緯について記します。

日本の経済力は長い間、横ばい傾向にありました。かなり前から後発国の追い上げが急迫しており相対的な地盤沈下に陥っています。

先発国の良いところを見習ってさらなる改良を加えて一時は頂上を極めましたが、『追いつき追い越せ』策はもう限界です。

太平洋戦争の敗戦を受け、そのころ世界一など望むべくもなくアジアで一番を目指していました。プロボクシングで「東洋フライ級チャンピオン」が生まれて日本国中おおさわぎになったことをかすかに覚えています。

そして時代が下ってアジアで一番など話題にする人がいなくなるほどたくさんの世界一が誕生しました。1949年には湯川秀樹さんが日本人として初めてノーベル賞を受賞しましたが、ここにきて『元の木阿弥』現象が起きつつあります。

国内で開かれる世界的なスポーツ大会で日本人が優勝することが少なくなり「日本人トップ」という言葉が使われることが多くなりました。残念なことです。

明治以来、連綿と続けてきた国策は行き詰っています。ここらで他人・他国を後追いすることはやめて自ら新しいことに挑戦してみませんか。

当ブログは完成品をすぐ提示するというより完成品を作り上げるための手法について語ってきました。ウサギ年はもっと閲覧者が増えるよう頑張りたいと考えていますので応援いただけたらありがたいです。

活気ある日本へ

日本は一時はトップに立ってもそれを維持するところは苦手の様です。さらなる改革を継続できず現状に安住しているかのようです。ぜひ予算を新しい分野に投じて欲しいものです。

また、新しいことをする人々を評価し元気づけてください。当方も物価が高騰する折り、ブログ維持もままならなくなりつつあります。

論理的なものの考えを養うのにプログラミング教育が重要視されています。長い間、ソフトウェア開発に携わってきました。プログラミングがそれに役立てばと思い、数年前からブログで取り上げてきました。今回は、『ナンバープレース』を取り上げます。

AIでナンプレ難問を解く

前項でブログの目的を述べました。新聞や雑誌で取り上げている『ナンプレ懸賞問題』をAIにより解いて景品をせしめることに加担するつもりはありません。

それらのサイトは数多くあり、この記事をまとめるに当たり参照させていただきました。それらのサイトからプログラミングに重きをおいたサイトが当ブログと言えます。

これから述べること（実装、未実装など）は当サイトの話であり、全体に通用することではありません。

誌面サイズの制限からナンプレの基本的なルールやプログラミングの初歩の初歩については別誌を紐解いてください。

本記事の目的

改めて明言すれば本記事は単にナンプレの正答を得るために用意されたものではありません。ナンバープレースの課題を解いて、解法を研究することによって脳を活性化させ、脳トレーニングの一環としてプログラミング学習をしながら論理的な考えを育むために記述されています。

社会生活をする上で他人にわかりやすく物事を説明することが要求されます。それには日頃から脳を刺激し鍛錬することが大切です。

脳の内部細胞を磨くことによって頭の切れが良くなります。楽しみながらナンプレに挑戦してみましょう。

自動解法を説いた記事には難解な課題を難なく解いているものが山ほどありますが、解けない課題も存在します。このようなときに当記事からエッセンスを抜き出し発展させ、自分なりのシステムを構築して難問に挑戦することができます。

操作方法

ここにはナンバープレースをよりよく楽しむための情報を詰め込みました。論より証拠、へ理屈よりも実益を尊重してナンプレの解を得ることを第一義にし課題画面からこの画面に到達しました。

冒頭の記述内容のタイトルには内部リンクが貼られています。注目する項目にいきなりジャンプする際に利用してください。

本文から細部に飛んで内容を確認し元に戻れる仕組みは電子媒体の独壇場です。

ナンバープレース解法アルゴリズム

多くの研究者によって発表された「ナンバープレースを解くアルゴリズム」を以下に掲げます。

新聞・雑誌等に掲載されている課題の多くは背景がアジュール（明るく鮮やかな青）色に彩られた組み込み済み解法で正解が得られますが、難解な問題を解くには未実装の解法を織り込まなければなりません。

ナンプレをこれから極めたい、フェルマーの定理解明に力を注いだ先人のような気骨のある方のために、多くは未実装のまま残しています。当サイトは実のところ体力不足やら何やらで手が回らなくなっています。

プログラミング言語について

問題解決への手順をコンピュータへ命令として記述したものをプログラムと言い、その形式をコンピュータプログラミング言語と呼びます。

たくさんの民族言語があるように数多くのプログラミング言語があります。以前はCやPHPなどで記述していましたが、最近ではインターネットの普及でHTML（プラスCss, JavaScript）を採用することが多くなっています。

多くの中からよく利用されている言語10個を以下に挙げます。モダーンブラウザが動作すればパソコン、スマホ、タブレットなどデバイスに依存することなく動作するHTMLは魅力的で有望な言語です。

新しい解法の実装法

それなりに複雑で重厚な新しいソフトウェアを作る時、ビルディングブロック構造に配慮すると後々の品質向上やメンテナウンスに貢献します。

ナンプレの解法数がいくつになるか前もって確定することは困難です。不確定要素が含まれる場合は制御関数名や制御情報をテーブルに登録し、制御処理でそのテーブルを参照するように計らいます。

一方、解法が追加されてもテーブルを改訂して制御処理には変更を加えないようにします。

制御の流れを右図のようにすることによって機能の追加・削除が発生しても制御本体への変更がなくなります。

幸い、JavaScriptにはテーブルの項目数を『methodTable.length』のようにlengthで取得できます。lengthプロパティをプログラムコードに採用することによって可変性に富むプログラミングが可能です。

解法の大きな流れ

ナンプレを背理法（仮置き）を除き正解に導く方法は個々のものでもかなりの数になり、それを集合した解き方は数えきれません。

個々については解法アルゴリズムで述べました。今回採用の全解法を絡ませた流れを左の流れ図にまとめました。

黄色の背景色で示した処理ではマスごとに複数の候補から1つに絞るべく用意した全解法を試みます。

この一括りをパス（pass）と呼びます。個々の解法で求め得る最大確定数が決定しましたが、複数の解法で状態が変われば再挑戦してぞくぞく全確定に近づくことが知られています。

そこで全マスが確定するまであるいは課題の出題ミスや未実装を配慮して確定数が0になるまで繰り返します。

プログラミングの基礎となる関連図

81コマを9X9, 3X9, 9個からなるグループとして扱うと考えやすくなります。

JavaScriptではグループを要素に見立て階層構造にして制御します。

行、列、ブロックごとに規則正しいネーミングをするとプログラミング効率が向上します。

右のような図を参考にしてプログラミングするとピッタリでしょう。

小さな数字の1～9および①～⑨は行と列の番号名です。ピンク色の大きな①～⑨はブロック名、緑色で示した0～80は候補数を表示するマスの要素番号です。

番号は説明用に1～9を用いていますが内部のプログラミングでは0～8で制御します。

準備するもの

AIでナンプレ難問を解くに当たり、これを具現化するにはスマホ、タブレット、パソコンなどの電子デバイスの他、開発環境が必要になります。スマホは場所を選ばないので有用です。パソコンは技術を蓄積したり再利用するのに好都合です。実情に合った選択をすればよいでしょう。

開発環境は改めて用意する必要はありません。ウェブデザインに利用するHTMLを採用すれば問題ありません。HTMLを利用する環境は検索ツールである『ブラウザ』に備わっています。

かつてソフトウェアシステムを構築する言語といえばC言語が代表例でしたが、今ではHTML言語を使用することが通例です。何よりも経費が掛からず世界中の多くの人々が開発環境の整備に関わっています。

必要とする関数

ナンバープレースは1から9までの数を扱います。未確定状態を0として扱ったとしても10種類で1桁の値に限られるので扱いやすといえます。

処理系が有する機能を拡張して効果的な関数に仕立て上げます。

文字列検索関数は全体の性能を決めるといっても過言でないほどの重要関数です。

サンプルコードの概要

プログラミング実行例

HTMLで記述した自動解法システムの実行例を以下に3例挙げます。録画するに当たりHTMLによる実行速度を通常の1/10倍速にしています。

再生するとき、全画面サイズにしたり画面を停止して右側に表示されたマス目情報・解析に用いた解き方に注目して候補数字がひとつひとつ減らされて決定するあり様をご確認ください。

①numberPlace0:askew-10.js

『斜め連番配置』に1⑨,3⑥,9①の3マスを追加して難易度を下げた課題

《シングル、隠れたシングルの2解法により未決マス51を解析》

②numberPlace1：exam-0228.js

隠れたシングルと二国同盟にて解ける課題

《57未決マスを隠れシングルと二国同盟の2法にて解決》

③numberPlace2：mysteriousLayout-5.js

ミステリアス配置2, 配置1の課題と回答を逆にした

《42未決マスをシングルのみで解く、123456789斜めに並ぶ》

行き詰ったときの突破法

当ソフトウェアは発展途上にあり6解法を実装しているに過ぎません。この現象は予期したことです。この場合の対処方法を示します。

ネット上には多くの先人の遺産があります。

例えば⑦ナンプレ京や⑬数独自動解法プログラムは数々の難問を解くほど充実していてその上、多くの候補数をどの解法を用いて最終数に絞ったかを明示してくれる優れモノです。その解法が当ソフトで未サポートでならば先人が作ったツールを用いてどの解法で正答に至ったかを調べるのは当然の帰結と理解できるでしょう。

あとは闘志を燃やして未サポート解法のアルゴリズムをじっくり理解してプログラミングし実装という運びに至ります。

三国同盟を組み込む

前項の方法により行き詰ったときの脱し方がお分かりいただけたことでしょう。難易度が高くなると6つの解法だけでは正答を導くことはできません。

プログラミングに精通すると、宮本武蔵が剣の達人から教えを乞うために武者修行に出て全国を行脚したように、高度な技術に接したくなるのが世の常です。

『三国同盟』という解法は、「3つのマスに限定された3つの候補がある時、同一の行(または列,Box)の他のマスにあるその候補は削除できる」というものです。いずれの解法にも言えることですが、一つの解法ですべて解決に導くことはできません。候補数を少なくして確定していきます。

さっそく、三国同盟の組み込み方に取り掛かります。

隠れ三国同盟を組み込む

『隠れ三国同盟』という解法は、「3つのマスに限定された3つの候補が他の候補と同居する(隠れ3国同盟)時、そのマスの他の候補を削除できる」というものです。

三国同盟も含めて下図にしました。ある行の背景色が黄色に彩られたマスにおいて三国同盟、隠れ三国同盟が成立しています。9マスをひとくくりにした列・ブロックでも同様のことが言えます。

三国同盟、隠れ三国同盟とも3つのマスにおける同盟成立を見極め3つのマスからあるいは他のマスから候補を削除する解法です。実装するには同盟成立条件を見定め成立した場合、該当マスから適切に候補を削除する処理を織り込みます。

具体的に、三国同盟では同一グループ（行・列・ブロック）の他のマスから成立した数字を削除することであり、隠れ三国同盟では成立したマスの中に同居している他の数字を削除する処理です。

参考資料

ナンバープレースを解析するにあたって参照したサイトを以下に挙げます。概要の枠内をクリックして目当てのサイトに進むことができますが「接続が拒否されました」が出力された場合、直リンクが禁止されており概要検索でサイトにジャンプします。

あとがき

雑誌・新聞にはナンプレ問題が毎日のように掲載されています。加えてネット上にはナンプレに関する解説記事が山積されています。

当サイトでは後追いを避け、それらとの棲み分けを目指し自らHTMLを駆使してプログラミングを主題にしてきました。

情報の公開、共有化が進み世界の至る所で斬新な取り組みが始まっています。日本の若者がその先陣に立って活躍することを期待しています。

今回のナンプレ記事は研究の始まりに過ぎません。老骨を奮い立たせてサポートする解法は少なくも2桁を実装したいと考え頑張ります。

謝辞

これまで単行本、新聞、週刊誌や多くのサイトで先達のナンプレへの熱い思いを参考にさせていただきました。深く感謝申し上げます。感想、ご意見などはブログのコメントをお使いください。記事に関すること以外公開されることはありません。

2023年1月、著者 滝口 政光