Puzzle DE Programming

問題の説明

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

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

今回の問題は盤面を「六芒星」の形にしたペグ・ソリテアです。

上図では黒丸でペグを表し、白丸で空き場所を表しています。ペグは線に沿って移動することができます。最初に取り除いたペグ（白丸）と最後に残ったペグの位置が同じになる「補償型の解」の最短手順を求めてください。

ところで、この六芒星盤のペグ・ソリテアですが、柏木 或 さんのホームページ 裂け目の向こう の パズルトピア攻略 - [ダビデの星] によると、『ちなみにこの六芒星状の配置は芦ヶ原氏によるオリジナルです。かつては東洋ガラスから同名の製品が市販されていました。』 とのことです。

●プログラムの作成

今回は Python3 (ver 3.8.10) でプログラムを作ります。このパズルはペグの個数が少ないので、単純な「反復深化」で十分です。反復深化のプログラムは今までに何度も作っているので、説明は省略いたします。反復深化の説明は拙作のページ ペグ・ソリテア をお読みくださいませ。

• プログラムリスト

●ペグ・ソリテア・スターの解答

それでは、パズル「ペグ・ソリテア・スター」の解答を示します。

上図のように穴に番号をつけて、ペグの移動は番号で表すことにします。移動手順は 1 手を [ 移動元 (from), 移動先 (to) ] で表し、連続跳び越しの場合は [from, to1, to2, ..., to3] とします。

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

>>> s = time.time(); solver(7, 3, 0); print(time.time() - s)
----- 2 -----
----- 3 -----
----- 4 -----
----- 5 -----
----- 6 -----
----- 7 -----
[7, 0][1, 3][8, 2][12, 5, 7][11, 9][4, 10][0, 5, 12, 7, 0]
[7, 0][1, 3][8, 2][12, 5, 7][11, 9][4, 10][0, 7, 12, 5, 0]
[7, 0][1, 3][12, 7][4, 2, 10][8, 2][11, 3][0, 5, 12, 7, 0]
[7, 0][1, 3][12, 7][4, 2, 10][8, 2][11, 3][0, 7, 12, 5, 0]
[7, 0][1, 3][12, 7][4, 2, 10][11, 3][8, 2][0, 5, 12, 7, 0]
[7, 0][1, 3][12, 7][4, 2, 10][11, 3][8, 2][0, 7, 12, 5, 0]
[7, 0][1, 3][12, 7][8, 2, 10][4, 2][11, 3][0, 5, 12, 7, 0]
[7, 0][1, 3][12, 7][8, 2, 10][4, 2][11, 3][0, 7, 12, 5, 0]
[7, 0][1, 3][12, 7][8, 10][11, 9][4, 10, 8, 2][0, 5, 7, 0]
[7, 0][1, 3][12, 7][8, 10][11, 9][4, 10, 8, 2][0, 7, 5, 0]
[7, 0][12, 7][1, 3][4, 2, 10][8, 2][11, 3][0, 5, 12, 7, 0]
[7, 0][12, 7][1, 3][4, 2, 10][8, 2][11, 3][0, 7, 12, 5, 0]
[7, 0][12, 7][1, 3][4, 2, 10][11, 3][8, 2][0, 5, 12, 7, 0]
[7, 0][12, 7][1, 3][4, 2, 10][11, 3][8, 2][0, 7, 12, 5, 0]
[7, 0][12, 7][1, 3][8, 2, 10][4, 2][11, 3][0, 5, 12, 7, 0]
[7, 0][12, 7][1, 3][8, 2, 10][4, 2][11, 3][0, 7, 12, 5, 0]
[7, 0][12, 7][1, 3][8, 10][11, 9][4, 10, 8, 2][0, 5, 7, 0]
[7, 0][12, 7][1, 3][8, 10][11, 9][4, 10, 8, 2][0, 7, 5, 0]
[7, 0][12, 7][8, 10][1, 3][11, 9][4, 10, 8, 2][0, 5, 7, 0]
[7, 0][12, 7][8, 10][1, 3][11, 9][4, 10, 8, 2][0, 7, 5, 0]
[7, 0][12, 7][8, 10][1, 9, 3][11, 9][4, 10][0, 5, 12, 7, 0]
[7, 0][12, 7][8, 10][1, 9, 3][11, 9][4, 10][0, 7, 12, 5, 0]
[7, 0][12, 7][8, 10][11, 9][1, 3][4, 10, 8, 2][0, 5, 7, 0]
[7, 0][12, 7][8, 10][11, 9][1, 3][4, 10, 8, 2][0, 7, 5, 0]
[7, 0][12, 7][8, 10][11, 9, 3][1, 9][4, 10][0, 5, 12, 7, 0]
[7, 0][12, 7][8, 10][11, 9, 3][1, 9][4, 10][0, 7, 12, 5, 0]
[7, 0][12, 7][8, 10][11, 9, 3][4, 10][1, 9][0, 5, 12, 7, 0]
[7, 0][12, 7][8, 10][11, 9, 3][4, 10][1, 9][0, 7, 12, 5, 0]
28
0.10868620872497559

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

