プログラミングパズルに関心のある人は雑談しましょう！
１１パズル最長手数面の探索に関する一連のメモリ節約法を実験してみた結果です。 実験1: １手ずつ、ビットマップ３枚 メモリ=89,812,800byte 455sec 実験2: １手ずつ、ビットマップ２枚 メモリ=59,875,200byte 518sec 実験3: ２手ずつ、ビットマップ２枚 メモリ=29,937,600byte 348sec 実験4: ２手ずつ、ビットマップ１枚+2M メモリ=16,968,800byte 392sec CPU = Athlon XP 2100+ (1.73GHz) Compiler = Visual C++ 5.0 (実行速度で最適化) deepgreenさんの考案した、(２)＋(３)の方法が一番魅力的のように感じました。 ただ、ディスクアクセスがプログラムの意図したタイミングで行われているかは 再調査の余地があります。メモリに余裕が有り過ぎるとＯＳが勝手に最適化して しまう可能性が考えられるのです。とは言っても、(２)＋(３)の方法がメモリの 節約という観点と実行速度で使いものなるという観点からベストのように思います。
塗り壁さん、こんばんは。お久しぶりです。 ホームページの移転に関する、リンクの更新は了解しました。 Ｎ−クイーン問題も１５パズルも終わりは無いと思っています。 ただ、私の場合は数学的なアプローチがとても弱いので着いて行く のがつらいのですが、なるだけ着いて行きたいと思っています。 中学生の頃までは数学も得意だったのですが、ポリポリ。 いろんなアイデアはお互いに使い回しするのが正しい道だと思っています。 山があるから登るみたいに、興味の尽きない問題はみんなでどこまでも 登って行きましょう。
高橋謙一郎様、御無沙汰しております。 「点と線の部屋」の高橋です。 このたび、プロバイダーの都合でホームページを移転することになりました。 移転先は次の通りです。よろしければリンクの更新をお願い致します。 「点と線の部屋」本館 http://www32.ocn.ne.jp/~graph_puzzle/index.html 直接メールでも良かったのですが、目立たせようとこちらに記載させてもらいました。 悪しからず、ご了承ください。 ついでといってはなんですが、２件ほど書かせてもらいます。 ・Ｎ−クイーン問題 プロジェクトの話は私はあきらめておりません。手詰まりとのことですが、 そういう場合の数学での常套手段は、問題を一般化することです。 一般化の方針は幾何学的な観点、代数学的な観点などいろいろあると思いますが、 組み合わせ論的には次のようになると思います。 ●Ｎ次の順列に対し、同じ斜め一直線上にある点の対の個数をクイーン指数 と呼ぶ事にする。クイーン指数がｍである順列の個数をＱＩｎｄ（Ｎ，ｍ）と書くとき、 それらの値、及び値の間に成り立つ関係を求めよ。 言わずもがなですが、Ｑｉｎｄ（Ｎ，０）がＮ−クイーン問題の解の個数に当たります。 私も、そのうちこの問題を考えようと思っていますが、興味のある方は是非挑戦して下さい。 ・１５パズル 先日の貴兄の書き込みにて、私もプログラムを作成してみました。（そのうち、 ホームページにも載せようと思います) この問題も数学的には順列の話ですね。空きマスを移動させることは、 状態（を表わす順列)に互換（２個の要素を交換し、他の要素は動かさない置換） を作用させることに当たります。 私のプログラムはその状態を木構造で管理してそれを幅優先で辿るというものです。 木構造の実装が今の状態では結構メモリーを食いますので、残念ながら今は９パズ ルまでしか対応できていません。 ただ、もう少し理論的に追い込む必要がありそうです。例えば、３パズルの最長手数の 最終状態は＜（１，４）（２，３）＞とサイクル表示できます。これは斜めの対ですね。 同様に、５パズルは＜（１，４）（２，５）（３，６）＞ 縦並びの対。 ７パズルは＜（１，８，５，４）（２，７）（３，６）＞ 中央斜めの対、及び、それ以外(両端) 以降は略しますが、この辺が取っ掛かりになりそうな気がします。
deepgreenさん、こんばんは。 それにしても次々といろんなことを考えるものだと驚いてしまいます。 でも、私の力不足のため、今回の（５）の方法は理解するのが難しいです。 「すべてのビットが０のマップは作らないことにする」という意味がよく分かりません。 私がテスト中だった方法と似ている気もします。(成果はあまりよく無かったのですが) 私がテスト中だった方法： BitMap全体を最初に作るのではなくBitMap全体をいくつかの領域に分割することにして、 あるBitMap領域を初めて参照しようとしたときに、その領域だけのBitMapを動的に確保し、 あるBitMap領域がすべて(n-2)手の局面で埋まって役目を終えたなら動的にメモリを開放する。 （５）の方法も、動的にメモリを確保したり開放したりするということなのでしょうか。 それと、「ただし、＊：上位の桁 ？：下位の桁とする」の部分ですが、「＊」は位置の ことなのか、初期完成形でその位置にあるコマ(場所は変動する)ということなのかも 教えていただけると助かります。すみません、よろしくお願いします。
こんばんは、deepgreenです。 強いて圧縮をやるとすればという案ですが、どうでしょうか。 （５）マップの圧縮 ハッシュ値を上位ｍ桁、下位ｎ桁に分けて考える。 下位ｎ桁は従来どおりのビットマップとする（ｎ！／２のＭａｐがたくさんある） メモリを節約するため、すべてのビットが０のマップは作らないことにする。 上位ｍ桁の値でこのビットマップを以下のように管理する（MapIndexと呼ぶ) −１ ： ビットマップは存在しない（値がすべて０のマップのため） ｋ ： 当該の下位ビットマップ用にＫ番目のマップ域を使用する 局面の配置 ａｂｃｄ ｅｆｇｈ ---> ハッシュ値 ---> Ｕ ＝ Ｈ ／ (n!/2) ｉｊｋｌ （Ｈ） | +---+------------+ ↓ ↓ +---+----+----+---+----+---+--------- MapIndex | 0 | -1 | -1 | 1 | -1 | 2 | ... +---+----+----+---+----+---+--------- | +---------+ ↓ +-----+-----+-----+------------- | | | | BitMap | [0] | [1] | [2] | ... | | | | +-----+-----+-----+------------- BitMap内の位置は、Ｌ ＝ Ｈ ％ （n!/2) で求める 高橋謙一郎さんの１１パズルＳｏｌｖｅｒを少し改造して、ｍ＝６，ｎ＝６の 場合について必要なビットマップの数を調べた結果、以下のようになりました。 MapIndexの位置 必要なBitMap数 BitMapの全数 圧縮率 ［ケース１] ＊＊＊？ ＊＊？？ 329,520 665,280 ４９．５％ ＊？？？ ［ケース２] ＊＊＊＊ ＊＊？？ 300,097 665,280 ４５．１％ ？？？？ ［ケース３] ＊＊＊＊ ＊？？？ 294,522 665,280 ４４．３％ ＊？？？ ただし、＊：上位の桁 ？：下位の桁とする MapIndexに必要なメモリは、６６５，２８０ｘ４＝約２．７ＭＢ BitMapに必要なメモリは、約３０ＭＢ＊０．４５＝１３．５ＭＢ あわせて、約１５．２ＭＢとなります。 ［ケース１]が良いだろうと思って最初に調べたのですが、結果は普通にやる方が よいと出てしまいました。
高橋さん、こんばんは。deepgreenです。 ご指摘のとおり、（４）は,重すぎてつかえませんね。 策におぼれてしまいました。面白いとおもったのですが。 ハッシュ関数を変える検討もしてみましたが、うまい答えがみつかりません。 確かに、ｎを中心に考えると、(n-1),(n+1)はその近傍になるので何かできそうな 感じはするのですが，．．．
deepgreenさん、こんばんは。 （２）は１回の探索で済ます方法がありましたね。私が甘かったです。（２）の方法は とても素晴らしい方法だと再認識しました。それにしても、deepgreenさんて、こういう 解析力は抜群ですね。（３）の方法はプログラムがややこしそうなので、（１)+(２）の 方法は、かなり有効な手段になりそうです。 （４）は、空きマスの位置に着目した偶奇性が合致して(ｎ−１)手の局面ではない局面 すべてに対して、１手もどした局面にｎ手の局面が存在すれば(ｎ＋１)手の局面である という逆発想でひとつひとつ鑑定していくのであれば、暗黙的に存在する下の方法（０） よりは確かに良いのですが、「(１)+(２)の方法」と同じメモリ量が必要になる分だけ、 効率がよくないと思います。でも、こういう方法を思い付けるのは、すごいです。 （０）12!/2 のすべての局面からそれぞれ完成形までの最短手数を反復深化で調べる。 保存用メモリはまったく要らない。(ただし、効果的な下限値枝刈り等が必要) 尚、追加問題については最小完全ハッシュ関数の作り方から見直す必要があると思います。 最小とはならないまでもｎ手付近のハッシュ値が群生するような特別な「完全ハッシュ関数」 の作り方が必要になると思うので私には難問すぎるようです。deepgreenさんならと振って みたのですが迷惑だったかも知れませんね。
こんにちは、deepgreenです。 追加問題がでるとは思いもよらないことでしたが、．．．ちょっと補足します。 （２）の補足：最長手数とその局面を求める方法 ２手づつの探索では、最長手数がｎ、(n+1)のいずれかを確定する処理が必要となります。 探索の結果、(n+2)手の局面が存在しない場合は、以下の手続きで最長手数とその局面を 求めることができる。 ｎ手の局面から１手進めた局面をａとします。ａは、（n+1）,（n-1）のいづれかの筈で すから、ａを基準にして１手進めた局面はｎ，(n-2) のいづれかになります。ａを基準 にして生成される局面がすべてｎ手の局面であれば、ａは（ｎ＋１）手の局面と判明します。 下図のｂのように（n-2）手の局面が１つでも生成される場合は、（n-1）手の局面です。 （ｎ＋１）手の局面 ---> ａ ／ ＼ ｎ 手の局面 ---> X Y Z ＼ ／ （ｎ−１）手の局面 ---> b ／ ＼ （ｎ−２）手の局面 ---> P Q R 上記の操作で（n+1）手の局面が全く存在しない場合は、最長手数は、ｎ手になります。 （４）３枚を１枚にする方法 (n-1),n,(n+1)の局面を１枚のマップにたたみこむ方法です。 前回の（２）で述べたように、局面の奇偶性に着目すると、ｎと(n+1) 又は、ｎと(n-1) を１つのマップで管理することが可能です。あるビットがオンになっていた時、その局面 の奇偶性を調べることで、ｎ，(n+1)のいづれであるかを判別できるからです。しかし、 (n-1)と(n+1)の奇偶性は同じため、(n-1),n,(n+1)を同時に管理することはできません。 そこで、ｘ＜Ｋの範囲では、ｎ，(n+1)を管理し、ｘ＞＝Ｋの範囲では、ｎ，(n-1)を管 理するという棲み分けを考えます。Ｋの値を０からＭａｘまでずらしていくことにより、 n,(n-1)の局面からｎ,(n+1)の局面に変換していきます。 （局面の奇偶性の定義） ＊ ○ ＊ ○ 空きマスの位置が○のとき 偶数手の局面 ○ ＊ ○ ＊ 空きマスの位置が＊のとき 奇数手の局面 ＊ ○ ＊ ○ （マップの各ビットの定義） n,(n+1)のマップ n,(n-1)のマップ [０]--------------[Ｋ]-----------------[Ｍａｘ] ｜ ｜ ｜ ＋---> 0 : (n-2)手以下の局面,又は(n+1)手以上の局面 ｜ 1 : 局面の奇偶性とｎの奇偶性が一致する場合は ｜ ｎ手の局面、そうでなければ、(n-1)手の局面 ｜ ＋-------------> 0 : (n-1)手以下の局面,又は(n+2)手以上の局面 1 : 局面の奇偶性とｎの奇偶性が一致する場合は ｎ手の局面、そうでなければ、(n+1)手の局面 （Ｋを１つ進める手順） Ｋの位置のビット＝１の時 当該ビットに対応する局面の奇偶性とｎの奇偶性が一致する場合はＫを１つ進 めるだけでよい。そうでない場合は、当該ビットを０にしてＫを１つ進める。 Ｋの位置のビット＝０の時 当該ビットに対応する局面の奇偶性とｎの奇偶性が一致する場合はＫを１つ進 めるだけでよい。（この局面は（n+2m)､(n-2m)の局面であり、(n+1)の局面と はなりえない） そうでない場合は、当該ビットに対応する局面をａとすると、ａの局面から1手 もどした局面をすべて生成し、ｎ手の局面が存在するかどうかを調べる。ｎ手 の局面が１つでも存在する場合は、当該ビットを１にしてＫを１つ進める。ｎ 手の局面が全く存在しない場合はそのままＫを１つ進める。 上記の操作によりＫを進めていきＭａｘまで到達した場合は、1手進める。 （n+1-->n,K=0にする）
deepgreenさん、お久しぶりです。 そして、大変素晴らしい解答をありがとうございます。 既にお分かりでしょうが、私の用意していた答えは（１）の２ビットの情報で十分 というものです。deepgreenさんの（２）（３）には感服しました。さすがです。 （２）の方法については、１回の探索で行う方法もあるのかも知れませんが、 ０手目（１局面）からスタートする探索と、１手目（２局面）からスタートする探索を 別々に２回に分けて行えば、探索の論理としては明瞭で確実と思われます。 最小完全ハッシュ関数にしても、空きマス位置６通りを基数にして最初に抜き出せば 良いので問題はないでしょう。（３）の方法も素晴らしいです。キューはシーケンシャル なので小さなバッファ分だけメモリ上にあれば良いという訳ですね。これらのアイデアが 有効に使える問題に出会ったときは、即実行ですね。 続いて第２問です。実は、この問題の答えは私自身も用意がありません。 ｎ手の局面を読んで(ｎ＋１)手の局面を生成するとき、同一面のチェックとしては、 (ｎ＋１)手、ｎ手、(ｎ−１)手のエリアだけを調べればよいということが知られて います。この理論を利用してメモリを節約する方法は？ というのが問題です。
ご無沙汰してます。deepgreenです。 幅優先探索の場合、ある局面の状態を以下のいづれかに分けて管理します。 Ｔ：既に生成された局面 Ｃ：丁度、ｎ手で生成される局面 Ｎ：（ｎ＋１）手で生成される局面 φ：まだ、生成されていない局面 （１）マップを３枚ー＞２枚にする方法 この４つの状態を管理するには、２ビットの情報で十分であり、Ａ，Ｂ２つの マップを用意して、以下のように対応させればよい。 Ａ Ｂ ０ ０ −−＞ φ １ ０ −−＞ Ｔ １ １ −−＞ Ｃ ０ １ −−＞ Ｎ Ａ，Ｂがともに１となる位置に対応する局面をスキャンして、その局面を基に 1手進めた局面を生成し、それに対応するＡ，Ｂの位置の状態が共に０であれば、 新たな局面であるから、Ｂのみを１（Ｎの状態）にする。 全てのｎ手の局面をスキャンしたら、Ｃの状態をＴに、Ｎの状態をＣに変更する。 ｎ＋１−−＞ｎとして、上記の操作を繰り返す。 （２）管理する局面を間引く方法 探索のループを２手づつ進めることにすると、空きの位置は以下の図のように １２ケ所から６ケ所に減るので、マップそのものが半分になる。 ＊ ○ ＊ ○ ○：管理対象とする空きの位置（偶数手の局面） ○ ＊ ○ ＊ ＊：管理対象外とする空きの位置（奇数手の局面） ＊ ○ ＊ ○ 探索の論理がちょっと面倒になるが、メモリ使用量が半分になるのは魅力。 また、（１）の方法とも共存できるので、合わせ技で全体を１／３にできる。 （３）Ｔ,φのみをメモリで管理する方法 メモリ上にはＴ，φを管理するマップのみを残し、新たな局面かどうかのチェ ックに利用する。Ｃ，Ｎに対応する局面はハッシュ値をファイルに書いておく。 Ｉ／Ｏ時間が気になるが、１ＭＢ程度のバッファを使えば、sequentialＩ／Ｏ なので、大きな問題にはならない。 メモリ使用量は、３０ＭＢ＋２ＭＢ（バッファ）となる。（２）と合わせると １５ＭＢ＋２ＭＢと約１／６になる。