ホームページへ戻る  書き込みリストへ戻る
プログラミングパズル雑談コーナー

プログラミングパズルに関心のある人は雑談しましょう!


高橋 駿輔 投稿者:Re:アッタジュニア  投稿日:04月15日(木)17時50分33秒

でも、
○
■● ■
 ■■
■=地面
○=スイカ
●=トム
こう置くと、段差が大きいんです(汗汗
以上


アッタジュニア 投稿者:mai  投稿日:03月31日(水)22時48分41秒

ふら〜っと来ました。面白いですね。
高橋駿輔さんの言うステージ3ですが、そのように
下に置かなければいいだけのことですね。
他にも方法があります。
私は今、ステージ4で試行錯誤中。奥が深いです。


アッタジュニアの攻略法 投稿者:高橋 駿輔  投稿日:03月31日(水)18時08分05秒

思考型パズルゲームで遊ぼうのアッタジュニアのステージ3、
■○○■
 ■■
■=地面
○=スイカ
こういう風におくと取れないんです。
誰か攻略法教えてください
以上


re:13パズルの最長手数解 投稿者:高橋謙一郎  投稿日:03月27日(土)22時30分04秒

deepgreenさん、こんばんは。

ハードウェアの進化を待たずして13パズルを解いてしまったんですね。
これまでいろいろやってきた事のノウハウがほとんどすべて活かされている
ようで素晴らしいです。解が1通りというのも、なかなか面白い結果ですね。

SubGoalを用いるという経験がほとんど無かったので勉強になりました。
ありがとうございます。


13パズルの最長手数解 投稿者:deepgreen  投稿日:03月27日(土)09時41分50秒

ちょっとご無沙汰してます。deepgreenです。

13パズルの最長手数解を求めた結果を以下に報告します。

【問題の定義】

 以下の局面を最終局面とする13パズルの最長手数を求める問題です。
 
    1 2 3 +
    4 5 6 7   +:ダミー(移動不可)
    8 9 a b   *:スペース
    + c d * 

 この13パズルの局面の数は、14!/2=43,589,145,600通りあり、1局面を1ビットで表現
 したとしてもメモリ不足で幅優先探索では解けません。これを、2ステップサーチ+斜軸対称性を利用して局面
 の数を削減すると、3*13!/2=9,340,531,200通りとなるが、まだとどきません。
 (高橋謙一郎さんの分析:2004.02.06の書き込み)

 今のところ、これ以上の改善は思いつかないので、別のアプローチを採用した。といっても新しいものではなく
 以前に15パズルの最長手数へのアプローチ(これは挫折した)を簡略化したもの+上記の2ステップサーチ+
 斜軸変換を適用しただけです。

【結果】

 ・最長手数     74手 (下記の1通り。この解は斜軸変換しても変わらない)
    
           * b 7 +
           d a 6 3
           c 9 5 2
           + 8 4 1

 ・探索時間    約19時間
 ・使用PC    CPU:Pentium4 1.4GHz
          メモリ:512MB (約400MBのハッシュテーブルを使用)

  なお、高橋謙一郎さんの15パズルのソルバーを改造して使用させていただきました。
  このソルバーなくして、この問題の解決はありえません。ありがとうございます。 

    解法の説明は、deepgreenのHPにupします。

http://www2.tokai.or.jp/deepgreen/


re:メモリ節約問題  投稿者:deepgreen  投稿日:02月06日(金)23時26分41秒

こんばんは、deepgreenです。

>実は私もいろいろ試したのですが(5)の方法は、私の場合は95%までしか圧縮でき
>ませんでした。ハッシュ値をn手附近に群生させたいという追加問題はしばらく封印する
>べき、ということにもなったみたいですね。

そろそろ本題かな。(これ自身もパズルt的要素がありますけど)

>ところで(2)の方法の改良案ということですが、具体案ということみたいですね。
>座標の取り方にもよりますが、単純な座標では、偶数手の局面では、pは奇数となり、
>奇数手の局面では、pは偶数となる、とは言えません。

あまり、考えていませんでした。以下のような変換はどうでしょう。

#  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方が楽ですね。


re:メモリ節約問題 投稿者:高橋謙一郎  投稿日:02月06日(金)21時22分56秒

特殊な場合にしか使えませんが、メモリ節約に「斜軸変換」を利用する方法があります。
斜軸変換については勝手に付けた用語なので、ここを読んでください。

http://www2.ic-net.or.jp/~takaken/auto/guest/bbs29.html

たとえば3×3の8パズルにおいて全局面数は、9!/2 = 181,440通り ですが、これを2手
ずつの探索にすると全局面数はその 4/9 の 80,640通り にできます。このとき1手目の
局面2つを登録して、そこから探索を開始することにします。

  *○*
  ○*○     ○:空きマス位置
  *○*

次に、正方形のボードでは斜軸変換が可能なので空きマス位置が△に来たら斜軸変換して
からハッシュ値を求めることにすると空きマス位置は2通りだけとなります。全局面数を
さらに半分の 40,320通り として探索することができるようになります。

  *○*
  △*○     ○:空きマス位置
  *△*     △:ここが空きマスなら斜軸変換する

実験の結果、31手(1通り)となりましたが、その1通りの解を斜軸変換して実際は
2通りになります。これは4×4の15パズルにも応用できるのですが、無理なので
下図のような13パズルを考えてみます。斜軸変換のできる形なので空きマスの位置は
3通りになります。全局面数を計算すると、3 * 13C2 * 11! = 9,340,531,200通りです。
メモリ量は1ギガバイトをちょっと超えてしまいます。あぁ残念。でもごく近い将来には
可能になりそうな量になりました。

  1 2 3
  4 5 6 7
  8 9 10 11   口:空きマス
    12 13 口


ところで話しは変わるのですが、この13パズルにおける「スライドパズルの偶奇性」に、
ちょっと難があります。まず、偶奇性があることはあきらかです。そこで、13のコマを12に
して(12を2枚にして)探索をしたいのですが、後でこれを元に戻すにはどうすればよいのか、
ということなのですが、転倒数を調べる順序が見つからないのです。転倒数については私の
HPよりも、M.HiroiさんのHPのほうが参考になると思います(下のURL)。

右上角と左下角の凹部分に動かせないダミーのコマを置いて15パズルの場合とまったく
同じ転倒数の数え方をすればよいのでしょうか?。

http://www.geocities.co.jp/SiliconValley-Oakland/1680/puzzle/parity.html


re:メモリ節約問題 投稿者:高橋謙一郎  投稿日:02月06日(金)21時07分39秒

deepgreenさん、こんばんは。

実は私もいろいろ試したのですが(5)の方法は、私の場合は95%までしか圧縮でき
ませんでした。ハッシュ値をn手附近に群生させたいという追加問題はしばらく封印する
べき、ということにもなったみたいですね。

ところで(2)の方法の改良案ということですが、具体案ということみたいですね。
座標の取り方にもよりますが、単純な座標では、偶数手の局面では、pは奇数となり、
奇数手の局面では、pは偶数となる、とは言えません。

  0@2B
  C5E7   この座標の決め方では成立しない(私がよく使う単純な座標)。
  8H10J

  0B6H
  @4F10   この座標の決め方なら成立する。
  2D8J

s=p/2とすると、偶数/奇数いずれの場合も s=0〜5となる。というのは確かに
どちらでも成立するのですが、局面を復元するときには、私はテーブル参照という方法を
採っています。(単純な座標を使う場合のことです)

   p0[s] = { 1, 3, 4, 6, 9, 11};    偶数手の局面
   p1[s] = { 0, 2, 5, 7, 8, 10};    奇数手の局面


re:メモリ節約問題  投稿者:deepgreen  投稿日:02月05日(木)00時07分09秒

こんばんは、deepgreenです。

高橋さん、いろいろと実験をしていただいて有り難うございます。

ちょっと、お詫びと訂正です。お騒がせしてすみません。

(その1)
 前回提案した(5)の方法の予備実験に見落としがあり、過剰に良い結果となっていました。
 実際に高橋さんの11パズルを改造して実測した結果、以下のように効果なしとの結論です。
     
          必要なBitMap数  BitMapの全数  圧縮率
   [ケース0]    533,596       665,280        80.2 % 
    [ケース2]   488,136    665,280     73.3 % 

 [ケース0]は、ハッシュ関数は、そのままにして、U=H/Mapsize, L=H%Mapsizeと
  して、ビットマップ関数だけ実装した場合。
 

(その2)
 (2)の方法の改良案です。2手づつ進めると、前に述べたように最後が面倒です。
  局面の奇偶性に着目して、ハッシュ関数を偶数手の局面の場合と奇数手の局面の場合で少し
  かえることにします。 

   (局面の奇偶性の定義)

     * ○ * ○   空きマスの位置が○のとき 偶数手の局面
     ○ * ○ *   空きマスの位置が*のとき 奇数手の局面
     * ○ * ○

  [ハッシュ関数] 
                     0 1 2 3 4 5 6 7...
     BOARD上の数字の並び −> abcd*efghijk (*は空きセル)
                          ↓
     *を除いた並びを作成する    abcdefghijk

     もとの*の位置をpとすると(この例では4)

     偶数手の局面では、pは奇数となり、奇数手の局面では、pは偶数となる。
     s=p/2とすると、偶数/奇数いずれの場合も s=0〜5となる。

     hash = s*(11!)/2 + (abcdefghijkのハッシュ値)

     とすると、このhashの値は、今までの半分の大きさとなる。
     もとに戻すには、p=2*S+δ
         ただし、δ=0(奇数手の局面の場合)or 1(偶数手の局面の場合)
     を求めれば空きセルの位置がきまるので問題ないでしょう。

   この方法は、ハッシュ関数をちょっと変えるだけなので、楽だと思います。


re:メモリ節約問題 投稿者:高橋謙一郎  投稿日:02月04日(水)21時07分02秒

 メモリに余裕があると、OSがディスクアクセスをメモリにキャッシュして
しまうことを何度か経験しているので、メモリに余裕が有り過ぎない場合での
(2)+(3)の方法がどの程度なのか、12パズルを解かせてみました。12パズル
というのは、これを検証する目的で下図のようにでっち上げてみました。

【12パズルの完成形】

   1 2 3 4
   5 6 7 8 9    □:空きマス
     10 11 12 □

 全局面数は、6 * 12C2 * 10! = 1,437,004,800 通り (179,625,600 バイト)
さらに、4,000,000 バイトのバッファを2つ用意してみました。合計で、
187,625,600 バイトなので、メモリが 256MB なら収まります。
メモリには、まだちょっと余裕がありますが現実的にはこんなもんでしょうか。

実行結果は、72手(6通り)となりました。肝心の実行時間は、1時間28分。
待てない時間でもないので、使えるいい方法という結果になったと思っています。
deepgreenさん、ありがとうございます。

ただ、11パズルから12パズルに増えただけ。15パズルにはほど遠いです。


 ホームページへ戻る 書き込みリストへ戻る