Puzzle DE Programming

問題の説明

騎士 (ナイト) はチェスの駒のひとつで、下図に示すように将棋の桂馬の動きを前後左右にとることができます。今回は黒騎士 ● と白騎士 ○ の位置を交換するパズルです。それでは問題です。

                              図 : 騎士の交換

●プログラムの作成

それではプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。次の図を見てください。

図 (A) のように、盤面の各マスに番号を付けて表します。すると、騎士の移動は図 (B) のようなグラフで表すことができます。START の局面は図 (C) のようになるので、黒騎士と白騎士を交換できることは簡単にわかりますが、最短手数となる移動手順を求めるのが今回の問題です。

改訂前のプログラムでは、最初に反復深化と下限値枝刈り法で解きましたが、とても時間がかかりました。上図を見ればおわかりのように、巡回路 (たとえば 0 - 7 - 2 - 3 - 10 - 5 - 0 など) をぐるぐると回る手順が生成されることがあるため、反復深化とは相性がとても悪いのです。そこで、今回は幅優先探索で解くことにします。

このパズルの場合、 12 マスに 3 個の黒騎士を置き、残りの 9 マスに白騎士を置くわけですから、盤面の総数は次のようになります。

12Ｃ3 * 9Ｃ3 = 220 * 84 = 18480 通り

それほど多くないので、単純な幅優先探索で十分でしょう。盤面は一次元配列 (Python のタプル) を使って表します。隣接リストの定義は次のようになります。

リスト : 大域変数の定義

# 定数
SIZE = 12
S = 0
B = 1
W = 2

# 隣接リスト
adjacent = [
    [5, 7],      # 0
    [6, 8],      # 1
    [3, 7],      # 2
    [2, 8, 10],  # 3
    [9, 11],     # 4
    [0, 6, 10],  # 5
    [1, 5, 11],  # 6
    [0, 2],      # 7
    [1, 3, 9],   # 8
    [4, 8],      # 9
    [3, 5],      # 10
    [4, 6],      # 11
]

# 問題
start = (
    B, B, B, S, S, S, S, S, S, W, W, W
)

goal = (
    W, W, W, S, S, S, S, S, S, B, B, B
)

S が空き場所 (0)、B が黒駒 (1)、W が白駒 (2) を表します。adjacent は隣接リストです。start と goal は START と GOAL の盤面を表します。

幅優先探索で解を求める関数 bfs() は次のようになります。

リスト : 幅優先探索

def bfs(start, goal):
    queue = deque()
    queue.append(start)
    check = {}
    check[start] = ()
    while len(queue) > 0:
        b = queue.popleft()
        if b == goal:
            print_moves(b, check)
            return
        for k in range(SIZE):
            if not b[k]: continue
            for s in adjacent[k]:
                if b[s]: continue
                a = move_piece(b, k, s)
                if a in check: continue
                queue.append(a)
                check[a] = b

キューは Python の標準ライブラリ collections のクラス deque を使い、同一局面のチェックには Python の辞書を使います。変数 queue に deque() をセットし、変数 check に辞書をセットします。check には 1 手前の盤面をセットします。start の 1 手前の盤面は無いので、空のタプルをセットします。check を使って移動手順を表示することができます。

while ループで、キューにデータがある間は探索を続けます。キューから盤面を取り出して変数 b にセットします。b が goal と等しい場合は、解を見つけたので関数 print_moves() で手順を表示します。そうでなければ、for ループで盤面から騎士がいる位置 k を求めます。そして、隣接リストから移動先 s を求め、s が空き場所であれば騎士を動かします。

関数 move_piece() は移動後の盤面を返すので、それを変数 a にセットします。次に、演算子 in で a が check にあるか調べます。同一の盤面がなければ a は新しい盤面です。queue に a を追加して、check[a] に b をセットします。あとは今まで作成した幅優先探索のプログラムとほとんど同じなので、説明は不要でしょう。詳細は プログラムリスト をお読みください。

●実行結果 (1)

それでは実行してみましょう。

>>> s = time.time(); bfs(start, goal); time.time() - s
(1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 2, 2)
(0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 2, 2)
(0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 2, 2)
(0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 2, 2)
(0, 1, 0, 2, 0, 1, 0, 0, 1, 2, 0, 2)
(0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 0, 2)
(0, 1, 2, 0, 0, 0, 0, 0, 1, 2, 1, 2)
(0, 1, 2, 1, 0, 0, 0, 0, 0, 2, 1, 2)
(0, 1, 2, 1, 0, 0, 0, 0, 2, 0, 1, 2)
(0, 1, 2, 1, 0, 0, 2, 0, 2, 0, 1, 0)
(0, 1, 2, 1, 0, 2, 0, 0, 2, 0, 1, 0)
(0, 0, 2, 1, 0, 2, 1, 0, 2, 0, 1, 0)
(2, 0, 2, 1, 0, 0, 1, 0, 2, 0, 1, 0)
(2, 0, 2, 1, 0, 0, 0, 0, 2, 0, 1, 1)
(2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 1, 1)
(2, 2, 2, 0, 0, 0, 0, 0, 1, 0, 1, 1)
(2, 2, 2, 0, 0, 0, 0, 0, 0, 1, 1, 1)
0.11851143836975098

実行環境 : Python3 (ver 3.8.10), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz

 1 1 1
 0 0 0
 0 0 0
 2 2 2
