ペグ・ソリテアは、盤上に配置されたペグ (駒) を最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動して取り除くことができます。
今回の問題は盤面を「六芒星」の形にしたペグ・ソリテアです。
○
／ ＼
●───●───●───●
＼ ／ ＼ ／ ＼ ／
●───●───●
／ ＼ ／ ＼ ／ ＼
●───●───●───●
＼ ／
●
問題 : ペグ・ソリテア・スター
上図では黒丸でペグを表し、白丸で空き場所を表しています。ペグは線に沿って移動することができます。最初に取り除いたペグ（白丸）と最後に残ったペグの位置が同じになる「補償型の解」の最短手順を求めてください。
ところで、この六芒星盤のペグ・ソリテアですが、柏木 或 さんのホームページ「裂け目の向こう」の「パズルトピア攻略 - [ダビデの星]」によると、『ちなみにこの六芒星状の配置は芦ヶ原氏によるオリジナルです。かつては東洋ガラスから同名の製品が市販されていました。』 とのことです。
今回は Python3 (ver 3.8.10) でプログラムを作ります。このパズルはペグの個数が少ないので、単純な「反復深化」で十分です。反復深化のプログラムは今までに何度も作っているので、説明は省略いたします。反復深化の説明は拙作のページ「ペグ・ソリテア」をお読みくださいませ。
○ ０
／ ＼ ／ ＼
●───●───●───● １───２───３───４
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
●───●───● ５───６───７
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
●───●───●───● ８───９───10───11
＼ ／ ＼ ／
● 12
図 : ペグ・ソリテア・スター
それでは、パズル「ペグ・ソリテア・スター」の解答を示します。上図のように穴に番号をつけて、ペグの移動は番号で表すことにします。移動手順は 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 つのグループに分けると、グループに属するペグ数と全体のペグ数の偶奇性を使って、解の有無をチェックすることができます。
● ０
／ ＼ ／ ＼ Group 0 : 7
●───●───●───● ０───１───２───０
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ Group 1 : 3
●───●───● ２───０───１
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ Group 2 : 3
●───●───●───● ０───１───２───０
＼ ／ ＼ ／ Total : 13
● ０
図 : ペグ・ソリテア・スターの偶奇性
最初にペグをどれかひとつ取り除いた状態で、3 つのグループのなかの 1 グループだけが全体のペグ数の偶奇性と一致していないと、そのペグ・ソリテアには解がありません。上図のペグ・ソリテア・スターの場合、最初にペグをひとつ取り除くと、そのグループのペグ数は偶数になりますが、ほかのグループは奇数のままですね。そして、全体のペグ数は偶数になるので偶奇性の条件を満たします。ただし、この関係を満たしているからといって、必ず解けるとはかぎらないことに注意してください。
それでは、ペグ・ソリテア・スター（その２）の場合はどうなるでしょうか。
● ０
／ ＼ ／ ＼ Group 0 : 6
●───●───●───● ０───１───２───０
＼ ／ ＼ ／ ＼ ／ ＼ ／ Group 1 : 3
● ● ２ １
／ ＼ ／ ＼ ／ ＼ ／ ＼ Group 2 : 3
●───●───●───● ０───１───２───０
＼ ／ ＼ ／ Total : 12
● ０
図 : ペグ・ソリテア・スター（その２）の偶奇性
最初に Group 0 のペグをひとつ取り除くと、3 つのグループすべて奇数になってしまいますね。この場合、解くことはできません。では、Group 1 のペグをひとつ取り除いてみましょう。すると、全体のペグ数は奇数になり、Group 0, 1 は偶数で Group 2 は奇数なので偶奇性の条件を満たします。同様に、Group 2 のペグをひとつ取り除いた場合も条件を満たします。
最初に Group 0 のペグを取り除くと解はありませんが、Group 1 か 2 のペグを取り除く場合は解があるかもしれません。実際に解いてみると、最短手順は次のようになりました。
０ 2 のペグを取り除いた場合
／ ＼ 1 : [7, 2]
１───２───３───４ 2 : [11, 5]
＼ ／ ＼ ／ 3 : [10, 8]
５ ６ 4 : [4, 9, 7]
／ ＼ ／ ＼ 5 : [0, 6]
７───８───９───10 6 : [1, 3]
＼ ／ 7 : [7, 2, 4, 9]
11
図 : ペグ・ソリテア・スター（その２）の解答
この場合、「補償型の解」は存在しません。これも偶奇性からわかります。最後にひとつ残るペグは、全体のペグ数の偶奇性と一致しているグループになります。つまり、最初に取り除いたペグのグループが全体のペグ数の偶奇性と一致していることが、「補償型の解」が存在する条件になるのです。
上図の場合、取り除いたペグのグループと全体のペグ数の偶奇性は一致しません。したがって、最初に 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
# 跳び先表
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)