Puzzle DE Programming

問題の説明

今回はもう少しだけサイズを大きくしたペグ・ソリテアに挑戦してみましょう。

上図は「チャイニーズ・チェッカー」と呼ばれるペグ・ソリテアです。15 個の点が三角形に並んでいて、そこにペグを配置します。ペグは別のペグをひとつだけ跳び超えることで、任意の方向へ移動することができます。もちろん、着地する地点が空いていなければ、跳び越えることはできません。15 個のペグの中からひとつのペグを取り除き、最後にひとつだけペグが残る跳び方の最短手数を求めることにします。

●プログラムを作る

それではプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.01) です。まず、ペグの跳び先表を定義します。下図のように座標を定義すると、跳び先表は次のようになります。

リスト : 定数と跳び先表の定義

# 定数
MAX_JUMP = 13
SIZE = 15

# 跳び先表
jump_table = [
    [(1, 3), (2, 5)],                     # 0
    [(3, 6), (4, 8)],                     # 1
    [(4, 7), (5, 9)],                     # 2
    [(1, 0), (4, 5), (6, 10), (7, 12)],   # 3
    [(7, 11), (8, 13)],                   # 4
    [(2, 0), (4, 3), (8, 12), (9, 14)],   # 5
    [(3, 1), (7, 8)],                     # 6
    [(4, 2), (8, 9)],                     # 7
    [(4, 1), (7, 6)],                     # 8
    [(5, 2), (8, 7)],                     # 9
    [(6, 3), (11, 12)],                   # 10
    [(7, 4), (12, 13)],                   # 11
    [(7, 3), (8, 5), (11, 10), (13, 14)], # 12
    [(8, 4), (12, 11)],                   # 13
    [(9, 5), (13, 12)],
]

ペグが 13 回移動すると盤上のペグはひとつになるので、MAX_JUMP は 13 となります。

次は解を求める関数 solver() を修正します。

リスト : チャイニーズ・チェッカーの解法

def solver(from_, del_, to_):
    global cnt
    cnt = 0
    board = [True] * SIZE
    # 初手を from_ -> to_ に限定
    board[from_] = False
    board[del_] = False
    for i in range(1, MAX_JUMP + 1):
        print(f'----- {i} -----')
        dfs(board, 0, i, [(from_, to_)])
        if cnt > 0: break
    print(cnt)

引数 from_, del_, to_ で初手を指定するように変更しただけです。あとのプログラムは Hoppers とほとんど同じなので説明は割愛します。詳細は プログラムリスト をお読みください。

●実行結果

それでは最短手数を求めてみましょう。盤面の対称性から穴の位置は 0, 1, 3, 4 の 4 つを調べれば OK です。初手の選び方も対称性を考えると次の 6 通りに限定することができます。

(1) 3 -> 1 -> 0
(2) 6 -> 3 -> 1
(3) 8 -> 4 -> 1
(4) 0 -> 1 -> 3
(5) 5 -> 4 -> 3
(6) 11 -> 7 -> 4

それでは実行結果を示します。

    : 手数 : 総数
----+------+------
(1) :   9  :  950
(2) :   9  :  950
(3) :  --  :    0
(4) :   8  :  280
(5) :   9  : 1151
(6) :  10  :  154

辺の中央のペグを取り除き、最初に頂点のペグを移動する (4) が最短手数 (8 手) になりました。移動手順は 280 通り、その一部を以下に示します。

>>> solver(0,1,3)
----- 1 -----
----- 2 -----
----- 3 -----
----- 4 -----
----- 5 -----
----- 6 -----
----- 7 -----
----- 8 -----
[0, 3][6, 1][5, 0, 3, 5][9, 2][11, 4][13, 11][10, 12, 5][2, 9][14, 5, 3]
[0, 3][6, 1][5, 0, 3, 5][9, 2][12, 5][2, 9][10, 12][13, 11, 4][14, 5, 3]
[0, 3][6, 1][5, 0, 3, 5][9, 2][12, 5][10, 12][2, 9][13, 11, 4][14, 5, 3]

・・・省略・・・

[0, 3][6, 1][12, 3][14, 12][11, 13][9, 7][1, 6][2, 9][10, 3, 12, 14, 5, 3]
[0, 3][6, 1][12, 3][14, 12][11, 13][9, 7][2, 9][1, 6][10, 3, 5, 14, 12, 3]
[0, 3][6, 1][12, 3][14, 12][11, 13][9, 7][2, 9][1, 6][10, 3, 12, 14, 5, 3]
280

最後のペグの位置は 3 と 14 の 2 通りがあり、補償型の解があることがわかります。

●プログラムリスト

#
# peg15.py : チャイニーズ・チェッカー (ペグ・ソリティア)
#
#            Copyright (C) 2022 Makoto Hiroi
#

# 定数
MAX_JUMP = 13
SIZE = 15

# 跳び先表
jump_table = [
    [(1, 3), (2, 5)],                     # 0
    [(3, 6), (4, 8)],                     # 1
    [(4, 7), (5, 9)],                     # 2
    [(1, 0), (4, 5), (6, 10), (7, 12)],   # 3
    [(7, 11), (8, 13)],                   # 4
    [(2, 0), (4, 3), (8, 12), (9, 14)],   # 5
    [(3, 1), (7, 8)],                     # 6
    [(4, 2), (8, 9)],                     # 7
    [(4, 1), (7, 6)],                     # 8
    [(5, 2), (8, 7)],                     # 9
    [(6, 3), (11, 12)],                   # 10
    [(7, 4), (12, 13)],                   # 11
    [(7, 3), (8, 5), (11, 10), (13, 14)], # 12
    [(8, 4), (12, 11)],                   # 13
    [(9, 5), (13, 12)],
]

# 手順の表示
def print_move(xs):
    from_, to_ = xs[0]
    print(f'[{from_}, {to_}', end='')
    prev = to_
    for from_, to_ in xs[1:]:
        if prev == from_:
            print(f', {to_}', end='')
        else:
            print(f'][{from_}, {to_}', end='')
        prev = to_
    print(']')

# 反復深化
def dfs(board, jc, limit, move):
    global cnt
    if jc > limit: return
    if len(move) == MAX_JUMP:
        print_move(move)
        cnt += 1
    else:
        for from_ in range(SIZE):
            if not board[from_]: continue
            for del_, to_ in jump_table[from_]:
                if not board[del_] or board[to_]: continue
                board[from_] = False
                board[del_] = False
                board[to_] = True
                if move[-1][1] == from_:
                    newjc = jc
                else:
                    newjc = jc + 1
                move.append((from_, to_))
                dfs(board, newjc, limit, move)
                move.pop()
                board[from_] = True
                board[del_] = True
                board[to_] = False

def solver(from_, del_, to_):
    global cnt
    cnt = 0
    board = [True] * SIZE
    # 初手を from_ -> to_ に限定
    board[from_] = False
    board[del_] = False
    for i in range(1, MAX_JUMP + 1):
        print(f'----- {i} -----')
        dfs(board, 0, i, [(from_, to_)])
        if cnt > 0: break
    print(cnt)