このパズルでは通常の将棋のルールとは異なり
平成26年3月にネットで検索したところ、全解探索の成功例は発見出来なかっ たため今回パソコンを使い全解探索を試みたところ、パズルの解答は1860通り 存在する事を確認した。なお、後述するが左右反転の鏡像は除外している。
このパズルの解答は、大駒(飛車/角行)の位置が、以下の場合および、
左右反転させた鏡像の場合のみが知られています。
今回、探索を試みた発端は、「大駒の位置が上記以外で、解答があるか?」という疑問が発端です。
将棋の駒の数は以下の通りである。
飛車x2, 角行x2, 王将x2, 金将x4, 銀将x4, 桂馬x4, 香車x4, 歩兵x18合計40枚である。盤面は9x9=81マスあるので、全ての駒を置いた時の空きマスは 41である。
なので、駒の置き方の組合せは、
飛車x2, 角行x2, 王将x2, 金将x4, 銀将x4, 桂馬x4, 香車x4, 歩兵x18、空きマスx41の順列の総数を求めれば良い。
一般にAがa個、Bがb個、Cがc個あった場合の順列の総数は
順列の総数 = [(a+b+c)!] / (a! * b! * c!)なので
駒の置き方の組合せ = 81! / (2! * 2! * 2! * 4! * 4! * 4! * 4! * 18! * 41!) ≒ 10^49となる。これはいくらPCが早くても無理。
プログラム・プロムナード/Haskellプログラミング上記文献で述べられているペントミノと類似のデータ構造を用いた。
2002年8月号 計算機用ジグソーパズル
- 空白(0)
- 駒1枚の利き筋(1)
- 駒2枚の利き筋(2)
. . . . 省略
- 駒99枚の利き筋(99)
- 飛車(100)
- 角行(101)
. . . . 省略
- 歩兵(107)
まず、Aが2個、空き地(_)を4個(Bが3個 + Cが1個)を置くパターン全てを作る。
1. A A _ _ _ _次に 1. の空き地(_)に、Bを3個、空き地(_)を1個置くパターン全てを作る。
2. A _ A _ _ _
3. A _ _ A _ _
4. A _ _ _ A _
..省略
15. _ _ _ _ A A
1.1. A A B B B _つぎに、1.1の空き地にCを置く
1.2. A A B B _ B
1.3. A A B _ B B
1.4. A A _ B B B
1.1.1. A A B B B Cつぎに、1.2の空き地にCを置く
1.2.1. A A B B C Bという流れで生成する。
例えば盤面の自陣側(盤の下)から敵陣側(盤の上)に向かって、順列生成で4マスに歩を2 枚置く場合、次の4種類の順列が生成可能だが、
(←自陣側, 敵陣側→)ここで1.と5.の2番目の歩の位置は駒の利き筋なので、そこに駒を置かず、次のマス に置く。2,3,4は利き筋が影響しないため、順列生成そのままに駒を置く。
1. 歩 歩 ■ ■
2. 歩 ■ 歩 ■
3. 歩 ■ ■ 歩
4. ■ 歩 ■ 歩
5. ■ ■ 歩 歩
実際は次のように置く。×は利き筋。
1. 歩 × 歩 ■ ■と駒を置いている。
2. 歩 ■ 歩 ■
3. 歩 ■ ■ 歩
4. ■ 歩 ■ 歩
5. ■ ■ 歩 × 歩
例えば、前述「4.枝刈り」であげた手法で最初に飛車2枚/角行2枚を置けば、 (利き筋の影響にない)残りマスが27から45個の盤面が現れる。
残りマスが27個の例。
飛車角を除いた、残りの駒の数は36枚であるが、残りマスが27個のため、この場合は調べない。
次に、残りマスが45個の例
残りマスより駒の数が少ないので探索を続ける。
(補足)本戦略のような歩を例外に扱う方法を取らない場合は、歩を最後に並 べない方が良いようです。あくまで実装依存の話。
経験則によると、以下のように歩を最後に並べる順番で順列生成を行い駒を並べていくより
飛x2, 角x2, 王x2, 香x4, 金x4, 銀x4, 桂x4, 歩x18次のように桂馬/香車を後に並べて順列生成する方が2-3倍早いです。
飛x2, 角x2, 王x2, 金x4, 銀x4, 歩x18, 桂x4, 香x4さらに早い順列生成順番があるかもしれないが、調査は行っていない。
残念な事に大駒の位置は「2.一般に知られているパズルの解答」で述べた既知 の配置以外の解答は無かった…orz
検索結果の中には、以下のような歩兵が盤の一番上に3枚 以下の解答も得られた。
この場合、香車に置き換える事が出来無いため、除外する必要がある。
以下のような、歩兵が一番上に4枚以上の解のみ有効である。
無効な解答を除外すると、有効な解答は1860通りであった。
この盤面では、上部の歩の位置をずらすと、桂馬を追加で置く事ができる。 (すでに桂馬を4枚置いた後の処理なので、5枚目の桂馬を置く事ができるという事。)
今回得られた解答には上記状態は無い事を目視で確認後、念のため、大駒の位 置を既知の解答に固定し、歩兵(+香車)も含めて順列生成を行なう方法で実行したが 上記の状態は検出出来なかった。この計算は1時間12分程度必要だった。
以下の通り、「金将x2, 桂馬x2, 歩兵x15」が位置が固定される。
なお、香車無し(香車0枚、歩兵22枚)の場合は、追加で「歩兵x1」が位置固定になる。
脳内で何パターンか試してみたが、たしかに40枚しか駒を置くことができない ようである。
なお、上記Webが挙げているオリジナル文献はリンク切れになっている。
オリジナルの簡略化は駒の利き筋が少ないため、パズルの枝刈りがあまりでき ず、PCでそのまま検索すると、かなり時間がかかるようである。場合分けをき ちんとやれば、条件が減り手作業でも実行可能と考えるが、ミスをするに違い ないのでPCで手抜き調査を行った。
具体的には、簡略化の「縦」と「石」は使わず、オリジナルの「飛車」と「角行」と「桂馬」に戻し、 以下の条件でPCで配置可能な組み合わせの全解探索を実行した。
飛車x2, 角x2, 桂馬x4, 歩兵x32手元の計算機(Core-i7/860/1コア使用)で計算した所、30分程度で 解は13通り見付かった。左右反転の 鏡像は除く。
見付かった13通りの解を用いて、歩の32枚の位置に本来の駒(歩x18, 王x2, 金 x4, 銀x4, 香x4) を置いて行く探索すれば、「利かずの駒並べ」の全解探索自 体も2-3時間で終わるのではと思う(未調査)。