利かずの駒並べの全解探索

利かずの駒並べの全解探索
松元隆二
H26/4/17(初版)
H26/4/19(更新)
H26/6/20(更新)

1. はじめに

将棋パズルのひとつに、将棋の駒40枚すべてを9x9の盤面に、全ての駒同士の利き筋(ききすじ)が重ならないように並べるパズルがあります。「利かずの駒並べ」と呼ばれる事が多いようです。チェスのエイトクイーンと類似のパズルです。

このパズルでは通常の将棋のルールとは異なり

二歩を置いても良い。
行き先の無い駒を置いても良い。(後ろに戻れない桂馬や香車を一番上に置いて良い。)
駒を全て同じ向きに並べる。

とする場合が多い。

平成26年3月にネットで検索したところ、全解探索の成功例は発見出来なかったため今回パソコンを使い全解探索を試みたところ、パズルの解答は1860通り存在する事を確認した。なお、後述するが左右反転の鏡像は除外している。

2. 一般に知られているパズルの解答

(具体的なパズルの解答例を挙げて説明した方が説明が容易ですが、これからパズルを楽しむ方が誤って読んでしまい、興を削ぐといけないため、説明のために必要な最低限の駒の配置のみ挙げる。具体的な解答例は後半に一つ挙げている。)

このパズルの解答は、大駒(飛車/角行)の位置が、以下の場合および、

左右反転させた鏡像の場合のみが知られています。

今回、探索を試みた発端は、「大駒の位置が上記以外で、解答があるか？」という疑問が発端です。

3. 駒の置き方の組合せ

駒の利き筋を考慮せずに、駒の置き方の組合せ数がいくつあるか数えてみる。

将棋の駒の数は以下の通りである。

飛車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が早くても無理。

4. 枝刈り

前節でのべたように、全ての駒の置き方を調べると10^49個もあり無理なため、あきらかに無駄な場合は調べない(枝刈り)。

全ての駒の利き筋は左右対象のため、左右反転させた鏡像は調べない。
前節での置き方の組み合わせの検討では、駒の利き筋は考慮してなかったが、パソコンで探索時は、すでに置いた駒の利き筋には駒を置かない。
大駒の飛車/角を1枚置くと利き筋になるために駒を置く事ができないマスが 16個出来るので、残りマスは64個(9x9 - 16 -1)になる。最初に飛車/角を置けば大幅に駒を置く事が出来るマスが減る。
桂馬、角行以外は、駒の上が利き筋である。例えば歩兵をひとつおけば、その上は利き筋になり、駒が置けない。駒を下から上に並べていくと、駒を置く事が出来るマスを減らす効率が良い。
香車は歩兵とみなした。香車0枚、歩兵22枚とした。もし香車を盤面の一番上の列もしくは二番目の以外に置く解答が存在したとしても、今回は全解探索を行なうため、歩兵の上に空きマスが1個以上ある盤面として表れるため。

などが考えつきました。

5. プログラミング

基本アイデアは

プログラム・プロムナード／Haskellプログラミング
 2002年8月号計算機用ジグソーパズル

上記文献で述べられているペントミノと類似のデータ構造を用いた。

使用言語はC++
盤面のデータ構造として、2次元配列は用いず、1次元配列を用いた。具体的な実装方法は上記文献を参照してほしい。
マスの状態として以下の状態を作った。括弧()内の数字は割り当てた数字。
- 空白(0)
- 駒1枚の利き筋(1)
- 駒2枚の利き筋(2)
. . . . 省略
- 駒99枚の利き筋(99)
- 飛車(100)
- 角行(101)
. . . . 省略
- 歩兵(107)
盤面(9x9)の回りに8マスの(アルゴリズム用語での)番兵を設けた。つまりデータ構造としては縦と横が25マス(9+8+8)の盤面とした。一次元配列としては25x25=625。番兵の領域は「駒1枚の利き筋(1)」とした。

6. 同じものを含む順列の生成

例として駒が3種類(A,B,C)で、Aが2個, Bが3個, Cが1個の順列生成を挙げる

まず、Aが2個、空き地(_)を4個(Bが3個 + Cが1個)を置くパターン全てを作る。

1.　A A _ _ _ _
2.　A _ A _ _ _
3.　A _ _ A _ _
4.　A _ _ _ A _
..省略
15. _ _ _ _ A A

次に 1. の空き地(_)に、Bを3個、空き地(_)を1個置くパターン全てを作る。

1.1. A A B B B _
1.2. A A B B _ B
1.3. A A B _ B B
1.4. A A _ B B B

つぎに、1.1の空き地にCを置く

1.1.1. A A B B B C

つぎに、1.2の空き地にCを置く

1.2.1. A A B B C B

という流れで生成する。

プログラム例(C++, コメントはUTF-8)

7. さらなる高速化

順列生成は、深さ優先探索で実装しているが、順列生成部と駒を置く作業を同じ関数で行い、省力化。
盤面で駒を外す作業を可能にし、バックトラック時に駒を外す操作を行っている。これにより深さ優先探索時に盤面を複数保持する必要がなくなった。マスの状態で「駒1枚の利き筋」と「駒2枚の利き筋」を区別しているのはこれが理由。
順列生成の時点で駒の利き筋のマスは除外している。
例えば盤面の自陣側(盤の下)から敵陣側(盤の上)に向かって、順列生成で4マスに歩を2 枚置く場合、次の4種類の順列が生成可能だが、
(←自陣側, 敵陣側→)
1. 歩歩 ■ ■
2. 歩 ■ 歩 ■
3. 歩 ■ ■ 歩
4. ■ 歩 ■ 歩
5. ■ ■ 歩歩

ここで1.と5.の2番目の歩の位置は駒の利き筋なので、そこに駒を置かず、次のマスに置く。2,3,4は利き筋が影響しないため、順列生成そのままに駒を置く。
実際は次のように置く。×は利き筋。
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
さらに早い順列生成順番があるかもしれないが、調査は行っていない。

8. 結果

以下の環境で全解探索を行った。

CPU: Quad Core / Intel Core i7-860 / 2.8GHz, 1コアのみ使用
OS: CentOS 6.5/64bit
言語: g++ 4.4.7
左右反転させた鏡像は調べない。
香車は歩兵とみなし、香車0枚、歩兵22枚とする。
具体的には次の駒の数。
飛x2, 角x2, 王x2, 金x4, 銀x4, 桂x4, 歩x22

上記環境で実行した所、計算時間50時間程度で、2520通りのパズルの解答が得られた。

残念な事に大駒の位置は「2.一般に知られているパズルの解答」で述べた既知の配置以外の解答は無かった…orz

例外の処理

この検索では歩兵を置く時に香車は歩兵とみなしていたため、歩兵4枚を香車に戻す必要がある。
検索結果の中には、以下のような歩兵が盤の一番上に3枚以下の解答も得られた。

この場合、香車に置き換える事が出来無いため、除外する必要がある。
以下のような、歩兵が一番上に4枚以上の解のみ有効である。

無効な解答を除外すると、有効な解答は1860通りであった。
歩兵を並べる段階で順列生成を行わず、置く事が可能なマスに順次置いているため、以下の状態が生成される可能性がある。

この盤面では、上部の歩の位置をずらすと、桂馬を追加で置く事ができる。 (すでに桂馬を4枚置いた後の処理なので、5枚目の桂馬を置く事ができるという事。)

今回得られた解答には上記状態は無い事を目視で確認後、念のため、大駒の位置を既知の解答に固定し、歩兵(+香車)も含めて順列生成を行なう方法で実行したが上記の状態は検出出来なかった。この計算は1時間12分程度必要だった。