(13) N君ソフト会社に就職内定する

2006年5月15日（月）の卒業研究ゼミで、N君がNTTコミュニケーションシステムズに就職が内定した旨の報告があった。この時期すでに内定をもらっている学生もいたが、そうでない学生は就職活動で飛び回っていて、ゼミは週一回全員顔を合わせて、一週間の研究の進捗状況や活動報告をすることになっていた。

研究室の配属は3年生の初めにあり、3年の後期には卒業研究に必要な演習を行う。私の研究室のゼミでは3年の終わり（実質的には1月末頃）までに各人の卒業研究のテーマとその内容を決め、プレゼンテーションが出来るようにしていた。長年の会社時代の技術面接の経験では、話題は卒業研究テーマぐらいしかないことを知っていたから。

Ｎ君の卒業研究テーマは、私の大学でのメインテーマの「乗り物酔い」に関するものであったが、まだ幾許も進んではいなかった。その日のゼミで、数独ソフトのＶｅｒ４を披露したら皆は「すごい」といってくれた。Ｎ君はソフトの会社にいくから、卒研もソフトに関するものをやりたいというので、数独の問題を解けるようになるようにと話をした。その時、私の頭の中にあるアイディアが思い浮かんでいた。学科名は「生体機械工学科」といい、研究室名は「生体ダイナミクス」であったので、数独ソフトを研究室テーマにふさわしいものにする必要があったのだ。

(12) Ver.4でA サーチの自動化

SUDOKU_Ver4(May2006) では曲がりなりにも Hard の問題がクリック一発で自動的に解けるようになった。同時に問題のインプット方式も少しは改良された。問題入力は transfer_problem のマクロでsheet1の問題番号を入れるセルに入力した問題番号を読み取り、Sheet2に記載した問題をSheet1のA面に移す。Sheet2　にインプットした問題も Hard なものばかり　３２題になっていた。

自動化の方は、新しく auto_search というマクロをつくった。このマクロは ippatsu と　back_to_win を解が得られるまでnumk回繰り返す。ippatsu の中には search_single （BM サーチ）を含んでいるのでそれで行き詰ったときには、Ver.3　で手動でやっていた操作に切り替わる。仮定した数字でまた　search_single を行うが、一回ではうまくいかないので、行き詰ると仮定する前の段階に戻り、新しい仮定した数字で実行する。

Sheet1のA画面にはその様子は逐次表示されるので、どのように解析が進んでいるのかわかり、 Final answer に到達したときには感動的である。numkを10回まわすと打ち切るようにしているが、これは Hard な問題では、空回りをおこすからだ。仮定法ではルートがねずみ算的に増えていくので、うまく数字を仮定すると一発で解けるし、そうでない場合にはすごく複雑なルーチンになる。最終的には５階層つまり３２ルートを正確に自動的に解くのを　Aサーチとしたがこれが完成するのはもっとあとのことであった。

(11) 数独パズル世界を制す

２００６年５月１２日(金)の日記に次のような記載がある。
「文芸春秋６月号に数独パズルのニコリ社の社長鍛冶真起氏の話がのっていた。独は独身の人が楽しむ、single の数字と使ってするパズルだから数独というそうだ。上、中、下という三つのパズルが載っていて、これを正解するためには私の今のソフトに改良を加えなければならない。まだまだ解き方に工夫を凝らさねばならない。」とある。

この記事の中には、解き方の話やそのソフトについては何も書いてなかったが、コンピューターメイドの問題は解き味がハンドメイドのものに劣るようである。数独の作問にもいろいろ苦労があることが伺えた。このあたりが分かれば面白い、それにはまずこの三問が全自動で解けることは先決であると改めて興味をもった。

後になって、使用する解法の種類によって6つのレベルに分類する独自のランク付けを考案したが、この三つの問題（ニコリ数独名品100選の6番（Easy）、30番（Medium）、49番（Hard））は私の分類では、6番はBeginner,30番は Very Easy, 49番は Easy となった。これらはすべて基本サーチ（BLCM)で解くことができる。6番はBサーチだけで、30番はBLCサーチでMサーチは使わないでよい。49番はBLCMのサーチを使う。49番を解いてみると、Lサーチから始まる。出だしからして基本サーチとは言え見つけにくいのではないか。49番はLサーチの解説にはよい問題だろう。でも上級者にはEasyな問題なのだろうとこの作者も注記している。

(10) Ver.3 で A サーチの奔り

