Beyond the White Line

前回の記事ではどんなに難しい数独問題でも瞬時に解いてしまう味気の無いプログラムを公開した．
そうしたら，よっし〜さんから「コレを使ってしまっては頭の体操にならないのでは？」というコメントを頂いた．
確かにそうだ．あのプログラムを作成するにあたって私はとっても頭の体操になったが，数独ファンにとっては何の役にも立たないシロモノだ．

ところで，ゴルフをカジっている方なら必ずご存知の「尾崎将司プロ」と「チャールズ・ヒュー・アリソン」．
ジャンボ尾崎プロは文句無く日本が生んだ最強のゴルフプレイヤー，アリソン氏は日本では廣野ゴルフ倶楽部をはじめ幾つもの名コースを設計して「アリソンバンカー」という名前も残す著名なゴルフ場設計家．
どちらが凄いか？とは比べることが出来ないが，アリソン氏が設計したコースに尾崎プロが挑むという構図を鑑みるに，私も分野は違えど設計者の端くれなのでアリソン氏に共感を覚える．

っということで，今回は数独に関してもアリソン氏を目指す．
即ち，『数独の問題を自動的に作成する』ことを目指す．

問題を作成するにあたって数独問題の要件を整理するとこんな感じ．

1. 81個のマス目のうち幾つかのマス目が埋まっている形になる
2. どんな方法で解いても同じ答えに帰着する

この要件を満たす問題を作成するのに，前回の記事で書いたコードを流用する．
概要は下記．

• 予め幾つ数字が埋まった問題を作成するか決めておく．
• 適当な問題を解く．
• 乱数を用いて解いた問題からどのマス目を問題にするか決める．
• 作成した問題を違う手法で解く．
• ２種類の解答が同じだったら終了
• 異なったら適当な問題を解くトコからやり直し

数独連載第一回でボツになった確率的手法を再度採用することになるが，予め決める数字を小さくしすぎなければ恐らく大丈夫だろう．
違う方法で問題を解く必要があるが，ロープの例えだと各段で「9」のラベルが付いたロープから手繰り寄せるようにすればお手軽に実装できる．
方針が決まったので早速コーディング．
前回の記事を作成する際にある程度Javascriptのお作法に慣れたので教科書とニラメッコの時間は結構減ったが思いのほか時間が掛かった．

さて，問題作成フォームは以下．「作成」ボタン左のフォームに数字を入れてボタンを押してください．

数字の数：

コレで「いちはちじゅうのもくもく」では無いが，「81マスに向かって黙々と解く」環境が出来上がった．
毎日100個ずつでも問題を作成することが出来る．
とは言え，javascriptで作成したデモ環境なので以下の使用制約がある．
・数字が埋まる数を「34」以上に制限してある．
・ブラウザの機能によって途中で解析を中断せざるを得ない場合がある．
どちらもjavascriptで書いた故の性能制約なので仕方が無い．
他の実装方法ならばこの制約を気にせず膨大な問題を作成できる．
あと，IEではなくFirefoxで動作させると探索の過程が解かりやすい．IEだと過程の値は表示せず，処理結果しか表示しないようだ．

ここまで出来れば問題本の作成くらいチョチョイのチョイだが，ひとつだけ観点が抜けている．それは『問題の難易度』の観点だ．
これまで計算機にしか出来ない乱暴な方法ばかり採用してきたツケが出てきてしまった．
難易度を判定するには人間の思考過程を模した方法，即ちgodgeoさんのインテリジェントアプローチを経なければならない．
このアプローチを実装するにはデータ構造から処理の方法までイッサイガッサイ再検討が必要だ．ヒラリンと軽く簡単には作れない．
っということで，私の数独検討はコレにて終了．
知的アプローチはgodgeoさんにお任せしようと思う．

---

後記：

４回に渡って数独に関する記事を書きましたが，今までで最高の熱中度でした．そして読者の方々にはどう映ったかは解かりませんが書き終わって最高の達成感です．
どの位熱中したかというと，会社では毎日ランチタイムにプログラミングして通勤電車内ではコードのプリントアウトを眺めて車中デバグ，家に帰ってはA子との会話はナマ返事にとどめて再びプログラミング，更に記事の付け合せ的なネタを考えてはインターネットの世界を駆け巡り書いては消しの繰り返し，という感じでした．
元々私は熱しやすい性格ですが，火をつけて下さったのは勿論godgeoさん．何をおいても感謝申し上げたい．
また記事に使ったコードも多くはgodgeoさん記事のパクリでプログラミングの初期段階で悩む所をかなり流用させていただいた．ヒトのフンドシで相撲を取っているようで申し訳なく思ってしまいます．
こんな興奮をブログ上で味わえるとは思いませんでした．改めてGDOさんに感謝です．

前回の記事を編集している時点ではJavascriptの書き方が不理解だったので不本意ながらプログラム公開には至らなかった．
今でも不勉強なのには変わらないが，どうにかこうにか動くモノが出来上がったので報告差し上げたい．

