お気づきの点や感想要望などなんでもＯＫ！
「おっ凄い！」最悪の事態(15パズルの最長手数＝78手)は回避出来たようです。 deepgreenさんから解いてみてほしいという面を解いたら最短解は80手でした。 0 12 9 13 15 11 10 14 7 8 6 2 4 3 5 1 (WD=33/33,ID=29/29) LowerBound=66 [80 moves] time=4669sec 12 9 13 14 2 1 5 3 8 11 9 13 14 2 1 5 3 8 4 7 15 12 13 9 10 1 5 3 8 4 7 15 12 13 9 14 1 6 4 7 11 12 13 10 14 1 6 5 3 4 7 11 12 14 5 7 11 12 15 13 10 9 1 6 2 3 4 8 12 15 14 10 9 5 6 2 3 4 8 12 私としても初めて目にする最短解80手の問題です。予想では最長手数は90手を 超えるだろうと思っていただけに、この80手問題の存在を目にした程度でホッ としている自分は何なのかと思ってしまいます。？！不思議にうれしい。 実行時間は約１時間２０分。まだまだ厳しい現状ではありますが、上限値を ベースにしたdeepgreenさんの最長手数面を確定させる構想の理論は完璧です。 なんとかしたいという想いが益々が沸いてきます。 # 週末に現在の私のソースをアップしようと思ってます。
15Puzzle面白そうだなと思ってWebを調べてみたところ、 以下の論文にたどり着きました。 参考になると思います。 http://citeseer.nj.nec.com/32578.html http://citeseer.nj.nec.com/gasser95harnessing.html
こんばんは、deepgreenです。 高橋さんのSolverは、すごい成果ですね。 この１５パズルの最長手数問題に取り組んだ当時には夢想だにできない性能です。 いまでも信じられない位です。 (1) ＵＢｃｈｅｃｋのその後 ＭＤ 問題数 結果 ６０ 41,472 ８２手以下の問題しか存在しない（８４手以上は存在ない） ５９ 331,776 ８３手以下の問題しか存在しない（８５手以上は存在しない） ８３手の可能性のある問題は５２問存在する ５８ 2,678,400 ８２手以下の問題しか存在しない（８４手以上は存在しない） ５７ （途中で中止） 約４Ｍ個の問題を調べた範囲では、８３手以下の問題のみ なんとなく、８０手あたりかなという感触？ ７８手という結果だけは避けたいなぁ (2) できたら、この問題を解いてください（少し前に、１昼夜かけても解けなかった問題） * c 9 d f b a e 7 8 6 2 4 3 5 1 多分、７８−８２手です（記憶違いでなければ） (3) Ｕｌｉｎｅ（最長手数問題の探索） ＭＤを基本にした探索は、所詮参考にしかならないので、まじめに最長手数問題を 探索することを考える必要がある。現時点で考えているのは、以下のような手順です。 (再掲：ＵＢｃｈｅｃｋ) Ｘ −(a)−＞ ｓｕｂｇｏａｌ −(b)−＞ ｇｏａｌ ｓｕｂｇｏａｌとしては、以下の２パターンを考えました。 １２３４ １ｘｘｘ ｘｘｘｘ ５ｘｘｘ ｘｘｘｘ ９ｘｘｘ ｘｘｘｘ ｄｘｘｘ １５パズルの問題を上記のｓｕｂｇｏａｌまでの手数αとｓｕｂｇｏａｌからｇｏａｌ までの手数βのペア（α，β）で分類する。０<=α<=４６、０<=β<=５３であるから、 ４７ｘ５４の長方形のいずれかのマスに配置されることになる。 【Ｕｌｉｎｅ】 Ｕ＝α＋βを考える。（これは、ＵＢｃｈｅｃｋの返却値に他ならないが） Ｕが最大となるのは、α＝４６、β＝５３であり、Ｕ＝９９となる。Ｕの値に応じて （α，β）の組がいくつか決まることになる。現時点の最長手数は７８手であるから それ以上の解をさがすには、Ｕ＞＝７８の範囲を調べればよい。 （つまり、７８＜＝Ｕ＜＝９９が探索範囲） 【問題面の生成】 上記は、問題面が与えられたときの話としてすすめましたが、最長手数の問題を探索 するには、（α，β）から問題面を生成する必要があります。 （１）ｇｏａｌからｓｕｂｇｏａｌへの変換は、βとＵＢｃｈｅｃｋの（ｂ）のテーブル を使用すれば可能です。下図のｘの部分が決まる。 １２３４ ｘｘｘｘ ｘｘｘｘ ｘｘｘｘ （２）ｓｕｂｇｏａｌから問題面への変換は、ＵＢｃｈｅｃｋの（ａ）のテーブルだけでは 不足で（０，１，２，３，４のみなので）、逆変換のマップを別に用意する必要が あります。（ａ）のテーブルを作成するときに同時に作成できる。 【探索範囲】 実際に、Ｕ＞＝８０の範囲でどのくらいの問題が存在するかをしらべてみました。 Ｕ ｃｏｕｎｔ ｔｏｔａｌ +++ 99 ( 0, 0) +++ 98 ( 40, 40) +++ 97 ( 94, 134) +++ 96 ( 5900, 6034) +++ 95 ( 16922, 22956) +++ 94 ( 160213, 183169) +++ 93 ( 460953, 644122) +++ 92 ( 2277313, 2921435) +++ 91 ( 5622308, 8543743) +++ 90 ( 19731609, 28275352) +++ 89 ( 42406243, 70681595) +++ 88 (117330785,188012380) +++ 87 (229318503,417330883) +++ 86 (528165205,945496088) +++ 85 (965488281,1910984369) +++ 84 (1920079055,3831063424) +++ 83 (3332088901,7163152325) +++ 82 (5877064347,13040216672) +++ 81 (9714781332,22754998004) +++ 80 (15534323773,38289321777) 結果は、Ｕ＝８０だけでも、約１６Ｇ個、Ｕ＞＝８０では、３８Ｇ個 １５パズル全体では、約１０Ｔ個なので、全体の０．４％まで絞りこめた事になる。 仮に、ＵＢｃｈｅｃｋで更に１００００分の１に絞れたとしても、数Ｍ個の問題を Ｓｏｌｖｅｒで解かなければならない。 まだ，先は遠いようです。とりあえず、Ｕ＞＝８４をしらべてみようかと考えています。 うまくすれば、８４手以上の問題は存在しないといえるかも？（甘いかな？）
下のWD(WalkingDistance)の説明は自分で読み返してあまりにも意味不明すぎました。 「着想の発端は下のＵＲＬ」ですので、ここを見て何か感じとっていただければと。。。 ただし、私は幅優先探索で小規模なテーブルを事前に作成しておくことでWDを実現させて います。計算式だけで求めている訳ではありません。http://web2.incl.ne.jp/yaoki/slide.htm
１５パズル高速ソルバー開発に、また新たな進展がありましたので報告します。 ■MDは上下動と左右動に分割すべし 前回報告したID(InvertDistance)は上下動と左右動を別々に求めて両者を合算 していますが、MD(ManhattanDistance)も実は上下動と左右動の合算によるので あることを再確認しましょう。合算した結果どうしを比較してより厳しい値を LowerBoundとするよりも、上下動どうしのMDとIDを比較し、左右動についても 同様にして得た「結果の両者を合算」してLowerBoundを求めた方がより良い結果 を得ることが出来ます。 [Fig.1] [Fig.2] 私が提示した７８手問題 deepgreenさんが提示した７８手問題 0 15 14 13 15 11 14 13 12 11 10 9 12 0 9 10 8 7 6 5 8 3 6 5 4 3 2 1 4 7 2 1 1.(MD,ID)合算後に比較 76秒 2969秒 2.(MD,ID)比較後に合算 68秒 2469秒 ■WD(WalkingDistance) LowerBoundを得る、また新たな概念を見つけました。見つけたというよりも無理 にひねり出した感があります。プログラム的にも手の込んだ方法なので掲示板 での説明はちょっと困難なので触りの部分だけを簡単に説明します。 MDを上下動と左右動に分割してMDを改めて眺めて見ると「MDって随分あまいなぁ」 と思えてなりません。下のFig.3ではMD=4ですが「たった４手で解ける訳がない！」 [Fig.3] 1 2 3 0 5 6 7 8 9 10 11 12 13 14 15 4 上下動だけに着目した（左右動は考えない）場合、最低でも１１手は必要になる。 これがWD(WalkingDistance)です。つまりFig.3の場合、上下動のWDは11となります。 WDはMDの完全上位互換の値をたたき出します。この時点で私のプログラムからはMD は完全に消滅しました。私自身ビックリした成績がこれです。 [Fig.1] [Fig.2] 1.(MD,ID)合算後に比較 76秒 2969秒 2.(MD,ID)比較後に合算 68秒 2469秒 3.(WD,ID)比較後に合算 9秒 371秒 <-ここ ■次の課題 初期LowerBoundが小さいくせに最短手数の長い問題というのはあるものです。 この掲示板を見ていないだろうと思われるBINGOさん出題による次のFig.4です。 [Fig.4] 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0 (WD=20/20,ID=12/12) LowerBound=40 もう解は得ましたが依然として一昼夜ものです。こういう問題にも何か弱点があるはず！ WD(WalkingDistance)の詳しい解説はID(InvertDistance)も含めていずれＨＰにアップ しようと思います。が、その前にdeepgreenさんから「１５パズルの最長手数問題」が 解決されてしまいそうな予感も、、、、
こんばんは、deepgreenです。 高橋さんのID(invertDistance)は，非常に素晴らしい着想です。 これで私の悩み(速いＳｏｌｖｅｒがほしい）が解決しそうです。
あらさん、こんばんは。 N=19を7個も見つけるとはスゴイ腕前ですね。15パズルの最長手数問題に行き詰まるか 解決するか、何かしらのタイミングがないと「究極のナンプレ問題」に進めそうにあり ません。申し訳ありません。気にはしているのですが頭と体がふたつほしいです。
失礼しました。IDの説明にある斜軸変換とは縦横変換のことです。
これは面白い展開になってきましたね。上限値に着目したのは素晴らしいです。 当時、私は上限値をあまり気にしていなかったので盲点でした。MD=58以下の面 にとんでもなく手数のかかる面があるのか、それとも４×４の最長手数そのもの が80〜84程度なのか。今年中にはかなりの成果が出そうですね。 ところで、私は高速ソルバーの開発に力を注いでいたのですが、その中からある 程度の成果が出た事柄を書いてみます。 ■縦横変換 左上から右下への対角線を軸にして盤を反転させるのが縦横変換です。 このとき盤の数字そのものも変換させます。その数字の変換には変換表があり、 完成局面を単純に縦横変換させて得られます。例えば３×３の最長手数面は２つ ありますが、この縦横変換を行うと２つの面は全く同じ面であることが分かりま す。 縦横変換 数字変換 6 4 7 6 8 3 8 6 7 8 5 0 -> 4 5 2 -> 2 5 4 3 2 1 7 0 1 3 0 1 (最長手数面1) (最長手数面2) 数字変換表 0 1 2 3 4 5 6 7 8 0 1 4 7 2 5 8 3 6 ４×４の最長手数面の候補群から、この変換によって約半分を切り捨てることが 可能になります。 ■ID(InvertDistance) 現時点でLowerBoundを得るのにMD(ManhattanDistance)とPDB(PatternDataBase) がありますが新たな概念として「転倒距離(InvertDistance)」というものが存在 することを発見しました。 先ず転倒数を数えます。転倒数の意味が分からない場合は「４ｘ３の最長手数 探索プログラム」の説明を見てください。さて、ピースの上下動によって転倒数 は、-3,-1,+1,+3の変化があります。このことから「最低限必要な上下動」の回数 は、転倒数/3によって得られることになりますが、この計算が割り切れなければ 余りを加算します。次に「最低限必要な左右動」の回数を得るために斜軸変換を 行い同様の計算を行うと最低限必要な左右動の回数が求まり両者を合算した値が ID(InvertDistance)になります。例えばCマガ2000/11に載せた78手の問題[Fig.1] はMD=58ですがIDを計算すると70になります。さらにこのIDはMDと同様に親局面か らの差分のみで求められるという利点もあります。ちなみにこの問題はMDとIDを 使って76秒で解けました。 [Fig.1] 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 (MD=58,ID=70) LowerBound=70 ■逆解き ありきたりな発想ですが逆解きも検討しています。かなり技巧的な技を使っている のですがプロトタイプでのテストでは結構いい成果が出ていますが、もう少し検討 してから報告します。
こんばんは、deepgreenです。 とりあえず、８５手以上の問題があるかどうかを探ってみました。 ＭＤ＝６０の問題（全部で ４１，４７２個）には、８５手以上の問題は存在しない。 ＭＤ＝５９の問題（全部で３３１，７７６個）にも、８５手以上の問題は存在しない。 （ＭＤ＝５８の問題は未調査） ことがわかりました。 探索時間は、約４３００秒です。 少し仕組みを説明します。 ある１５パズルの問題が与えられたとき、その問題が高々何手で解けるかを判定する関数 （UBcheck：UpperBound check）をつくりました。たとえば、前回の問題の場合は、 高橋さんが解いた７８手の問題 最短手数７８手の問題 （ＭＤ＝５８） （ＭＤ＝６０） * f e d f b e d c b a 9 c * 9 a 8 7 6 5 8 3 6 5 4 3 2 1 4 7 2 1 ＵＢ＝８６−＞８４ ＵＢ＝８２−＞８２ 高橋さんの問題は、初期状態では８６手以下となりますが、少し局面を展開すると８４手 以下の問題とわかります。（判定時間は１５０ｍｓ） 私の問題の方は初期状態で８２手 以下の問題と判断できますが、少し局面を展開しても変わりませんでした。 （コストの割には、よい上限値をもとめることができる） ＵＢｃｈｅｃｋを使って、ＭＤ＝６０，５９の問題で８５手以上となるものを探索すると 上記の結果がえられました。 【ＵＢｃｈｅｃｋの仕組み】 途中にｓｕｂｇｏａｌをおき、問題面からｓｕｂｇｏａｌまでの最小手数とｓｕｂｇｏａｌ からｇｏａｌまでの最小手数の和を求めるだけです。高速化のために、２つのテーブル（ａ）， （ｂ）を準備してテーブルの検索だけで済むようにしてあります。多分、１つの局面なら数μｓ でもとめることができるでしょう。 Ｘ −(a)−＞ ｓｕｂｇｏａｌ −(b)−＞ ｇｏａｌ ｓｕｂｇｏａｌとしては、以下の２パターンを考えました。 １２３４ １ｘｘｘ ｘｘｘｘ ５ｘｘｘ ｘｘｘｘ ９ｘｘｘ ｘｘｘｘ ｄｘｘｘ 補足）（ｂ）のテーブル作成には、高橋謙一郎さんの４ｘ３の最長手数探索プログラムを 利用させていただきました。（ＨＰに公開されているもの） おかげで、少し改造する程度ですみました。ありがとうございます。