[START]

 0 1 1    0 1 0    0 1 0    0 1 0    0 1 2    0 1 2    0 1 2    0 1 2
 0 0 1    1 0 1    0 0 1    2 0 1    0 0 1    0 0 0    1 0 0    1 0 0
 0 0 0    0 0 0    0 0 1    0 0 1    0 0 1    0 0 1    0 0 0    0 0 2
 2 2 2    2 2 2    2 2 2    2 0 2    2 0 2    2 1 2    2 1 2    0 1 2

 0 -> 5   2 -> 3   3 -> 8   10 -> 3  3 -> 2   5 -> 10  8 -> 3   9 -> 8

 0 1 2    0 1 2    0 0 2    2 0 2    2 0 2    2 2 2    2 2 2    1 1 1
 1 0 0    1 0 2    1 0 2    1 0 0    1 0 0    1 0 0    0 0 0    0 0 0
 2 0 2    0 0 2    1 0 2    1 0 2    0 0 2    0 0 0    0 0 1    0 0 0
 0 1 0    0 1 0    0 1 0    0 1 0    0 1 1    0 1 1    0 1 1    2 2 2
                                                                [GOAL]
 11 -> 6  6 -> 5   1 -> 6   5 -> 0   6 -> 11  8 -> 1   3 -> 8   8 -> 9

最短手数は 16 手、実行時間は約 0.12 秒でした。

●最長手数の局面

次は最長手数となる局面を求めてみましょう。まず、START から騎士を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から騎士を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ延ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。

プログラムは次のようになります。

リスト : 最長手数の局面

def solver_max():
    xs = [start]
    check = {}
    check[start] = True
    move = 0
    while True:
        ys = []
        for b in xs:
            for k in range(SIZE):
                if not b[k]: continue
                for s in adjacent[k]:
                    if b[s]: continue
                    a = move_piece(b, k, s)
                    if a in check: continue
                    ys.append(a)
                    check[a] = True
        if not ys: break
        xs = ys
        move += 1
    print(f'最長手数 = {move}, 個数 = {len(xs)}')
    for b in xs: print(b)
    print('状態の総数 =', len(check))

リスト xs は move 手で生成した盤面と空き場所の位置を格納します。リスト check は同一局面のチェックに使用します。最初に盤面 start を xs と check に追加します。移動手順は求めないので、check には True をセットします。あとは while ループで move + 1 手の盤面を生成します。

リスト ys に move + 1 手の盤面を格納します。for ループで xs から盤面を一つずつ取り出し、次の for ループで、盤面 b から騎士がいる位置 k を求めます。騎士がいて移動先 s が空き場所ならば、move_piece() で旗幟を動かして盤面 a を生成します。同一局面がなければ、ys と check に a を追加します。

for ループを終了したら、ys にデータがあるかチェックします。ys が空リストならば xs が最長手数の盤面になります。break で while ループを脱出して、最長手数と個数、盤面、状態の総数を出力します。そうでなければ、xs を ys にセットし、move を +1 して探索を続けます。

あとは今まで作成した最長手数の局面を求めるのプログラムとほとんど同じなので、説明は不要でしょう。詳細は プログラムリスト をお読みください。

●実行結果 (2)

結果は次のようになりました。

>>> s = time.time(); solver_max(); time.time() - s
最長手数 = 22, 個数 = 3
(0, 0, 2, 2, 1, 0, 0, 2, 1, 1, 0, 0)
(2, 0, 0, 0, 1, 2, 1, 2, 0, 0, 0, 1)
(2, 0, 2, 0, 1, 0, 0, 2, 0, 1, 0, 1)
状態の総数 = 18480
0.11668753623962402

最長手数は 22 手で局面は 3 通りありました。上図の (B) と (C) は左右対称なので、対称解を除くと 2 通りになります。実行時間は約 0.12 秒でした。ちなみに、生成した全局面は 18480 個になりました。しがたって、このパズルでは騎士をランダムに配置しても、必ず START の局面に到達できることがわかります。

●プログラムリスト

#
# knightchg.py : 騎士の交換
#
#                Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque

# 定数
SIZE = 12
S = 0
B = 1
W = 2

# 隣接リスト
adjacent = [
    [5, 7],      # 0
    [6, 8],      # 1
    [3, 7],      # 2
    [2, 8, 10],  # 3
    [9, 11],     # 4
    [0, 6, 10],  # 5
    [1, 5, 11],  # 6
    [0, 2],      # 7
    [1, 3, 9],   # 8
    [4, 8],      # 9
    [3, 5],      # 10
    [4, 6],      # 11
]

# 問題
start = (
    B, B, B, S, S, S, S, S, S, W, W, W
)

goal = (
    W, W, W, S, S, S, S, S, S, B, B, B
)

# 騎士の移動
def move_piece(b, n, s):
    a = list(b)
    a[s] = a[n]
    a[n] = S
    return tuple(a)

# 手順の表示
def print_moves(b, table):
    if b:
        print_moves(table[b], table)
        print(b)

# 幅優先探索
def bfs(start, goal):
    queue = deque()
    queue.append(start)
    check = {}
    check[start] = ()
    while len(queue) > 0:
        b = queue.popleft()
        if b == goal:
            print_moves(b, check)
            return
        for k in range(SIZE):
            if not b[k]: continue
            for s in adjacent[k]:
                if b[s]: continue
                a = move_piece(b, k, s)
                if a in check: continue
                queue.append(a)
                check[a] = b

# 最長手数の局面を求める
def solver_max():
    xs = [start]
    check = {}
    check[start] = True
    move = 0
    while True:
        ys = []
        for b in xs:
            for k in range(SIZE):
                if not b[k]: continue
                for s in adjacent[k]:
                    if b[s]: continue
                    a = move_piece(b, k, s)
                    if a in check: continue
                    ys.append(a)
                    check[a] = True
        if not ys: break
        xs = ys
        move += 1
    print(f'最長手数 = {move}, 個数 = {len(xs)}')
    for b in xs: print(b)
    print('状態の総数 =', len(check))