悩めるプログラマの高橋です。

ありがとうございます。執筆依頼があったのが６月、やっと発売されました。
と言っても私はまだ現物を見ていません。私の住んでいる山形は書籍関係の
発売はすべて１日遅いのです。明日2,3冊買占めようと思っています(記念に)。

記事の終盤はgeepgreenさんとの話がなかったら書けなかったもので当時の
旬の話題を書いてしまいました。どうもありがとうございます。

それから広井さんがX68000の電脳倶楽部に書いた記事を先に読んでいたなら
私の今回の記事も別のものになっていたろう、とそれが残念です。

こんばんは、deepgreenです。

おめでとうございます。そして,お疲れ様でした。
早速、高橋さんの力作を読ませていただきました。素晴らしい内容です。

この記事を読むと、深さ優先探索の好きな私も、ＩＤＡをやってみようかと
気持ちがゆらぎます。ちょっと浮気かな。
アンコールではないですけど、続編をつい期待したくなりますね。

１５パズルは、ＩＤＡで意外とよい成績がでましたね。実用上は結構いける
かもしれません。

こんばんは、広井です。

> 皆さん方には物足りなく感じてしまう内容になっていると思います。申し訳ありません。

いえいえ、そんなことはありません。
最近、アルゴリズムの解説記事を掲載する雑誌が少ないなかで、
パズルを題材にアルゴリズム入門的な記事を執筆されたことは、
とても素晴らしいことです。

どのプログラミング言語を使うにしても、けっきょく
「アルゴリズム＋データ構造＝プログラム」にかわりはありません。
アルゴリズムの学習はとても重要なことだと思います。

　これは、パズルを解くアルゴリズムについて入門的かつ網羅的な記事を書いて
ほしいという執筆依頼があって、C言語は知っているけどパズルを解くような経験
があまり無い読者を対象にして書かせていただいたものです。だから、皆さん方
には物足りなく感じてしまう内容になっていると思います。申し訳ありません。

ホームページを開設しているとこんなこともあるんですね。原稿料をあてにして
ノートパソコンを買ってしまいました。今それを無線LANで使ってます。

こんばんは、広井です。

私が毎月購読しているプログラミング系の雑誌に「Ｃ MAGAZINE」があります。
11月号(10月18日発売予定）の内容をホームページで確認したのですが、
特集「パズルを解くアルゴリズム」は高橋謙一郎さんが執筆されたのですね。
11月号、とても楽しみです。

動きが制御できないっす

deepgreenさんの方法を読んだとき１時間４４分で探索が終わるハズが無い
と最初に思ってしまいました。探索量を概算で見積ると依然として膨大だか
らです。

> 探索時間を速くするため、予め各領域のｐｕｓｈパターン（３＾６個）に
> ついて、重複解もふくめて手数を求めておく。

「重複解もふくめて」ここが凄いアイデアですね。これによって処理がとて
も軽くなります。１時間４４分というのには納得出来ます。しかし、ほんと
deepgreenさんて頭が良く廻るなあ。驚かされっぱなしです。

皆さん、ありがとうございます。deepgreenです。

幅優先探索の結果、２５手の解は存在しないことがわかりました。
（従って、２４手の解が最長手数となります。）

補足：幅優先探索の課題は、状態を記憶するスぺース量にあります。この場合
　　　も、単純な方式では３＾２２＝３．１４＊１０＾１０となり、破綻する。
　　　しかし、状態を記憶せず、生成できれば話は変わります。

［概要］
　　問題面ではなく解のｐｕｓｈパターンをベースに考えます。
　　ｐｕｓｈパターン（ｐ）に対して２６個の０解を重ねた重複解を生成し、
　　ｐの手数が最小となるのものを代表とする。

　　５ｘ５を以下の５つの領域に分割する。

　　　　ＡＡＡＢＢ
　　　　ＡＡＡＢＢ　　この分割は高橋さんと同じですね
　　　　ＣＣＥＢＢ
　　　　ＣＣＤＤＤ
　　　　ＣＣＤＤＤ

　　ｐｕｓｈパターンｐの各領域の手数をａ、ｂ、ｃ、ｄ、ｅとする。
　　０解のパターンからｅの地点は無条件に２としてよい。

　　探索時間を速くするため、予め各領域のｐｕｓｈパターン（３＾６個）に
　　ついて、重複解もふくめて手数を求めておく。

　　ｍ＝ａ＋ｂ＋ｃ＋ｄとなる（ａ，ｂ，ｃ，ｄ）の組み合わせパターンを生
　　成する。次に、（ａ，ｂ，ｃ，ｄ）を満たすすべてのｐｕｓｈパターンｐ
　　について、ｐが代表かどうかをテストする。

　　まず、ｍ＝２２から始めて、解が１つ見つかれば、ｍを＋１して、２３，
　　２４と探索を続ける。解が存在しないところで終了すればよい。
　　（ｍ＝２２は２４手の解の確認の意味で探索）

　（ａ、ｂ、ｃ、ｄ）の選び方
　　領域の対象性から、ａ，ｂ，ｃ，ｄは以下の条件の範囲に限定してよい。

　　　　ａ＞＝ｂ，ｃ，ｄ
　　　　ａ＝ｄのとき、ｂ＞＝ｃ　
　　　　ａ＜＝１２（領域の大きさは６なので）
　　
　（結果）
　　ｍ＝２２（２４手の解）は以下のパターンを検出したが、ｍ＝２３は
　　解が存在しなかった。

　　　　ｍ＝２２の解のパターン　　　　対応する問題面
　　　　　２２２０２　　　　　　　　　　２０２２２
　　　　　００００２　　　　　　　　　　０１２１１
　　　　　１０２０１　　　　　　　　　　００１１０
　　　　　２００２０　　　　　　　　　　０２０２０
　　　　　０２２２０　　　　　　　　　　２２００１

　　探索時間は、ThinkPad（Pentium　133MHz）で　１時間４４分

高橋です。私もギブアップしそうです。

幅優先探索が使えないなら深さ優先探索を使うことになります。
再帰を使って解の存在する問題面(3^22個)を作り、27通りの解
の中から最適解を選ぶことになります。(重いなぁ)

ただし０解パターンを見ると中央の１箇所に影響を与えること
が出来ないのでその場所は２回押すべきです。そうなるとその
場所を２回押すための条件式があります。それはこの式です。

13: ------------1------------　111211-22-121--22---1----

右辺の計算結果が２になるように問題面を作ってやる必要があ
ります。この制約を受けて計算量は 3^21 に減らすことが出来
ます。後は対称性を考慮して探索量を減らすことが考えられます。
例えば下図の問題面でＡの領域にある１の個数よりもＢ,Ｃ,Ｄ
の各領域で１の個数が超えてはいけない、とする方法です。

　　問題面
　ＡＡＡＢＢ
　ＡＡＡＢＢ
　ＣＣＥＢＢ
　ＣＣＤＤＤ
　ＣＣＤＤＤ

この方法で探索量をどの程度減らせるかは見積もれませんが、
仮に約1/3〜1/4に減らせたとして 3^22 よりも最終的にその
約1/10に減らせそうですが、まだだひと工夫ほしいところです。

他に探索量を減らすアイデアはないでしょうか。

こんばんは、広井です。

３色版ライツアウトの最長手数、これは難しいですね。
3 ^ 22 は、とても大きな数字です。24 手の問題を見つけた
だけでも凄いことだと思います。私も考えてみましたが、ギブ
アップしそうです。