Puzzle DE Programming

パズルの説明

ペグ・ソリテアは、盤上に配置されたペグ（駒）を、最後にはひとつ残るように取り除いていく、古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。

• ペグは隣にあるペグをひとつだけ跳び越して、空いている場所へ着地します。
• 跳び越されたペグは盤上から取り除かれます。
• 移動方向は、ふつう縦横のみの 4 方向ですが、 ルールによっては斜め方向の移動を許す場合もあります。
• 同じペグの連続跳び越しは 1 手と数えます。

盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。

  図 : ペグ・ソリテア 33 穴英国盤

33 のマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。上図では、ペグを ● で空き位置を ○ で表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、盤の種類によっては、ペグを取り除く位置 (空き位置) によって、解けない場合もあるので注意してください。

参考文献 6 によると、最初の空き位置と最後に残ったペグの位置が同じになることを「補償型の解」といい、最初の空き位置が盤の中央で、なおかつ補償型の解がある場合を「中央補償型の解」というそうです。33 穴英国盤には、中央補償型の解があるそうです。

ペグ・ソリテアの場合、昔から補償型や中央補償型の解の最小手数を求めることが行われてきました。33 穴英国盤のように、数が多いと解くのが大変なので、サイズを小さくした簡単なペグ・ソリテアをコンピュータで解いてみましょう。

●Hoppers

Hoppers は芦ヶ原伸之氏が考案されたペグ・ソリテアです。次の図を見てください。

     図 : Hoppers

Hoppers は穴を 13 個に減らしていて、遊ぶのに手頃な大きさになっています。上図に示したように、最初に中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めることにします。最小手数といえば「幅優先探索」ですが、連続跳びの処理が面倒になりそうなので、ここは「深さ優先探索」を採用することにします。

プログラムのポイントは、ペグを跳び越すときに手数も同時に数えていくことです。直前に動かしたペグと違うペグを動かすときは手数をカウントし、同じペグを動かすときは手数をカウントしません。そして、手数の上限値を定めて探索を行います。たとえば、最初は 5 手を限度に探索し、見つからなければ上限値を 6 手に増やす、というように 1 手ずつ増やしながら探索するのです。

このような探索を「反復深化」といいます。幅優先探索が使えない問題には有効な探索手法のひとつです。反復深化の詳しい説明は拙作のページ Algorithms with Python 集合、グラフ、経路の探索 をお読みください。今回は Python3 (ver 3.8.10) でプログラムを作ることにします。

●跳び先表とペグの移動

それでは、プログラムを作りましょう。今回は Hoppers の盤面を配列 (Python のリスト) で表すことにします。リストの要素は真偽値です。ペグがある状態を True で、ペグがない状態を False で表します。ベクタの添字と盤面の対応は、下図を見てください。

            図 : Hoppers の盤面

ペグの移動は跳び先表を用意すると簡単です。次のプログラムを見てください。

リスト : 定数と跳び先表

# 定数
MAX_JUMP = 11
HOLE = 6
SIZE = 13

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

ペグの跳び先表は jump_table で定義します。jump_table の要素はリストであることに注意してください。中のリストの要素は、跳び越されるペグの位置と跳び先の位置を格納したタプルです。たとえば、0 番の位置にあるペグは、1 番を跳び越して 2 番へ移動する場合と、3 番を跳び越して 6 番へ移動する場合と、5 番を跳び越して 10 番へ移動する場合の 3 通りがあります。これをタプル (1, 2), (3, 6), (5, 10) で表しています。

●反復深化による Hoppers の解法

あとは単純な反復深化で最短手順を求めます。プログラムは次のようになります。

リスト : 反復深化による解法

def dfs(board, jc, limit, move):
    global cnt
    if jc > limit: return
    if len(move) == MAX_JUMP:
        if board[HOLE]:
            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():
    global cnt
    cnt = 0
    board = [True] * SIZE
    # 初手を 0 -> 6 に限定
    board[0] = False
    board[3] = False
    for i in range(2, MAX_JUMP + 1):
        print(f'----- {i} -----')
        dfs(board, 1, i, [(0, 6)])
        if cnt > 0: break
    print(cnt)

反復深化の処理は関数 dfs() で行います。引数 board が盤面、jc がペグが跳んだ回数、limit が反復深化の上限値、move が移動手順を格納するリストで、要素はタプル (移動元, 移動先) です。

ペグ・ソリテアを反復深化で解く場合、上限値 limit に達していても連続跳びによりペグを移動できることに注意してください。最初に、jc をチェックして limit 以下であればペグを移動します。Hoppers の場合、ペグの総数は 12 個なので、MAX_JUMP (11) 回ペグを移動すると、残りのペグは 1 個になります。解を見つけたら関数 print_move() で手順を表示して、見つけた解の個数 cnt を +1 します。

