Q&A
タグに「アルゴリズム」があるといいと思います。
また、6×6盤の場合駒は何種何個になるのでしょう。
以下の私のブログに書いた将棋の駒の配置問題を解決したいと思います。
一応、私が作成したものはありますが、時間がかかって解けません。
言語は任意です。
以下のサイトの3.3.および4.のヒントをいただければ幸いです。
一気に問題を解いていただいても構いません。
http://blogs.yahoo.co.jp/artery2020/40173086.html
以下は、上記ブログの引用です。
■ プログラミング課題-駒配置問題
□ 問題
・将棋の駒40枚を9×9の盤上に同じ方向にお互いに取られないように配置できることが知られている。
・ネット上で探せた例は下に示している。
・また多湖輝の「頭の体操」にも例が載っていたが、同じものかは分からない。
・すべての組合せがどのくらいあるのかは、(少なくとも私にとっては)不明である。
・この組み合わせをすべて求める、これが問題。
□ プログラムのスペック
・任意の大きさの盤の問題を解けること。
・9×9だけではなく5×5、あるいは7×8など長方形の盤の問題も解けること
・別の言い方をすれば、プログラム中に番の大きさが記述されていてはいけない。
・三角形や円形の盤は対象外とする。
・既存の将棋駒ではなく、新たな動き方を定義した駒の問題も解けること。
・例えば、横に一つだけ動ける駒などを定義して問題に投入できること。
・別の言い方をすれば、プログラム中に駒の動き方が記述されていてはいけない。
・使用する駒の種類と数を指定できること。
□ 課題
・この問題を解くには、非常に時間がかかるので、いかに計算パワーを使わない解法を実現するかがポイント。
□ 参考
1.駒の動き方を最初に求めておく必要がある
1.1.問題を解いている最中に、「このポイントに、この駒を置いたときは、どことどこに動けるか？」と求めていると、非常に時間がかかる。
1.2.初期起動時に、すべての駒のすべてのポイントでの駒の動き方を求めておく。
2.配置情報の作成と取消のオーバーヘッドを少なくすること。
2.1.実行時には、どこかに駒が配置され、結果として、その行先はどこか？次に配置できる場所はどことか？という情報が作成される。
2.2.大部分の場合は、行き止まりになるので、その情報をキャンセルし、また新たな情報を作成することになる。
2.3.この情報を作成、キャンセルする処理の負荷を、できるだけ軽くすること。
2.4.このデータ構造を作るにも、(実行時に)コストがかかるが、差引してコストが低くなるようにする。
3.配置不可の判定を早めにすること
3.1.駒を配置できなくなるまで配置する ⇒ これはアホ。
3.2.「空きの数 ＜ 残りの駒の数」であれば、不可と判定する。
3.3.上記の状態になる前に、なんとか不可と判定する ⇒ 私にはロジック不明。
4.以前に不可と判定したパターンを保存しておく。
4.1.細かい部分でみれば、同じパターンが何度でも表れるはず。
4.2.ダメだったパターンを記憶しておいて、以降の実行をパスするようにする。
4.3.フィボナッチ数の計算でも以前に計算した値を記憶しておけばスピードは速くなるが、これと同じ。
4.4.ただ同じバターンであることの定義や認識が難しい。
4.5.パターンの単位を細かいものから、少し大きいものまで、階層的に記憶しておき、スピードアップを図る。
5.複数のコンピュータを利用して解く。
・私が作成したJavaプログラムは、次の状況
・2.は実装したが、もっとよい方法があったかもしれない。
・3.3.は未実装
・4.は未実装
・5.は未実装
・6×6盤では簡単に終了したが、7×7盤では解けなかった。
・3.3.と4.が実現できれば、非常に効果的と思われる。
□ お願い
私のパソコンの能力と私のプログラミング能力では難しいので、この問題をどなたか解いていただきたい。
====
ありがとうございます。
＞6×6盤の場合駒は何種何個になるのでしょう。
行先の少ない駒を、配置可能な範囲で、ぎりぎりまで多数個配置した場合に、時間がかかります。
回答2件
0
ベストアンサー
既に参照されているかもしれませんが、参考情報として、
将棋パズル（１）利かずの駒並べ: 詰将棋メモ
というページがありました。
ここからリンクされている
利かずの駒並べの全解探索
というページで、1860通りの解が見つかったそうです。
arteryさんが「プログラムのスペック」としてあげている様な一般化はせず、
「将棋の駒40枚すべてを9x9の盤面に、全ての駒同 士の利き筋(ききすじ)が
重ならないように並べる」を目指すために、
駒の特性を活かして、以下のような枝刈りを行ったそうです。
- 全ての駒の利き筋は左右対象のため、左右反転させた鏡像は調べない。
- 前節での置き方の組み合わせの検討では、駒の利き筋は考慮してなかったが、
パソコンで探索時は、すでに置いた駒の利き筋には駒を置かない。- 大駒の飛車/角を1枚置くと利き筋になるために駒を置く事ができないマスが
16個出来るので、残りマスは64個(9x9 - 16 -1)になる。最初に飛車/角を置けば
大幅に駒を置く事が出来るマスが減る。- 桂馬、角行以外は、駒の上が利き筋である。例えば歩兵をひとつおけば、
その上は 利き筋になり、駒が置けない。駒を下から上に並べていくと、
駒を置く事が出来るマスを 減らす効率が良い。- 香車は歩兵とみなした。香車0枚、歩兵22枚とした。もし香車を盤面の
一番上の列もしくは二番目の以外に置く解答が存在したとしても、
今回は全解探 索を行なうため、歩兵の上に空きマスが1個以上ある盤面
として表れるため。
投稿2015/10/25 07:18
編集2015/10/25 07:40
総合スコア1546
0
まず探索空間の広さを評価しておきましょう。
40個の駒を81個のセルに配置する方法は81!/41!通り。
ここから、同種の駒の存在を差し引いていきます。
81!/41!
/18!（歩）
/4!（香）
/4!（桂）
/4!（銀）
/4!（金）
/2（飛）
/2（角）
/2（王）
/2（鏡像解を差し引く。左右対称解があるかもしれないので厳密ではないけれど）
= 5.0 * 10^48
この探索空間の天文学的な広さから、4のアプローチは無理とわかります。すなわち、パターンを何らかの方法で記述することができたとしても、そのパターン数そのものが多すぎていかなる記憶装置にも収まりきらないからです。
よってアプローチは3の枝刈りと5の分散処理に絞られます。
枝刈りについて、即座に思いつく良い方法というのはないのですが、とにかく「早めにこけさせる」発想から利き筋面積の大きな駒から配置していくのが有効でしょうか。飛車・角は16マスが常に利きます。8マスの王や6マスの金より先に飛車角から置いていくことで「早めに失敗に気付」けます。
で、飛車と角から並べ始めるとして、この最初の4駒を並べる方法は81 * 64 * 47 * 30 = 7309440通りです。
多数のコンピュータに計算を分散するには何を基準に問題を分割するかが問題ですが、この課題ですと
これらをスタート地点にして全探索せよという問題が7309440個できているわけなので、これらを問題集として参加マシンに問題を配っていけばいいんじゃないですかね。
投稿2015/10/25 05:18
総合スコア5568
あ、最初の4駒の置き方は7309440よりもっと大きいですね。利き筋同士はかぶってもいいんだから。明らかなのは、最初の2駒の置き方が81*64 = 5184通りだってことだけですか。
ありがとうございます。
確かに不可の解を部分解を記憶するのはメモリが足りません。理解不足でした。
それでも、メモリが足りなくなった時に、利用頻度が少ないものをドロップするような方法はあるかと。ただこれもいちいちメモリが足りているか否かと知りべるので、オーバーヘッドになりますね。
＞利き筋面積の大きな駒から配置していく
これは、その通りです。ロジックとしては入れていませんが、初期設定ファイルに、駒の順番を調整することで、実現しています。初期起動時に調べれば、可能かと思います。
あなたの回答
tips
プレビュー
