質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.34%

将棋の駒の配置問題

解決済

回答 2

投稿

  • 評価
  • クリップ 4
  • VIEW 2,852

score 43

以下の私のブログに書いた将棋の駒の配置問題を解決したいと思います。
一応、私が作成したものはありますが、時間がかかって解けません。
言語は任意です。
以下のサイトの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.が実現できれば、非常に効果的と思われる。


□ お願い

   私のパソコンの能力と私のプログラミング能力では難しいので、この問題をどなたか解いていただきたい。

====


  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • yuba

    2015/10/25 14:19

    タグに「アルゴリズム」があるといいと思います。
    また、6×6盤の場合駒は何種何個になるのでしょう。

    キャンセル

  • artery

    2015/10/25 17:08

    ありがとうございます。
    >6×6盤の場合駒は何種何個になるのでしょう。
    行先の少ない駒を、配置可能な範囲で、ぎりぎりまで多数個配置した場合に、時間がかかります。

    キャンセル

回答 2

checkベストアンサー

+2

既に参照されているかもしれませんが、参考情報として、
将棋パズル(1)利かずの駒並べ: 詰将棋メモ
というページがありました。
ここからリンクされている
利かずの駒並べの全解探索
というページで、1860通りの解が見つかったそうです。

arteryさんが「プログラムのスペック」としてあげている様な一般化はせず、
「将棋の駒40枚すべてを9x9の盤面に、全ての駒同 士の利き筋(ききすじ)が
重ならないように並べる」を目指すために、
駒の特性を活かして、以下のような枝刈りを行ったそうです。
1. 全ての駒の利き筋は左右対象のため、左右反転させた鏡像は調べない。
2. 前節での置き方の組み合わせの検討では、駒の利き筋は考慮してなかったが、 
   パソコンで探索時は、すでに置いた駒の利き筋には駒を置かない。
3. 大駒の飛車/角を1枚置くと利き筋になるために駒を置く事ができないマスが
    16個出来るので、残りマスは64個(9x9 - 16 -1)になる。最初に飛車/角を置けば
    大幅に駒を置く事が出来るマスが減る。
4. 桂馬、角行以外は、駒の上が利き筋である。例えば歩兵をひとつおけば、
    その上は 利き筋になり、駒が置けない。駒を下から上に並べていくと、
    駒を置く事が出来るマスを 減らす効率が良い。
5. 香車は歩兵とみなした。香車0枚、歩兵22枚とした。もし香車を盤面の
    一番上の列もしくは二番目の以外に置く解答が存在したとしても、
    今回は全解探 索を行なうため、歩兵の上に空きマスが1個以上ある盤面
    として表れるため。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/10/25 17:18

    ご指摘のサイトは知りませんでした。ありがとうございます。
    解答数が分かったのは心強いです。ずいぶんとあるんですね。

    キャンセル

  • 2015/10/25 22:51

    知らなかったのであれば、回答して良かったです。

    アイデアでしか無いですが、不可の解でなく、可の解を記憶することで、
    このパターンになったら、解はこれしかない、というような判定はできないでしょうか?

    もう少し考えてみます。

    キャンセル

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 14:25

    あ、最初の4駒の置き方は7309440よりもっと大きいですね。利き筋同士はかぶってもいいんだから。明らかなのは、最初の2駒の置き方が81*64 = 5184通りだってことだけですか。

    キャンセル

  • 2015/10/25 17:15

    ありがとうございます。
    確かに不可の解を部分解を記憶するのはメモリが足りません。理解不足でした。
    それでも、メモリが足りなくなった時に、利用頻度が少ないものをドロップするような方法はあるかと。ただこれもいちいちメモリが足りているか否かと知りべるので、オーバーヘッドになりますね。
    >利き筋面積の大きな駒から配置していく
    これは、その通りです。ロジックとしては入れていませんが、初期設定ファイルに、駒の順番を調整することで、実現しています。初期起動時に調べれば、可能かと思います。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る