プログラミングパズルに関心のある人は雑談しましょう！
でも、 ○ ■● ■ ■■ ■＝地面 ○＝スイカ ●＝トム こう置くと、段差が大きいんです（汗汗 以上
ふら～っと来ました。面白いですね。 高橋駿輔さんの言うステージ３ですが、そのように 下に置かなければいいだけのことですね。 他にも方法があります。 私は今、ステージ４で試行錯誤中。奥が深いです。
思考型パズルゲームで遊ぼうのアッタジュニアのステージ３、 ■○○■ ■■ ■＝地面 ○＝スイカ こういう風におくと取れないんです。 誰か攻略法教えてください 以上
deepgreenさん、こんばんは。 ハードウェアの進化を待たずして１３パズルを解いてしまったんですね。 これまでいろいろやってきた事のノウハウがほとんどすべて活かされている ようで素晴らしいです。解が１通りというのも、なかなか面白い結果ですね。 SubGoalを用いるという経験がほとんど無かったので勉強になりました。 ありがとうございます。
ちょっとご無沙汰してます。deepgreenです。 １３パズルの最長手数解を求めた結果を以下に報告します。 【問題の定義】 以下の局面を最終局面とする１３パズルの最長手数を求める問題です。 １ ２ ３ ＋ ４ ５ ６ ７ ＋：ダミー（移動不可） ８ ９ ａ ｂ ＊：スペース ＋ ｃ ｄ ＊ この１３パズルの局面の数は、１４！／２＝４３，５８９，１４５，６００通りあり、１局面を１ビットで表現 したとしてもメモリ不足で幅優先探索では解けません。これを、２ステップサーチ＋斜軸対称性を利用して局面 の数を削減すると、３＊１３！／２＝９，３４０，５３１，２００通りとなるが、まだとどきません。 （高橋謙一郎さんの分析：２００４．０２．０６の書き込み） 今のところ、これ以上の改善は思いつかないので、別のアプローチを採用した。といっても新しいものではなく 以前に１５パズルの最長手数へのアプローチ（これは挫折した）を簡略化したもの＋上記の２ステップサーチ＋ 斜軸変換を適用しただけです。 【結果】 ・最長手数 ７４手 （下記の１通り。この解は斜軸変換しても変わらない） ＊ ｂ ７ ＋ ｄ ａ ６ ３ ｃ ９ ５ ２ ＋ ８ ４ １ ・探索時間 約１９時間 ・使用ＰＣ ＣＰＵ：Ｐｅｎｔｉｕｍ４ １．４ＧＨｚ メモリ：５１２ＭＢ （約４００ＭＢのハッシュテーブルを使用） なお、高橋謙一郎さんの１５パズルのソルバーを改造して使用させていただきました。 このソルバーなくして、この問題の解決はありえません。ありがとうございます。 解法の説明は、deepgreenのＨＰにｕｐします。http://www2.tokai.or.jp/deepgreen/
こんばんは、deepgreenです。 >実は私もいろいろ試したのですが（５）の方法は、私の場合は９５％までしか圧縮でき >ませんでした。ハッシュ値をｎ手附近に群生させたいという追加問題はしばらく封印する >べき、ということにもなったみたいですね。 そろそろ本題かな。（これ自身もパズルt的要素がありますけど） >ところで（２）の方法の改良案ということですが、具体案ということみたいですね。 >座標の取り方にもよりますが、単純な座標では、偶数手の局面では、ｐは奇数となり、 >奇数手の局面では、ｐは偶数となる、とは言えません。 あまり、考えていませんでした。以下のような変換はどうでしょう。 # location # 0 1 2 3 # 4 5 6 7 # 8 9 10 11 ［p to s］ s = p/2 ［s to p］ 奇数手 p = s*2 + (s/2 & 0x01) 偶数手 p = s*2 + 1 - (s/2 & 0x01) 高橋さんの言われるように、逆変換は、mapping方が楽ですね。
特殊な場合にしか使えませんが、メモリ節約に「斜軸変換」を利用する方法があります。 斜軸変換については勝手に付けた用語なので、ここを読んでください。 https://computerpuzzle.net/etc/bbs/bbs29.html たとえば３×３の８パズルにおいて全局面数は、9!/2 = 181,440通り ですが、これを２手 ずつの探索にすると全局面数はその 4/9 の 80,640通り にできます。このとき１手目の 局面２つを登録して、そこから探索を開始することにします。 ＊○＊ ○＊○ ○：空きマス位置 ＊○＊ 次に、正方形のボードでは斜軸変換が可能なので空きマス位置が△に来たら斜軸変換して からハッシュ値を求めることにすると空きマス位置は２通りだけとなります。全局面数を さらに半分の 40,320通り として探索することができるようになります。 ＊○＊ △＊○ ○：空きマス位置 ＊△＊ △：ここが空きマスなら斜軸変換する 実験の結果、３１手（１通り）となりましたが、その１通りの解を斜軸変換して実際は ２通りになります。これは４×４の１５パズルにも応用できるのですが、無理なので 下図のような１３パズルを考えてみます。斜軸変換のできる形なので空きマスの位置は ３通りになります。全局面数を計算すると、3 * 13C2 * 11! = 9,340,531,200通りです。 メモリ量は１ギガバイトをちょっと超えてしまいます。あぁ残念。でもごく近い将来には 可能になりそうな量になりました。 １ ２ ３ ４ ５ ６ ７ ８ ９ 10 11 口：空きマス 12 13 口 ところで話しは変わるのですが、この１３パズルにおける「スライドパズルの偶奇性」に、 ちょっと難があります。まず、偶奇性があることはあきらかです。そこで、13のコマを12に して(12を２枚にして)探索をしたいのですが、後でこれを元に戻すにはどうすればよいのか、 ということなのですが、転倒数を調べる順序が見つからないのです。転倒数については私の ＨＰよりも、M.HiroiさんのＨＰのほうが参考になると思います(下のURL)。 右上角と左下角の凹部分に動かせないダミーのコマを置いて１５パズルの場合とまったく 同じ転倒数の数え方をすればよいのでしょうか？。http://www.geocities.co.jp/SiliconValley-Oakland/1680/puzzle/parity.html
deepgreenさん、こんばんは。 実は私もいろいろ試したのですが（５）の方法は、私の場合は９５％までしか圧縮でき ませんでした。ハッシュ値をｎ手附近に群生させたいという追加問題はしばらく封印する べき、ということにもなったみたいですね。 ところで（２）の方法の改良案ということですが、具体案ということみたいですね。 座標の取り方にもよりますが、単純な座標では、偶数手の局面では、ｐは奇数となり、 奇数手の局面では、ｐは偶数となる、とは言えません。 ０①２③ ④５⑥７ この座標の決め方では成立しない(私がよく使う単純な座標)。 ８⑨10⑪ ０③６⑨ ①４⑦10 この座標の決め方なら成立する。 ２⑤８⑪ ｓ＝ｐ／２とすると、偶数／奇数いずれの場合も ｓ＝０～５となる。というのは確かに どちらでも成立するのですが、局面を復元するときには、私はテーブル参照という方法を 採っています。(単純な座標を使う場合のことです) p0[s] = { 1, 3, 4, 6, 9, 11}; 偶数手の局面 p1[s] = { 0, 2, 5, 7, 8, 10}; 奇数手の局面
こんばんは、deepgreenです。 高橋さん、いろいろと実験をしていただいて有り難うございます。 ちょっと、お詫びと訂正です。お騒がせしてすみません。 （その１） 前回提案した（５）の方法の予備実験に見落としがあり、過剰に良い結果となっていました。 実際に高橋さんの１１パズルを改造して実測した結果、以下のように効果なしとの結論です。 必要なBitMap数 BitMapの全数 圧縮率 ［ケース０] 533,596 665,280 80.2 % ［ケース２］ 488,136 665,280 73.3 % ［ケース０]は、ハッシュ関数は、そのままにして、Ｕ＝Ｈ／Mapsize, Ｌ＝Ｈ％Mapsizeと して、ビットマップ関数だけ実装した場合。 （その２） （２）の方法の改良案です。２手づつ進めると、前に述べたように最後が面倒です。 局面の奇偶性に着目して、ハッシュ関数を偶数手の局面の場合と奇数手の局面の場合で少し かえることにします。 （局面の奇偶性の定義） ＊ ○ ＊ ○ 空きマスの位置が○のとき 偶数手の局面 ○ ＊ ○ ＊ 空きマスの位置が＊のとき 奇数手の局面 ＊ ○ ＊ ○ ［ハッシュ関数］ 0 1 2 3 4 5 6 7... ＢＯＡＲＤ上の数字の並び －＞ ａｂｃｄ＊ｅｆｇｈｉｊk （＊は空きセル） ↓ ＊を除いた並びを作成する ａｂｃｄｅｆｇｈｉｊｋ もとの＊の位置をｐとすると（この例では４） 偶数手の局面では、ｐは奇数となり、奇数手の局面では、ｐは偶数となる。 ｓ＝ｐ／２とすると、偶数／奇数いずれの場合も ｓ＝０～５となる。 ｈａｓｈ ＝ ｓ＊（11！)/2 + (ａｂｃｄｅｆｇｈｉｊｋのハッシュ値） とすると、このｈａｓｈの値は、今までの半分の大きさとなる。 もとに戻すには、ｐ＝２＊Ｓ＋δ ただし、δ＝０（奇数手の局面の場合）or １（偶数手の局面の場合） を求めれば空きセルの位置がきまるので問題ないでしょう。 この方法は、ハッシュ関数をちょっと変えるだけなので、楽だと思います。
メモリに余裕があると、ＯＳがディスクアクセスをメモリにキャッシュして しまうことを何度か経験しているので、メモリに余裕が有り過ぎない場合での (２)＋(３)の方法がどの程度なのか、１２パズルを解かせてみました。１２パズル というのは、これを検証する目的で下図のようにでっち上げてみました。 【１２パズルの完成形】 １ ２ ３ ４ ５ ６ ７ ８ ９ □:空きマス 10 11 12 □ 全局面数は、6 * 12C2 * 10! = 1,437,004,800 通り (179,625,600 バイト) さらに、4,000,000 バイトのバッファを２つ用意してみました。合計で、 187,625,600 バイトなので、メモリが 256MB なら収まります。 メモリには、まだちょっと余裕がありますが現実的にはこんなもんでしょうか。 実行結果は、72手(6通り)となりました。肝心の実行時間は、1時間28分。 待てない時間でもないので、使えるいい方法という結果になったと思っています。 deepgreenさん、ありがとうございます。 ただ、１１パズルから１２パズルに増えただけ。１５パズルにはほど遠いです。