使い方のメモ
- 戻るは目次に戻るの意
改訂記録
- 2023-01-14 初稿
- 2023-01-16 「隠れ三国同盟」追加
勃勃たる威風へ
はじめにこのような記事をまとめるに思い至った経緯について記します。
日本の経済力は長い間、横ばい傾向にありました。かなり前から後発国の追い上げが急迫しており相対的な地盤沈下に陥っています。
先発国の良いところを見習ってさらなる改良を加えて一時は頂上を極めましたが、『追いつき追い越せ』策はもう限界です。
太平洋戦争の敗戦を受け、そのころ世界一など望むべくもなくアジアで一番を目指していました。プロボクシングで「東洋フライ級チャンピオン」が生まれて日本国中おおさわぎになったことをかすかに覚えています。
そして時代が下ってアジアで一番など話題にする人がいなくなるほどたくさんの世界一が誕生しました。1949年には湯川秀樹さんが日本人として初めてノーベル賞を受賞しましたが、ここにきて『元の木阿弥』現象が起きつつあります。
国内で開かれる世界的なスポーツ大会で日本人が優勝することが少なくなり「日本人トップ」という言葉が使われることが多くなりました。残念なことです。
明治以来、連綿と続けてきた国策は行き詰っています。ここらで他人・他国を後追いすることはやめて自ら新しいことに挑戦してみませんか。
当ブログは完成品をすぐ提示するというより完成品を作り上げるための手法について語ってきました。ウサギ年はもっと閲覧者が増えるよう頑張りたいと考えていますので応援いただけたらありがたいです。
活気ある日本へ
日本は一時はトップに立ってもそれを維持するところは苦手の様です。さらなる改革を継続できず現状に安住しているかのようです。ぜひ予算を新しい分野に投じて欲しいものです。
また、新しいことをする人々を評価し元気づけてください。当方も物価が高騰する折り、ブログ維持もままならなくなりつつあります。
論理的なものの考えを養うのにプログラミング教育が重要視されています。長い間、ソフトウェア開発に携わってきました。プログラミングがそれに役立てばと思い、数年前からブログで取り上げてきました。今回は、『ナンバープレース』を取り上げます。
AIでナンプレ難問を解く
前項でブログの目的を述べました。新聞や雑誌で取り上げている『ナンプレ懸賞問題』をAIにより解いて景品をせしめることに加担するつもりはありません。
それらのサイトは数多くあり、この記事をまとめるに当たり参照させていただきました。それらのサイトからプログラミングに重きをおいたサイトが当ブログと言えます。
これから述べること（実装、未実装など）は当サイトの話であり、全体に通用することではありません。
誌面サイズの制限からナンプレの基本的なルールやプログラミングの初歩の初歩については別誌を紐解いてください。
本記事の目的
改めて明言すれば本記事は単にナンプレの正答を得るために用意されたものではありません。ナンバープレースの課題を解いて、解法を研究することによって脳を活性化させ、脳トレーニングの一環としてプログラミング学習をしながら論理的な考えを育むために記述されています。
社会生活をする上で他人にわかりやすく物事を説明することが要求されます。それには日頃から脳を刺激し鍛錬することが大切です。
脳の内部細胞を磨くことによって頭の切れが良くなります。楽しみながらナンプレに挑戦してみましょう。
自動解法を説いた記事には難解な課題を難なく解いているものが山ほどありますが、解けない課題も存在します。このようなときに当記事からエッセンスを抜き出し発展させ、自分なりのシステムを構築して難問に挑戦することができます。
操作方法
ここにはナンバープレースをよりよく楽しむための情報を詰め込みました。論より証拠、へ理屈よりも実益を尊重してナンプレの解を得ることを第一義にし課題画面からこの画面に到達しました。
冒頭の記述内容のタイトルには内部リンクが貼られています。注目する項目にいきなりジャンプする際に利用してください。
本文から細部に飛んで内容を確認し元に戻れる仕組みは電子媒体の独壇場です。
ナンバープレース解法アルゴリズム
多くの研究者によって発表された「ナンバープレースを解くアルゴリズム」を以下に掲げます。
新聞・雑誌等に掲載されている課題の多くは背景がアジュール（明るく鮮やかな青）色に彩られた組み込み済み解法で正解が得られますが、難解な問題を解くには未実装の解法を織り込まなければなりません。
ナンプレをこれから極めたい、フェルマーの定理解明に力を注いだ先人のような気骨のある方のために、多くは未実装のまま残しています。当サイトは実のところ体力不足やら何やらで手が回らなくなっています。
| 名称 | 略称 | 概要 |
|---|---|---|
| ➊シングル | Singles | シングルとは、「候補が１つしかないマスには、その数字を確定する」 |
| ❷隠れたシングル | HiddenSingles | 隠れたシングルとは、「特定の行、列、Boxで候補が１つしかない数字は、その数字を確定できる」 |
| ❸二国同盟 | NakedPairs | 二国同盟とは、「2つのマスに限定された2つの候補があるとき、その同一グループの他のマスにあるその候補は削除できる」 |
| ❹隠れ二国同盟 | HiddenPairs | 隠れ二国同盟とは、「2つのマスに限定された2つの候補が他の候補と同居する時、そのマスの他の候補を削除できる」 |
| ❺ポインティングペア１ | PointingPairs1 | ポインティングペア1とは、「ブロック(3×3の9マス)で限定された候補によって、行または列の候補が消去できる」 |
| ❻ポインティングペア２ | PointingPairs2 | ポインティングペア2とは、「行または列で限定された候補によって、ブロック(3×3の9マス)の候補が消去できる」 |
| ❼三国同盟 | 未実装 | ここを含めて以下の解法は未実装、次項の参考資料により適宜、組み込み可 |
| ❽隠れ三国同盟 | ||
| ❾四国同盟 | ||
| ➓隠れ四国同盟 | ||
| ⓫Xウィング | ||
| ⓬スカイスクレイパー | ||
| ⓭2ストリングカイト | ||
| ⓮Yウィング | ||
| ⓯ソードフィッシュ | ||
| ⓰XYZウィング | ||
| ⓱リモート ペア | ||
| ⓲シンプル チェーン | ||
| ⓳BUG | ||
| ⓴XYチェーン | ||
| ㉑ジェリーフィッシュ | ||
| ㉒WXYZウィング | ||
| ㉓フィンド/サシミ Xウィング | ||
| ㉔フィンド/サシミ ソードフィッシュ | ||
| ㉕—続く | もっと存在しているが今回は終了 |
プログラミング言語について
問題解決への手順をコンピュータへ命令として記述したものをプログラムと言い、その形式をコンピュータプログラミング言語と呼びます。
たくさんの民族言語があるように数多くのプログラミング言語があります。以前はCやPHPなどで記述していましたが、最近ではインターネットの普及でHTML（プラスCss, JavaScript）を採用することが多くなっています。
多くの中からよく利用されている言語10個を以下に挙げます。モダーンブラウザが動作すればパソコン、スマホ、タブレットなどデバイスに依存することなく動作するHTMLは魅力的で有望な言語です。
| 言語 | おもな利用分野 |
|---|---|
| ➊C言語 | 業務システム／組み込みシステム |
| ❷C++ | 業務システム／組み込みシステム／ゲーム |
| ❸Java | Webアプリ／業務システム／組み込みシステム／スマホアプリ |
| ❹C# | パソコンアプリ／ゲーム |
| ❺HTML(JavaScript, CSS) | Webアプリ／ゲーム |
| ❻PHP | Webアプリ |
| ❼Ruby | Webアプリ |
| ❽TypeScript | Webアプリ |
| ❾Python | Webアプリ／人工知能 |
| ➓R言語 | 人工知能 |
新しい解法の実装法
それなりに複雑で重厚な新しいソフトウェアを作る時、ビルディングブロック構造に配慮すると後々の品質向上やメンテナウンスに貢献します。
ナンプレの解法数がいくつになるか前もって確定することは困難です。不確定要素が含まれる場合は制御関数名や制御情報をテーブルに登録し、制御処理でそのテーブルを参照するように計らいます。
一方、解法が追加されてもテーブルを改訂して制御処理には変更を加えないようにします。
制御の流れを右図のようにすることによって機能の追加・削除が発生しても制御本体への変更がなくなります。
幸い、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つのマスからあるいは他のマスから候補を削除する解法です。実装するには同盟成立条件を見定め成立した場合、該当マスから適切に候補を削除する処理を織り込みます。
具体的に、三国同盟では同一グループ（行・列・ブロック）の他のマスから成立した数字を削除することであり、隠れ三国同盟では成立したマスの中に同居している他の数字を削除する処理です。
参考資料
ナンバープレースを解析するにあたって参照したサイトを以下に挙げます。概要の枠内をクリックして目当てのサイトに進むことができますが「接続が拒否されました」が出力された場合、直リンクが禁止されており概要検索でサイトにジャンプします。
| 概要とURL-ADDRESS | 適用 |
|---|---|
| 一般に使われている解法を解説 | |
| 複数解についての所見 | |
| ブロックと行の情報から、候補を一つに絞るナンプレ（数独）のコツ | |
| 代表的な解法の解説とサンプル | |
| 数独を解くための14種類のテクニックを解説 | |
| 候補数の消し方と成立条件 | |
| ナンプレを楽しむ上で強力な解析ツールになる | |
| ルールの確認と様々な解法の解説 | |
| 数独の解き方【初級編】に続く第2弾 | |
| ルールの再確認と解き方の概略 | |
| レベル別数独の解き方のコツ | |
| 数独を解くテクニックから数独リベンジへ | |
| 数独自動解法プログラム、場面ごとに解法を示しているところは秀逸 | |
| コンピューターによる数独自動解法 | |
| 再び「京」、未実装解法のアルゴリズム作成に役立ち、プログラミングへの第一歩 | |
| 「世界一難しい問題(2012)も解けます」と語っている | |
| ナンプレ解法プログラム | |
| XY-WINGを解説 |
あとがき
雑誌・新聞にはナンプレ問題が毎日のように掲載されています。加えてネット上にはナンプレに関する解説記事が山積されています。
当サイトでは後追いを避け、それらとの棲み分けを目指し自らHTMLを駆使してプログラミングを主題にしてきました。
情報の公開、共有化が進み世界の至る所で斬新な取り組みが始まっています。日本の若者がその先陣に立って活躍することを期待しています。
今回のナンプレ記事は研究の始まりに過ぎません。老骨を奮い立たせてサポートする解法は少なくも2桁を実装したいと考え頑張ります。
謝辞
これまで単行本、新聞、週刊誌や多くのサイトで先達のナンプレへの熱い思いを参考にさせていただきました。深く感謝申し上げます。感想、ご意見などはブログのコメントをお使いください。記事に関すること以外公開されることはありません。
2023年1月、著者 滝口 政光