さて，
前回はロープの比喩でアルゴリズムの概論を書いたが，今回は詳細実装内容．
ロープを手繰り寄せる動きをコーディングする方法は色々思いつくが，今回は以下のような考えで実装方法を決めた．

数独と言えば，様々な可能性の中から素晴らしい組合せのタカラを探すようなもの
タカラと言えば，日本有数の玩具メーカーで「リカちゃん人形」が有名
リカちゃんと言えば，「Recursive Call（再帰呼び出し）」

ということで，意味も無く再帰呼び出しを採用決定！
「メモリを握りっぱなしにしてしまう」とか「スピードが遅い」とか気にしない．こういうコトは勢いが重要！
ちなみに最初は「藤田幸希プロ」をネタにしようとしていたのだが話が続かなくて勢い不足だったので敢え無くボツ．

具体的な解答ロジックは下記
【解答関数 （引数：マス目のラベル）】
マス目に1〜9まで試してみる
    行チェックに通っていて
    列チェックに通っていて
    ブロックチェックに通っていたら以下を行う
        マス目にその数字を入れる
        全部のマス目が埋まれば終了
        未だなら【解答関数（ラベルをカウントアップ）】を呼ぶ

この関数に「0」を渡すだけで解答を得られるというお手軽実装．
もっと華麗な方法があるハズだけど気にしない．
実際は，マス目に問題として設定した数字が入っている場合を考慮するロジックがあったり，返り値の考慮があったりと，もう少しばかり面倒な（キタナイ）コードになっている．

っということで，テストもソコソコにお待ちかねの解析インターフェース公開．
本家のgodgeoさんがまだ公開していないので少しばかり気が引けるが公開しちゃいます．
突貫工事で作ったのでバグだらけかもしれませんが，もし気づいたコトがあったらコメントによろしくお願いします．
##既知のバグ##
ブログの全体表示では何故か動かないので，「この記事の詳細」で表示後にお試しください．

前回は数独を解くのに楽をして確率的解法を用い，ドッグレッグホールをショートカットするかのごとくギャンブルを試みたが敢え無く失敗．
ということで数独シリーズ第2回はシラミ潰し解法．

まず，便宜上８１のマス目に１〜８１のラベルをつけてみる．

1	2	3	4	5	6	7	8	9
10	11	12	13	14	15	16	17	18
19	20	21	22	23	24	25	26	27
28	29	30	31	32	33	34	35	36
37	38	39	40	41	42	43	44	45
46	47	48	49	50	51	52	53	54
55	56	57	58	59	60	61	62	63
64	65	66	67	68	69	70	71	72
73	74	75	76	77	78	79	80	81

シラミ潰しというぐらいだから概要は「８１のマス目すべてに1〜9まで入れてみて確かめる．」という方法になる．
でもこれだと最悪９の８１乗回という超天文学的数字の回数だけ繰り返さなければならなくなるので，もうチョット端折った方法を執ることにする．
ロープを使った比喩で説明するとこんな感じ．

• 今手元に9本のロープがある．それぞれのロープには１〜９の数字が貼ってある．
• 各ロープの先には更に9本のロープが繋がっており，それぞれのロープには１〜９の数字が貼ってある．
• また更に各ロープの先には9本のロープが繋がっていて，都合81段ロープが繋がっていることとする．

ココまでが問題の定義．イメージとしては81段のタコ足ロープのお化け．
では以下が解の探索．

• まず１段目の１番のロープを手繰り寄せてマス目の１番目に入れて，例の「行チェック」「列チェック」「ブロックチェック」を行う．
• チェックに通ったら次の段のロープを手繰り寄せて同様にチェックを行う．
• チェックにはねられたらマス目の数字を消してそのロープを切り，同じ段の次の数字のロープを手繰り寄せる．
• ９の数字まで試してダメだったらその上の段の次の数字のロープを手繰り寄せる．
• 「i」段目の「j」番ロープを手繰り寄せて「i」番マス目に「ｊ」番の数字を入れてチェックすることを繰り返す．
• 81段目のロープを手繰り寄せた時点でチェックに問題が無かったら，その時マス目を埋めている数字が解答．

ということで基本的な考え方は完成．
この様に行きつ戻りつシラミつぶしに探索しながら枝刈りをするという方法はゲームプログラミング等の人工知能の分野では古典的方法なので，恐らく有効な方策だろう．

あとはこれを忠実にコーディングして，ValidationCheckとDisplayの機能を作り込めば動くハズ！
ここまでHTML形式で結構書いたので，消えてしまっては悲しいので実際のプログラムは次回にします．

出来上がりイメージはこんな感じ

世界的なブームになっていると噂の「数独」．
私もかねてから興味があったものの，パズルを解きまくるというまでには至らなかった．

しかしながら，尊敬申し上げるブロガーgodgeoさんが数独解析プログラミングの連載を始めたと知っては黙ってはいられない．
数ヶ月前に取り組んだモノの完成せずに放り投げていたプログラムに再び手を入れたので私もブログ上で報告しようと思う．
しかし初回から長いです．

数独になじみの無い方は概論をコチラで． 続きを読む...