そうでなければペグを移動します。for ループの変数 from_ が動かすペグの位置を表します。まず from_ の位置にペグがあることを確認します。それから、跳び先表から跳び越されるペグの位置と跳び先の位置を for ループで順番に取り出して、変数 del_, to_ にセットます。del_ の位置にペグがあり to_ の位置にペグがなければ、from_ のペグを to_ へ移動することができます。

ペグが移動できるできる場合、ペグを動かして dfs() を再帰呼び出しします。そして、このプログラムのポイントが連続跳びのチェックをするところです。直前に移動した場所からペグを動かすときは、連続跳びと判断することができます。つまり、move の末尾のタプルの 1 番目の要素 (move[-1][1]) が from_ と等しい場合は、跳んだ回数 jc を増やしません。異なる場合は jc の値を +1 します。再帰呼び出しから戻ってきたらペグを元に戻します。

あとは反復深化の上限値を増やしながら dfs() を呼び出します。for ループの変数 i が上限値を表します。最初の移動は、四隅にあるペグのひとつを中央に動かす手順しかありません。そこで、最初は 0 のペグを 6 へ動かすことに決めて、その状態から探索を開始します。cnt が 0 でなければ、解を見つけたので反復深化を終了します。

最後に手順を表示する関数 print_move() を作ります。

リスト : 手順の表示

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(']')

移動手順は 1 手を [from, to] で表し、連続跳びの場合は [from, to1, to2, ..., toN] とします。1 手前の跳び先の位置を変数 prev にセットしておいて、それと動かすペグの位置が同じであれば連続跳びです。跳び先の位置を prev にセットして、それを表示します。違うペグが跳ぶ場合は、] [ を表示してから動かすペグの位置と跳び先の位置を表示します。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト をお読みください。

●実行結果

これでプログラムは完成です。それでは実行してみましょう。

>>> from peg13 import *
>>> solver()
----- 2 -----
----- 3 -----
----- 4 -----
----- 5 -----
----- 6 -----
----- 7 -----
[0, 6][9, 3][2, 0, 6][11, 1][10, 0, 2, 6][8, 4][12, 2, 6]
[0, 6][9, 3][2, 0, 6][11, 1][10, 6][4, 8][12, 2, 0, 10, 6]
[0, 6][9, 3][2, 0, 6][11, 1][12, 2, 6][8, 4][10, 0, 2, 6]
[0, 6][9, 3][2, 6][8, 4][10, 0, 2, 6][7, 5][12, 10, 0, 6]
[0, 6][9, 3][2, 6][8, 4][10, 0, 2, 6][11, 1][12, 2, 0, 6]
[0, 6][9, 3][2, 6][8, 4][10, 0, 6][7, 5][12, 10, 0, 2, 6]
[0, 6][9, 3][2, 6][8, 4][12, 2, 0, 6][5, 7][10, 12, 2, 6]
[0, 6][9, 3][2, 6][8, 4][12, 2, 0, 6][11, 1][10, 0, 2, 6]
[0, 6][9, 3][2, 6][8, 4][12, 2, 6][5, 7][10, 12, 2, 0, 6]
[0, 6][9, 3][10, 0, 6][7, 5][2, 0, 10, 6][4, 8][12, 10, 6]
[0, 6][9, 3][10, 0, 6][7, 5][2, 6][8, 4][12, 10, 0, 2, 6]
[0, 6][9, 3][10, 0, 6][7, 5][12, 10, 6][4, 8][2, 0, 10, 6]
[0, 6][9, 3][10, 6][4, 8][2, 0, 6][11, 1][12, 2, 0, 10, 6]
[0, 6][9, 3][10, 6][4, 8][2, 0, 10, 6][7, 5][12, 10, 0, 6]
[0, 6][9, 3][10, 6][4, 8][2, 0, 10, 6][11, 1][12, 2, 0, 6]
[0, 6][9, 3][10, 6][4, 8][12, 10, 0, 6][1, 11][2, 12, 10, 6]
[0, 6][9, 3][10, 6][4, 8][12, 10, 0, 6][7, 5][2, 0, 10, 6]
[0, 6][9, 3][10, 6][4, 8][12, 10, 6][1, 11][2, 12, 10, 0, 6]
18

7 手で解くことができました。解は全部で 18 通りになりました。最近のパソコンは高性能なので、穴の数が少ない盤面であれば、単純な反復深化でも高速に解くことができるようです。

●プログラムリスト

#
# peg13.py : Hoppers (ペグ・ソリティア)
#
#            Copyright (C) 2022 Makoto Hiroi
#

# 定数
MAX_JUMP = 11
HOLE = 6
SIZE = 13

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

# 手順の表示
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:
        if board[HOLE]:
            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():
    global cnt
    cnt = 0
    board = [True] * SIZE
    # 初手を 0 -> 6 に限定
    board[0] = False
    board[3] = False
    for i in range(2, MAX_JUMP + 1):
        print(f'----- {i} -----')
        dfs(board, 1, i, [(0, 6)])
        if cnt > 0: break
    print(cnt)