問題の説明
ペグ・ソリテアは、盤上に配置されたペグ (駒) を最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動して取り除くことができます。
- ペグは隣にあるペグをひとつだけ跳び越して、空いている場所へ着地します。
- 跳び越されたペグは盤上から取り除かれます。
- 移動方向は、ふつう縦横のみの 4 方向ですが、 ルールによっては斜め方向の移動を許す場合もあります。
- 同じペグの連続跳び越しは 1 手と数えます。
「トライトライ」は芦ヶ原伸之氏のデザインによるペグ・ソリテアです。次の図を見てください。
トライトライは 25 の穴にペグがありますが、そこからペグをひとつ取り除いてゲームを開始します。上図では黒丸がペグを表し、中央の白丸が空き場所を表しています。ペグは線に沿って移動することができます。それでは問題です。
[問題１] 最初に中央のペグを取り除いて、最後にペグが一つ残る最短手数を求めてください。 [問題２] 最初の空き位置と最後に残ったペグの位置が同じになることを「補償型の解」といい、 最初の空き位置が盤の中央で、なおかつ補償型の解がある場合を「中央補償型の解」といいます。 トライトライには「中央補償型の解」が存在します。この最小手数を求めてください。
●プログラムの作成
それではプログラムを作りましょう。使用するプログラミング言語は Python3 (PyPy3) です。今回は 変形三角盤 と同様に「反復深化＋下限値枝刈り法」で解くことにします。
最初に、ペグの跳び先表を定義します。下図のように穴に番号をつけると、跳び先表は次のようになります。
リスト : 定数と跳び先表の定義
# 定数
MAX_JUMP = 23
HOLE = 11
SIZE = 25
# 跳び先表
jump_table = [
[(2, 5), (3, 7)], # 0
[(3, 6), (4, 8)], # 1
[(3, 4), (5, 9), (6, 11)], # 2
[(6, 10), (7, 12)], # 3
[(3, 2), (7, 11), (8, 13)], # 4
[(2, 0), (6, 7), (9, 14), (10, 16)], # 5
[(3, 1), (7, 8), (10, 15), (11, 17)], # 6
[(3, 0), (6, 5), (11, 16), (12, 18)], # 7
[(4, 1), (7, 6), (12, 17), (13, 19)], # 8
[(5, 2), (10, 11), (15, 21)], # 9
[(6, 3), (11, 12), (15, 20), (16, 22)], # 10
[(6, 2), (7, 4), (10, 9), (12, 13), (16, 21), (17, 23)], # 11
[(7, 3), (11, 10), (17, 22), (18, 24)], # 12
[(8, 4), (12, 11), (18, 23)], # 13
[(9, 5), (15, 16)], # 14
[(10, 6), (16, 17)], # 15
[(10, 5), (11, 7), (15, 14), (17, 18)], # 16
[(11, 6), (12, 8), (16, 15), (18, 19)], # 17
[(12, 7), (17, 16)], # 18
[(13, 8), (18, 17)], # 19
[(15, 10), (21, 22)], # 20
[(15, 9), (16, 11), (22, 23)], # 21
[(16, 10), (17, 12), (21, 20), (23, 24)], # 22
[(17, 11), (18, 13), (22, 21)], # 23
[(18, 12), (23, 22)], # 24
]
データは跳び越す位置と着地する位置をタプルで表しています。たとえば、2 番のペグは 3 番を跳び越して 4 番に着地するという跳び方があります。
●下限値の求め方
ペグ・ソリテアでは、コーナーと辺にあるペグから下限値を求めることができます。次の図を見てください。
ペグ・ソリテアの場合、コーナーにあるペグはほかのペグから跳び越されることはありません。つまり、コーナーのペグは自分でジャンプするしか移動する方法がないのです。したがって、コーナーにペグが残っていれば、最低でもその個数だけ移動手数が必要になります。トライトライの場合、コーナーは 0, 1, 14, 19, 20, 24 番の 6 か所あります。これを下限値として利用することができます。
ところが、コーナーペグの下限値だけでは不十分のようで、PyPy3 でも時間がかかります。そこで、辺にあるペグを下限値として使うことにします。次の図を見てください。
トライトライには 3 つの辺 (2, 5, 9), (4, 8, 13), (21, 22, 23) があります。図 (A) の辺を見てください。ペグが 3 つ並んでいますね。この状態では、ほかのペグから跳び越されることはありません。つまり、コーナーペグと同様に自分でジャンプするしか移動する方法がないのです。
だからといって、移動手数が 3 手必要になるわけではありません。たとえば、中央のペグが 5 -> 16 -> 14 -> 5 -> 0 と連続跳びすれば、辺にあるペグを取り除くことができますね。つまり、辺にあるペグが 3 つ並んでいる場合、移動手数は最低でも 1 手必要になるのです。
図 (B) の状態も同様です。ペグが 2 つ並んでいる状態では、ほかのペグから跳び越されることはありません。この場合、移動手数は最低でも 1 手必要になります。ただし、辺にペグがひとつしかない場合や図 (C) の状態では、ほかのペグの連続跳びで取り除かれることがあるので、移動手数は 0 手とします。辺にあるペグとコーナーペグを合わせて下限値として利用することにしましょう。
ところで、これらの下限値を利用する場合、注意点がひとつだけあります。それはペグが連続跳びをしている場合です。次の局面を見てください。
上限値を N 手とします。今、上限値の 1 手前で上図の局面になりました。ここで、16 -> 7 -> 5 -> 0 -> 7 または 16 -> 7 -> 0 -> 5 -> 7 と連続跳びすると、N 手で解くことができますね。ここで 15 -> 7 -> 5 と跳んだ局面に注目してください。辺のペグ (2 番と 5 番) が 2 つ並びますが、ここで下限値に 1 を加えると上限値 N を越えるため枝刈りされてしまいます。15 -> 7 -> 0 と跳ぶ場合も同じです。ペグはコーナー (0 番) に移動しますが、ここで下限値に 1 を加えると上限値 N を越えてしまいます。これでは解を求めることができませんね。
そこで、直前に移動したペグは下限値の計算から除外することにします。ようするに、直前に移動したペグは連続跳びする可能性があるので、下限値の対象にしてはいけないのです。15 -> 7 -> 5 と跳んで 2 番と 5 番のペグが並んだ場合、直前に移動したペグは 5 番なので下限値の計算から除外します。15 -> 7 -> 0 と跳んでペグがコーナーに移動した場合も同様です。これで条件を満たす手順が枝刈りされることはありません。
●下限値枝刈り法のプログラム
コーナーペグを下限値として使用する方法は 変形三角盤 : プログラムの高速化 と同じです。コーナーペグの個数は関数 dfs() の引数 lower に保持します。あとは、lower に辺の下限値を加えて枝刈りを行います。下限値を求めるプログラムは次のようになります。
リスト : 下限値の計算
# 辺
edge = [
0, 0, 1, 0, 2,
1, 0, 0, 2, 1,
0, 0, 0, 2, 0,
0, 0, 0, 0, 0,
0, 3, 3, 3, 0
]
# 辺の下限値
edge_value = [
# 000, 001, 010, 011, 100, 101, 110, 111 ペグの並び
0, 0, 0, 1, 0, 0, 1, 1, # 下限値
]
def get_edge_value(board, a, b, c):
n = 0
if board[a]: n += 4
if board[b]: n += 2
if board[c]: n += 1
return edge_value[n]
def get_lower_value(board, prev, lower):
e = edge[prev]
if corner[prev]: lower -= 1
if e != 1: lower += get_edge_value(board, 2, 5, 9)
if e != 2: lower += get_edge_value(board, 4, 8, 13)
if e != 3: lower += get_edge_value(board, 21, 22, 23)
return lower
関数 get_lower_value() の引数 board が盤面、prev は直前に移動したペグの位置、lower がコーナーペグの下限値を表します。最初に、コーナーペグの下限値を修正します。prev がコーナーペグならば、連続跳びの途中かもしれないので lower を -1 します。
辺の下限値は配列 edge_value から求めます。ペグの並びをビットに対応させて数値で表すと 0 から 7 の値になります。それに対応する下限値を edge_value にセットしておきます。そして、関数 get_edge_value() でペグの並びを数値に変換して下限値を求めます。辺のペグはリスト edge によりグループ分けされていて、prev が同じグループでなければ、下限値 lower に get_edge_value() で求めた値を加算します。
●反復深化のプログラム
次は反復深化を行う関数 dfs() を作ります。次のリストを見てください。
リスト : 反復深化＋下限値枝刈り法
def dfs(board, jc, limit, lower, move):
global cnt
if jc + get_lower_value(board, move[-1][1], lower) > limit or cnt > 0: 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
# 連続跳びのチェック
newjc = jc
if move[-1][1] != from_: newjc += 1
# コーナーペグのチェック
newlower = lower
if corner[from_]: newlower -= 1
if corner[to_]: newlower += 1
move.append((from_, to_))
dfs(board, newjc, limit, newlower, move)
move.pop()
board[from_] = True
board[del_] = True
board[to_] = False
引数 board が盤面、jc が跳んだ回数、limit が反復深化の上限値、lower がコーナーペグの下限値、move が移動手順を表します。最初の if 文で get_lower_value() を呼び出して下限値を求め、jc + 下限値 が limit を超えたら枝刈りを行います。get_lower_value() には直前に移動したペグの位置を move から取り出して渡します。move[-1][0] が移動元の位置、move[-1][1] が移動先の位置を表します。
len(move) が MAX_JUMP に達したならば、盤上にはひとつのペグしか残っていません。print_move() で移動手順を表示して、解の個数 cnt を +1 します。ペグが複数残っている場合は探索を続行します。この処理は変形三角盤のプログラムと同じです。
最後に dfs() を呼び出す関数 solver() を作ります。
リスト : トライトライの解法
def solver():
global cnt
cnt = 0
board = [True] * SIZE
# 初手を 2 -> 11 に限定
board[2] = False
board[6] = False
for i in range(9, MAX_JUMP + 1):
print(f'----- {i} -----')
dfs(board, 1, i, 6, [(2, 11)])
if cnt > 0: break
print(cnt)
初手に動かすことができるペグは 6 通りありますが、トライトライの対称性により 1 通りだけ調べれば OK です。今回は初手を 2 -> 11 に限定します。あとはとくに難しいところはないでしょう。詳細は プログラムリスト をお読みくださいませ。
●実行結果
それでは実行結果を示します。
>>>> s = time.time(); solver(); print(time.time() - s) ----- 9 ----- ----- 10 ----- ----- 11 ----- [2, 11][1, 6][10, 3][8, 1, 6][22, 10, 3][19, 8, 6][0, 7, 16][20, 22, 10][24, 22] [9, 2, 11, 13, 23, 21, 9][14, 5, 16, 18] 1 3.9019415378570557 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
最短手数は 11 手、約 3.9 秒でした。コーナーペグだけではなく、辺のペグを下限値に加えた効果は十分に出ていますね。また、思っていたよりも短い手数で解けたのには驚きました。トライトライは連続跳びしやすい盤なのかもしれません。
●中央補償型の解
今度は「中央補償型の解」を求めてみましょう。プログラムの改造は簡単です。関数 dfs() でペグがひとつ残ったときに、そのペグが 11 番にあるかチェックするだけです。さっそく実行してみたところ、結果は次のようになりました。
>>>> s = time.time(); solver(); print(time.time() - s) ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- [2, 11][1, 6][9, 2][0, 5][10, 3][20, 10][8, 6, 15][22, 10][14, 16, 7][19, 8, 6, 15][24, 22, 20, 10] [4, 2, 9, 11, 13, 23, 11] 1 26.25136137008667
最短手数は 12 手、実行時間は約 27 秒でした。
トライトライの解法プログラムは 20 年前にＣ言語で作ったのが最初です。当時のパソコンは Windows 95 (Pentium 166 MHz) で、最短手数 11 手を求めるのに 1.2 秒、中央補償型の解を求めるのに 84 秒、ペグのグール分けによる枝刈りを行っても 50 秒かかりました。
当時のプログラムはちょっと手直しするだけで gcc でコンパイル可能です。興味のある方は プログラムリスト２ をお読みください。実際に実行すると、最短手数 11 手を求めるのに 0.016 秒、中央補償型の解を求めるのに 1.656 秒でした。驚くほど速いですね。今のパソコンが超高性能であることを改めて実感しました。
●プログラムリスト１
#
# trytry.py : トライトライ (ペグ・ソリティア)
#
# Copyright (C) 2022 Makoto Hiroi
#
# 定数
MAX_JUMP = 23
HOLE = 11
SIZE = 25
# 跳び先表
jump_table = [
[(2, 5), (3, 7)], # 0
[(3, 6), (4, 8)], # 1
[(3, 4), (5, 9), (6, 11)], # 2
[(6, 10), (7, 12)], # 3
[(3, 2), (7, 11), (8, 13)], # 4
[(2, 0), (6, 7), (9, 14), (10, 16)], # 5
[(3, 1), (7, 8), (10, 15), (11, 17)], # 6
[(3, 0), (6, 5), (11, 16), (12, 18)], # 7
[(4, 1), (7, 6), (12, 17), (13, 19)], # 8
[(5, 2), (10, 11), (15, 21)], # 9
[(6, 3), (11, 12), (15, 20), (16, 22)], # 10
[(6, 2), (7, 4), (10, 9), (12, 13), (16, 21), (17, 23)], # 11
[(7, 3), (11, 10), (17, 22), (18, 24)], # 12
[(8, 4), (12, 11), (18, 23)], # 13
[(9, 5), (15, 16)], # 14
[(10, 6), (16, 17)], # 15
[(10, 5), (11, 7), (15, 14), (17, 18)], # 16
[(11, 6), (12, 8), (16, 15), (18, 19)], # 17
[(12, 7), (17, 16)], # 18
[(13, 8), (18, 17)], # 19
[(15, 10), (21, 22)], # 20
[(15, 9), (16, 11), (22, 23)], # 21
[(16, 10), (17, 12), (21, 20), (23, 24)], # 22
[(17, 11), (18, 13), (22, 21)], # 23
[(18, 12), (23, 22)], # 24
]
# コーナーペグ (0,1,14,19,20,24)
corner = [
True, True, False, False, False,
False, False, False, False, False,
False, False, False, False, True,
False, False, False, False, True,
True, False, False, False, True
]
# 辺
edge = [
0, 0, 1, 0, 2,
1, 0, 0, 2, 1,
0, 0, 0, 2, 0,
0, 0, 0, 0, 0,
0, 3, 3, 3, 0
]
# 辺の下限値
edge_value = [
# 000, 001, 010, 011, 100, 101, 110, 111 ペグの並び
0, 0, 0, 1, 0, 0, 1, 1, # 下限値
]
def get_edge_value(board, a, b, c):
n = 0
if board[a]: n += 4
if board[b]: n += 2
if board[c]: n += 1
return edge_value[n]
def get_lower_value(board, prev, lower):
e = edge[prev]
if corner[prev]: lower -= 1
if e != 1: lower += get_edge_value(board, 2, 5, 9)
if e != 2: lower += get_edge_value(board, 4, 8, 13)
if e != 3: lower += get_edge_value(board, 21, 22, 23)
return lower
# 手順の表示
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, lower, move):
global cnt
if jc + get_lower_value(board, move[-1][1], lower) > limit or cnt > 0: 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
# 連続跳びのチェック
newjc = jc
if move[-1][1] != from_: newjc += 1
# コーナーペグのチェック
newlower = lower
if corner[from_]: newlower -= 1
if corner[to_]: newlower += 1
move.append((from_, to_))
dfs(board, newjc, limit, newlower, move)
move.pop()
board[from_] = True
board[del_] = True
board[to_] = False
def solver():
global cnt
cnt = 0
board = [True] * SIZE
# 初手を 2 -> 11 に限定
board[2] = False
board[6] = False
for i in range(9, MAX_JUMP + 1):
print(f'----- {i} -----')
dfs(board, 1, i, 6, [(2, 11)])
if cnt > 0: break
print(cnt)
●プログラムリスト２
/*
* trytry.c : ペグ・ソリテア「トライトライ」
*
* Copyright (C) 2002-2022 Makoto Hiroi
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 25
#define MAX_JUMP 23
#define HOLE 11
/* 跳び先表 */
const char jump_table[][SIZE] = {
{ 2, 5, 3, 7, -1}, /* 0 */
{ 3, 6, 4, 8, -1}, /* 1 */
{ 3, 4, 5, 9, 6, 11, -1}, /* 2 */
{ 6, 10, 7, 12, -1}, /* 3 */
{ 3, 2, 7, 11, 8, 13, -1}, /* 4 */
{ 2, 0, 6, 7, 9, 14, 10, 16, -1}, /* 5 */
{ 3, 1, 7, 8, 10, 15, 11, 17, -1}, /* 6 */
{ 3, 0, 6, 5, 11, 16, 12, 18, -1}, /* 7 */
{ 4, 1, 7, 6, 12, 17, 13, 19, -1}, /* 8 */
{ 5, 2, 10, 11, 15, 21, -1}, /* 9 */
{ 6, 3, 11, 12, 15, 20, 16, 22, -1}, /* 10 */
{ 6, 2, 7, 4, 10, 9, 12, 13, 16, 21, 17, 23, -1}, /* 11 */
{ 7, 3, 11, 10, 17, 22, 18, 24, -1}, /* 12 */
{ 8, 4, 12, 11, 18, 23, -1}, /* 13 */
{ 9, 5, 15, 16, -1}, /* 14 */
{10, 6, 16, 17, -1}, /* 15 */
{10, 5, 11, 7, 15, 14, 17, 18, -1}, /* 16 */
{11, 6, 12, 8, 16, 15, 18, 19, -1}, /* 17 */
{12, 7, 17, 16, -1}, /* 18 */
{13, 8, 18, 17, -1}, /* 19 */
{15, 10, 21, 22, -1}, /* 20 */
{15, 9, 16, 11, 22, 23, -1}, /* 21 */
{16, 10, 17, 12, 21, 20, 23, 24, -1}, /* 22 */
{17, 11, 18, 13, 22, 21, -1}, /* 23 */
{18, 12, 23, 22, -1}, /* 24 */
};
/* corner */
const char corner[SIZE] = {
1, 1,
0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1,
};
/* edge */
const char edge[SIZE] = {
0, 0,
1, 0, 2,
1, 0, 0, 2,
1, 0, 0, 0, 2,
0, 0, 0, 0, 0, 0,
0, 3, 3, 3, 0,
};
/* 初期状態 */
const char init_data[SIZE] = {
1, 1,
1, 1, 1,
1, 1, 1, 1,
1, 1, 0, 1, 1,
1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
};
/* 盤面 */
char board[SIZE];
/* 跳び手順を格納 */
char move[MAX_JUMP][2];
/* コーナーのペグ数 */
int lower_value = 6;
/* 計測用 */
int start;
/* 辺の下限値 */
const char edge_value[8] = {
0, /* 000 */
0, /* 001 */
0, /* 010 */
1, /* 011 */
0, /* 100 */
0, /* 101 */
1, /* 110 */
1, /* 111 */
};
/* 辺の下限値を求めるマクロ */
#define GET_EDGE_VALUE(a,b,c) edge_value[(board[(a)]<<2) + (board[(b)]<<1) + board[(c)]]
/* 下限値の計算 */
int get_lower_value( int prev )
{
int low = lower_value - corner[prev];
int eg = edge[prev];
/* 辺のチェック */
if( eg != 1 ) low += GET_EDGE_VALUE( 2, 5, 9 );
if( eg != 2 ) low += GET_EDGE_VALUE( 4, 8, 13 );
if( eg != 3 ) low += GET_EDGE_VALUE( 21, 22, 23 );
return low;
}
/* ペグを動かす */
void move_piece( int n, int from, int del, int to )
{
board[from] = 0;
board[del] = 0;
board[to] = 1;
move[n][0] = from;
move[n][1] = to;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value--;
} else if( corner[to] ){
lower_value++;
}
}
/* ペグを元に戻す */
void back_piece( int from, int del, int to )
{
board[from] = 1;
board[del] = 1;
board[to] = 0;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value++;
} else if( corner[to] ){
lower_value--;
}
}
/* 手順を表示 */
void print_move( void )
{
int i, j;
for( i = 0, j = 1; i < MAX_JUMP; i++, j++ ){
printf("(%d, %d", move[i][0], move[i][1] );
for( ; j < MAX_JUMP; i++, j++ ){
if( move[i][1] != move[j][0] ) break;
printf(", %d", move[j][1] );
}
printf(")");
}
printf("\n時間 %f 秒\n", (double)(clock() - start) / CLOCKS_PER_SEC);
}
/* 手順の探索（反復深化＋下限値枝刈り法） */
void search_move( int n, int jc, int limit )
{
int prev = move[n - 1][1];
if( (jc + get_lower_value( prev )) > limit ) return;
if( n == MAX_JUMP ){
if ( board[HOLE] ){
print_move(); exit( 0 );
}
} else {
int from, del, to, i;
for( from = 0; from < SIZE; from++ ){
if( !board[from] ) continue; /* ペグが無い */
i = 0;
while( (del = jump_table[from][i++]) != -1 ){
to = jump_table[from][i++];
if( board[del] && !board[to] ){
/* 跳び越せる */
move_piece( n, from, del, to );
search_move( n + 1, (prev == from ? jc : jc + 1), limit );
back_piece( from, del, to );
}
}
}
}
}
int main()
{
int limit;
/* 初期化 */
start = clock();
memcpy( board, init_data, SIZE );
/* 初手は [2, 11] に決め打ち */
move_piece( 0, 2, 6, 11 );
/* 初期状態の下限値は 9 */
for( limit = 9; limit <= MAX_JUMP; limit++ ){
printf("・・・手数 %d を探索中・・・\n", limit );
search_move( 1, 1, limit );
}
return 0;
}
改訂 2022 年 10 月 29 日