7 手で解くことができました。最短手順の一例を示します。

1: [7, 0]
2: [12, 7]
3: [8, 10]
4: [11, 9, 3]
5: [4, 10]
6: [1, 9]
7: [0, 7, 12, 5, 0]

「補償型の解」という条件がない場合でも最短手数は 7 手になります。また、最初に取り除くペグの位置が 2 の場合も最短手数は 7 手になります。

これではもの足りないという方のために、もうひとつ問題を出しましょう。下図のように中央のペグを取り除いた盤を考えてみます。

最初にどれかひとつペグを取り除いて、最後にペグがひとつ残る最短手順を求めてください。ただし、最初に取り除くペグの位置によっては解けない場合があります。ご注意くださいませ。

●ペグ・ソリテア・スターの偶奇性

偶奇性のお話 で説明しましたが、ペグ・ソリテアには「偶奇性」があります。ペグ・ソリテア・スターの場合、下図のように 3 つのグループに分けると、グループに属するペグ数と全体のペグ数の偶奇性を使って、解の有無をチェックすることができます。

最初にペグをどれかひとつ取り除いた状態で、3 つのグループのなかの 1 グループだけが全体のペグ数の偶奇性と一致していないと、そのペグ・ソリテアには解がありません。上図のペグ・ソリテア・スターの場合、最初にペグをひとつ取り除くと、そのグループのペグ数は偶数になりますが、ほかのグループは奇数のままですね。そして、全体のペグ数は偶数になるので偶奇性の条件を満たします。ただし、この関係を満たしているからといって、必ず解けるとはかぎらないことに注意してください。

それでは、ペグ・ソリテア・スター（その２）の場合はどうなるでしょうか。

最初に Group 0 のペグをひとつ取り除くと、3 つのグループすべて奇数になってしまいますね。この場合、解くことはできません。では、Group 1 のペグをひとつ取り除いてみましょう。すると、全体のペグ数は奇数になり、Group 0, 1 は偶数で Group 2 は奇数なので偶奇性の条件を満たします。同様に、Group 2 のペグをひとつ取り除いた場合も条件を満たします。

最初に Group 0 のペグを取り除くと解はありませんが、Group 1 か 2 のペグを取り除く場合は解があるかもしれません。実際に解いてみると、最短手順は次のようになりました。

この場合、「補償型の解」は存在しません。これも偶奇性からわかります。最後にひとつ残るペグは、全体のペグ数の偶奇性と一致しているグループになります。つまり、最初に取り除いたペグのグループが全体のペグ数の偶奇性と一致していることが、「補償型の解」が存在する条件になるのです。

上図の場合、取り除いたペグのグループと全体のペグ数の偶奇性は一致しません。したがって、最初に Group 1 のペグを取り除くと最後に残るペグは Group 2 になり、逆に Group 2 のペグを取り除くと最後に残るペグは Group 1 になるのです。

●プログラムリスト

#
# pegstar.py : ペグ・ソリティア・スター
#
#              Copyright (C) 2022 Makoto Hiroi
#

# 定数
MAX_JUMP = 11
SIZE = 13

# 跳び先表
jump_table = [
    [(2, 5), (3, 7)],            # 0
    [(2, 3), (5, 9)],            # 1
    [(3, 4), (5, 8), (6, 10)],   # 2
    [(2, 1), (6, 9), (7, 11)],   # 3
    [(3, 2), (7, 10)],           # 4
    [(2, 0), (6, 7), (9, 12)],   # 5
    [],                          # 6
    [(3, 0), (6, 5), (10, 12)],  # 7
    [(5, 2), (9, 10)],           # 8
    [(5, 1), (6, 3), (10, 11)],  # 9
    [(6, 2), (7, 4), (9, 8)],    # 10
    [(7, 3), (10, 9)],           # 11
    [(9, 5), (10, 7)],           # 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:
        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(from_, del_, to_):
    global cnt, HOLE
    cnt = 0
    board = [True] * SIZE
    # 初手を from_ -> to_ に限定
    board[from_] = False
    board[del_] = False
    HOLE = to_
    for i in range(2, MAX_JUMP + 1):
        print(f'----- {i} -----')
        dfs(board, 1, i, [(from_, to_)])
        if cnt > 0: break
    print(cnt)

#
# pegstar2.py : ペグ・ソリティア・スター２
#
#               Copyright (C) 2022 Makoto Hiroi
#

# 定数
MAX_JUMP = 10
SIZE = 12

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

# 手順の表示
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(2, MAX_JUMP + 1):
        print(f'----- {i} -----')
        dfs(board, 1, i, [(from_, to_)])
        if cnt > 0: break
    print(cnt)