この時点(２００６年５月８日）でとにかく、どんなに難しい問題でも一回のクリックで Final Answer に到達するアルゴリズムがあるはずで、容易に考えつくのが解を仮定してしらみつぶしに調べていく方法である。数学的には、条件付連立方程式の重複のない整数解を解く問題に帰着できると考えていた。それも簡単なプログラムで。

この探索法は問題を解くという観点からいえば最強の方法である。後に、A search という名付けた方法は、「仮定法」とか「矛盾の常識」として紹介さあれている。

sudoku_Ver3(May 2006) ではその奔りとなるいくつかのマクロを開発した。search_cell_with_two_candidate というのは、候補が二つしかないセルとその値をリストアップするマクロである。back_to_win は行き詰ったとき、前の記録をないものにして仮定前の状態に戻すマクロである。あと known_number, input_added_cell, transfer_A_to_B, transfer_B_to_A とかいろいろある。Sheet 1 のなかで　A画面がもとのめいんの表で仮定するときにはいったんB画面に残しておくのである。

これらのマクロを順次使うことでこれまで解けなかった問題がいくらか解けるようになった。ただ仮定すつセルの数が増えるとものすごく複雑でそれこそ手に負えない。とりあえず、２階層ぐらいの問題を自動的に解けるように sodoku_Ver.4 の開発に取り掛かった。

Hard な問題でいきどまる

２００６年５月８日、数独のむづかしい問題を求めて、インターネットで調べてみた。これまでVer1で試みたのはすべて、読売新聞や文芸春秋にスポット的に掲載されているもので、読者のレベルをかんがえた　Easy　な問題ばかりであった。すると「晴耕数独 on WWW 」というサイトに、Easy, Medium, Hard にレベルわけされた多数の問題集があるのを見つけた。

早速、５題ばかり Hard の問題を取り出し、開発したばかりのVer.2にかけてみた。どれも解けなかった。いたずらに空回りするばかりで、新しい解法が必要なのはあきらかであった。ここで誰もが考えるのはコンピューターの馬鹿力を利用した方法で、西山先生のおっしゃるコンピュータに適した方法というものである。

つまり候補の数字を二つもつセルにおいて、どちらかが正解であるわけだから、そのひとつを仮定して進めるというものである。行き詰るともとに引き返してつぎの仮定の数字を実行する。ひとつのセルだけで Final Answer　にたどりつけばよいが大抵の場合はそうはいかない。これは「矛盾の常識」として知られる解法のひとつであるが、何段階も続くとねずみ算でルートが増えてきて、まさに「コンピューターに適した方法」いうことができる。

問題のインプットに一苦労

数独に限らずコンピュータで計算するときの入力データほど手数がかかるものはない。データが多いほど慎重に間違いの無いようにしなければならない。そのためのデータ入力方法の簡易化や効率化は数独の解法以上に重要とおもっている。

数独の場合、解けない問題や複数解になると入力ミスだとおもってまず間違いない。困るのは解ける場合であるが、これは数字を一箇所入れ忘れた時にしばしばおこる。数独では最終状態（Final answer）に到達するまでの唯一解を与える中間段階以降はすべて数独解なのだから。

Ver1では問題を matrix のelement　として module の中に書き込んだ面倒なものであった。そこで　Ver2では別の Sheet に　９×９ の問題を書き込む場所をいくつか作り、そこに書き込めるようにした。また、それに対応した Final Answer も別の Sheet に残す事に変更した。

数独の基本サーチは４つだけ。

数独の基本的な探索方法は４つだけです。それは　①ブロック、行、列に候補をひとつしか持たない数字をさがす。　②　候補をひとつしか持たないセルを探す。ことです。①が三つでそれぞれ B search, L search, C search と呼ぶことにします。また②は M search となずけました。

四つ合わせて BLCM search とよび、これが基本サーチです。初級問題は大体見落としさえしなければこれで解けます。例えば、「ポケット数独初級編」や「ナンプレ１６０問」（竹書房）は全問解けました。また、「ニコリ数独名品１００選」では７０問が解けます。数独の面白さはこれ以外の中級、上級の探索法を見つけることにあるようです。

私の作った最初のプログラムは B とM　サーチにだけ対応するもので、これでも「ナンプレ１６０問」では１４３問、、「ニコリ数独名品１００選」では５１問を解くことができました。　

sudoku_Ver1(May2006) が完成

２００６年５月６日（土）に記念すべき第１号の数独の解析ソフトが完成した。探索法は search_single というマクロで①ひとつしか数字の候補を持たないセルを探す。（A　判定）　② ブロックの中で一度しか現れない候補の数字を探す。（B判定）　の二つだけの方法を内臓する。それに ippatu という自動化のマクロをつくった。

問題を別に入力しておいて、ippatu を実行すると 全空白セルの候補がひとつになるまで mixy_part を繰り返す。mixy_part では候補を調べてその個数を count_kosuu で数えた後、search_single で候補を確定するという手順を繰り返す。

この程度のソフトで新聞や雑誌に掲載されているやさしい問題は大体解けることがわかった。いま改めて「ポケット数独初級編」（２００６年７月１７日に購入したもの）をA判定とB判定だけで解いてみると１０５問中１０４問が解ける。中でもB判定だけで８３問が解けることがわかった。７１番の一問だけがsearch_single では解けなかった。

この時点では、解き方の体系というか基本が全然わかっていなかったといえる。コンピュターでは解けてもまだ実際に自分で解いたことが無かったからだ。７１番の解けない理由が４つの基本サーチの内のひとつ L-search であると気づくのはもっと後のことで、興味の対象は西山先生も指摘されたコンピューターに適した解法に移っていった。

候補の一覧を作るマクロ

数独のプログラミングの最初は、空白セルに入る可能性のある数字の候補（candidate）の一覧表をつくることだった。いまでは candy_table とよび、洗練されたものになっているが、当初は mixy あるいは mixy_part と名付けたゴテゴテのマクロであった。

mixy のアルゴリズムは数独の表出数（以後 Givens とよぶ）以外の空白セル（Empty cell）を対象として、 check というマクロにて、そのセルと同じ列、同じ行、同じブロックにすでに Givens があるかどうかを順次1から９までチェックするものである。

とりわけ同じブロックにあるかどうかのチェックは checkmate というマクロを別につくり、Ｇｉｖｅｎｓ　があれば flag をたてて戻すようにした。この方法は後に、カラーナンプレとかジグザグナンプレとかに流用する場合このマクロだけを変更すれば容易に達成できた。

mixy_part は　group_search というマクロでブロックを限定して候補の数字を見つけだすものだ。mixy では最後に各空白セルの候補の数をカウントする count_kosuu というマクロがついている。候補の数がひとつだとそのセルの数字（digit と呼ぶ）が特定できる。これがプログラムでは一番簡単にわかる探索法（のちに M-search とよぶ）なのだが、実際には、探しにくいので中級あるいは上級にランクされている探索法である。

　

VBAは数独に適したプログラム環境

ナンバープレースのプログラミングにあたって、マイクロソフト社の Visual Basic for Application を使おう。EXCEL　はいまや最もポピュラーなソフト だし、数独には最も適したアプリケーションといえる。VBEを使えば簡単にプログラミングが可能である。

フォートランからはじまり、ベーシックを長くつかっていたが、ここ15年ばかりはVBAを使っている。容量も速さもパソコンの進化とともに全く不自由することはない状況だ。強いて不便さをあげるとすれば、Excel sheet の列の数の制限（IVまで）ぐらいだろうか。（Excel 2007　以降この制限もなくなった。）

数独のプログラム開発ではExcelの表計算がすごく役に立つ。だから、これから数独の要素の呼び方や利用形式もExcelに準じた名前で呼ぶことにする。例えば、マスはセル（cell）、ヨコ列、タテ列は行と列というように。セルの位置を表す方法をいろいろあるようだが、Matrix演算に準じることにする。つまり i 行目、 j 列目のセルの位置は ( i , j ) であらわす。

初めて数独に出会う。

三年前の連休の頃だった。正確には2006年5月4日に載った読売新聞の数独パズルを家内がやっているのを見かけた。ルールを教えてもらうと簡単にできるように見えた。こんなのはパソコンを使えば簡単に出来るとおもいそのアルゴリズムを考えはじめた。

もともとコンピューターでプログラミングするのが好きだった。これまで作ったいくつかのプログラム手法を思い出し、そのアルゴリズムを考えた。後で知ったことだが、西山豊先生が「数学を楽しむ」という記事を「理系の数学」に連載されていてその中の一章に「数独」について書かれている。先生の感想では「これはコンピューターに適したパズルである」ということだが、私も数独に対する最初の印象は同じものであった。多少でも数学を生業とし、プログラミングを自分では得意だと自負している人はコンピュータの持つ馬鹿正直な愚直さや偉大さを身をもって感じているからだろう。

その日はわずかに空白セルに入る候補をリストアップするマクロ（candy_table）を作成するにとどまった。

数林と呼ぼう。

Number　Place(俗称ナンプレ)はオイラー方陣に由来する。その後魔方陣から派生して、アメリカでNumber　Placeと呼ばれるパズルが誕生した。ニコリ社の鍛冶真起氏がこれに眼をつけ、「数独」と名付けて3年前にブレークした。

イギリスでも SUDOKU の名前で人気が高い。鍛冶氏の説明によれば「数独は独身に限る」というのから名付けたという。この謂れも語呂もあまり私にはなじめない。

私なら数林（スーリン）と呼びたい。語呂の上からスーリンというのなら美しい響きをもつ言葉とおもう。人形劇「三国志」に出てくる劉備の妻の名がたしかスーリン「淑玲」だったとおもう。意味の上からも｢数の林」というのでよろしいのでは？疎らな木を規則的に埋めることにより、美しい数の林にすることは環境上にもよい。

徒然なるままに

作：　松本亙平　

数独AI　アルゴリズム　　　　　　　　　　　　　　　　　



　つれづれなるままに、ひぐらしパソコンに向かい、新型インフルの恐怖におびえ、家の中にとじこもり、思い浮かぶよしなしごとを、あれやこれやとめぐらせて、古きこと新しきこと纏まりなきことかなしけり。



ふと思いつきしことあらば、むかし馴染んだ数独か、はたまたナンバープレースかと古い本をば取り出して、物思いにふけることあわれなり。