今回は Memorandum 2002 年 11 月 20 日 に出題したパズル「フリップ・イット・スター」を解いてみましょう。「フリップ・イット (Flip It)」は芦ヶ原伸之氏が考案されたパズルで、すべての駒を裏返しにするのが目的です。今回はリバーシの駒を使うことにします。次の図を見てください。
０ １ ２ ３ ４ ５ ０ １ ２ ３ ４ ５
┌─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┐
│ │●│●│●│●│●│ │●│○│○│○│○│ │
└─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┘
│ │
┌─────────┘ └─────┐
↓ ↓
┌─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┐
│●│○│○│○│○│ │ │●│○│ │●│●│○│
└─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┘
５の駒が０へ跳んだ場合 ２の駒が５へ跳んだ場合
図：フリップ・イットのルール
フリップ・イットのルールは簡単です。ある駒はほかの駒を跳び越して空き場所へ移動することができます。空き場所の隣にある駒は、跳び越す駒がないので移動できません。このとき、跳び越された駒は裏返しにされますが、跳んだ駒はそのままです。図では 5 の位置にある駒が 0 へ跳び、それから 2 の駒が 5 へ跳んだ場合を示しています。このあと 0 -> 2, 5 -> 0 と跳ぶと、すべての駒を白にすることができます。
参考文献 [12] には 1 行 5 列 の問題があります。今回の「フリップ・イット・スター」は駒の配置を六芒星の形にしたバージョンです。それでは問題です。
□
／ ＼
●───●───●───●
＼ ／ ＼ ／
● ●
／ ＼ ／ ＼
●───●───●───●
＼ ／
●
問題：フリップ・イット・スター
図では空き場所を □ で表しています。ルールは「フリップ・イット」と同じで、駒は直線に沿ってほかの駒を跳び越すことができます。途中で曲がって跳び越すことは許されません。すべての駒を白にする最短手順を求めてください。
まずは単純な反復深化でプログラムを作りましょう。使用するプログラミング言語はＣ言語です。最初にグローバル変数を定義します。
０
／ ＼
１───２───３───４
＼ ／ ＼ ／
５ ６
／ ＼ ／ ＼
７───８───９───10
＼ ／
11
図：配列と盤面の対応
リスト：グローバル変数の定義
/* 盤面 */
char board[SIZE];
/* 直線 */
const char line[LINE][4] = {
0, 2, 5, 7, 0, 3, 6, 10, 7, 8, 9, 10,
1, 2, 3, 4, 1, 5, 8, 11, 4, 6, 9, 11
};
/* 移動手順 */
int line_number[MAX_MOVE + 1];
int space_position[MAX_MOVE + 1];
int piece_position[MAX_MOVE + 1];
盤面は 1 次元配列 board で表します。盤面の位置と配列の添字の対応は、左図のように定義します。すると、6 本の直線は配列 line で表すことができます。ここで、line に格納される番号は昇順に並んでいることに注意してください。移動手順は 3 つの配列で表します。line_number に駒を動かした直線の番号、space_position に空き場所の位置、piece_position に動かした駒の位置を格納します。
駒の移動は跳び先表を定義すると簡単です。次のリストを見てください。
リスト：駒の跳び先表
/* 駒の跳び先表 (直線の番号と駒の位置）*/
const char move_pattern_table[][SIZE] = {
{0, 5, 0, 7, 1, 6, 1, 10, -1}, /* 0 */
{3, 3, 3, 4, 4, 8, 4, 11, -1}, /* 1 */
{0, 7, 3, 4, -1}, /* 2 */
{1, 10, 3, 1, -1}, /* 3 */
{3, 1, 3, 2, 5, 9, 5, 11, -1}, /* 4 */
{0, 0, 4, 11, -1}, /* 5 */
{1, 0, 5, 11, -1}, /* 6 */
{0, 0, 0, 2, 2, 9, 2, 10, -1}, /* 7 */
{2, 10, 4, 1, -1}, /* 8 */
{2, 7, 5, 4, -1}, /* 9 */
{1, 0, 1, 3, 2, 7, 2, 8, -1}, /* 10 */
{4, 1, 4, 5, 5, 4, 5, 6, -1}, /* 11 */
};
配列 move_pattern_table は空き場所を基準にして、直線の番号と移動する駒の位置を順番に定義しています。-1 は終端を表します。たとえば、空き場所が 2 であれば、直線 0 の 7 にある駒、直線 3 の 4 にある駒を動かすことがでます。
駒を動かす関数 move_piece は次のようになります。
リスト：駒を動かす
void move_piece( int l, int p1, int p2 )
{
int i, temp;
temp = board[p1]; /* p1 と p2 の要素を交換 */
board[p1] = board[p2];
board[p2] = temp;
if( p2 < p1 ){ /* 順番のチェック */
temp = p1;
p1 = p2;
p2 = temp;
}
/* 駒の裏返し */
for( i = 0; i < 4; i++ ){
int p3 = line[l][i];
if( p1 < p3 && p3 < p2 ){
board[p3] = (board[p3] == B ? W : B);
}
}
}
引数 l が直線の番号、p1 と p2 が動かす駒の位置と空き場所の位置です。空き場所と駒の位置は p1 と p2 のどちらでもかまいません。最初に p1 と p2 にある要素を交換します。次に駒を裏返しにしますが、ここで配列 line に格納されている番号が昇順に並んでいることを利用します。p1 < p2 になるように値を入れ替えて、p1 と p2 の間にある駒を裏返しにします。B と W は黒石と白石を表すマクロです。
あとは単純な反復深化で最短手順を求めるだけです。次のリストを見てください。
リスト：反復深化による解法
void solve_id( int n, int limit, int space )
{
if( n == limit ){
if( !count_piece( B ) ){
/* 黒が 0 個だからすべて白 */
print_answer( n ); exit( 1 );
}
} else {
int i, l, p;
for( i = 0; (l = move_pattern_table[space][i++]) != -1; ){
p = move_pattern_table[space][i++];
if( l != line_number[n] || p != space_position[n] ){
/* 移動可能 */
move_piece( l, space, p );
piece_position[n + 1] = p;
space_position[n + 1] = space;
line_number[n + 1] = l;
solve_id( n + 1, limit, p );
/* 元に戻す */
move_piece( l, space, p );
}
}
}
}
関数 solve_id の引数 n が手数、limit が反復深化の上限値、space が空き場所の位置です。手数 n が上限値 limit に達したならば、関数 count_piece で黒石 (B) の個数を数えます。黒石が 0 個ならば全部の石が白になったので、print_answer で手順を表示して exit で終了します。そうでなければ move_piece で駒を動かして新しい局面を生成します。
配列 move_pattern_table から直線の番号と動かす駒の位置を取り出して、変数 l と p にセットします。フリップ・イットは、同じ駒を続けて動かすと元の状態に戻ってしまいます。そこで、1 手前の直線の番号 line_number[n] が同じで、動かす駒の位置 p が 1 手前の空き場所の位置 space_position[n] と同じ場合は、その駒を動かさないようにします。このチェックがないと実行時間がとても遅くなります。ご注意くださいませ。あとは move_piece で駒を動かして、solve_id を再帰呼び出しするだけです。そのあと、move_piece で盤面を元に戻すことをお忘れなく。
あとのプログラムは簡単なので説明は省略いたします。詳細は プログラムリスト１ をお読みくださいませ。
さっそく実行してみたところ、最短手順は次のようになりました。
図では黒石を 1, 白石を 2, 空き場所を 0 で表しています。
0
1 1 1 1
1 1
1 1 1 1
1
-(1)----- -(2)----- -(3)----- -(4)----- -(5)----- -(6)-----
1 1 1 1 1 0
1 2 1 1 1 0 1 1 1 1 2 0 1 1 2 1 1 1 2 1 1 1 1 1
2 1 1 1 1 1 1 2 1 0 1 1
0 1 1 1 2 1 1 1 2 1 1 1 2 1 2 1 2 1 1 1 2 1 1 1
1 1 1 0 2 2
-(7)----- -(8)----- -(9)----- -(10)---- -(11)---- -(12)----
2 2 2 2 2 2
1 2 1 1 1 0 1 1 1 1 2 0 1 1 2 2 0 1 2 2 2 2 0 2
2 1 1 1 1 1 1 2 2 2 2 2
0 1 1 1 2 1 1 1 2 1 1 1 2 1 2 1 2 2 2 1 2 2 2 1
2 2 2 0 1 1
-(13)---- -(14)---- -(15)---- -(16)---- -(17)---- -(18)----
2 0 2 2 2 2
2 2 1 2 2 2 2 2 2 1 2 2 2 1 2 2 0 1 2 2 2 2 0 2
2 1 2 2 0 2 1 2 2 2 2 2
2 2 2 0 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2
1 1 1 0 2 2
図：「フリップ・イット・スター」の解答
最短手数は 18 手、実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で 7.1 秒でした。単純な反復深化なので、ちょっと時間がかかるのはしかたがないですね。幅優先探索を使えばもっと速くなると思います。興味のある方は挑戦してみてください。
次は最長手数となる局面を幅優先探索で求めます。最初にキューの大きさを決めるため、駒の置き方が何通りあるか数えましょう。これは空き場所の配置から考えた方が簡単です。盤面の大きさは 12 なので、空き場所の配置は 12 通りあります。残りは黒か白のどちらかなので、駒の配置は 2 11 = 2048 通りあります。したがって、全体では 12 * 2048 = 24576 通りになります。けっこう大きな数になりますね。そこで、同一局面のチェックにはハッシュ法を使うことにします。
それではプログラムを作りましょう。最初にキューを定義します。
リスト：キューの定義
/* 局面の総数 */
#define MAX_STATE 24576
/* 局面 */
typedef struct {
char board[SIZE];
char move;
char space_position;
} State;
/* キュー */
State state_table[MAX_STATE + 1];
局面を表す構造体 State を定義し、その配列 state_table がキューになります。board が盤面、move が手数、space_position が空き場所の位置を表します。MAX_STATE は局面の総数 (24576) を表すマクロです。キューの領域が +1 されているのは、新しい局面を生成するときの作業領域として使用するためです。
次はハッシュ関数を作りましょう。フリップ・イットの場合、駒の置き方を数えた方法で簡単に「最小完全ハッシュ関数」を作ることができます。次のリストを見てください。
リスト：同一局面のチェック
/* ハッシュ表 */
char hash_table[MAX_STATE];
/* 最小完全ハッシュ関数 */
int hash_value( char *board )
{
int i, space, value = 0;
for( i = 0; i < SIZE; i++ ){
switch( board[i] ){
case S: space = i; break;
case B: value = value * 2 + 1; break;
case W: value = value * 2; break;
}
}
/* 2048 = 2 の 11 乗 */
return 2048 * space + value;
}
int insert_hash( char *board )
{
int value = hash_value( board );
if( !hash_table[value] ){
return hash_table[value] = TRUE;
}
return FALSE;
}
今回は最小完全ハッシュ関数を作成するので、ハッシュ値の衝突は発生しません。ハッシュ表の値は TRUE (1) と FALSE (0) だけで十分なので、ハッシュ表 hash_table は char 型で宣言します。関数 insert_hash は同一局面のチェックを行います。同じ局面がなければハッシュ表に登録して TRUE を返し、同じ局面があれば FALSE を返します。
関数 hash_value は局面 board のハッシュ値を返します。ハッシュ値は空き場所の位置と駒の配置から計算することができます。まず、空き場所の位置を変数 space にセットします。駒の配置は、黒がビットオンで白がビットオフと定義すれば 2 進数と考えることができるので、数値に変換するのはとても簡単です。この値を変数 value にセットします。あとは 2048 * space + value を計算するだけです。
次は幅優先探索を行う関数 solve_breadth を作ります。
リスト：幅優先探索
void solve_breadth( void )
{
int i, front = 0, rear = 0;
/* キューの初期化 */
for( i = 0; i < SIZE; i++ ){
memset( state_table[i].board, W, SIZE );
state_table[i].board[i] = S;
state_table[i].move = 0;
state_table[i].space_position = i;
rear++;
insert_hash( state_table[i].board ); /* ハッシュ表に登録 */
}
while( front < rear ){
State *new_state, *state = &(state_table[front]);
int l, p, space = state->space_position;
for( i = 0; (l = move_pattern_table[space][i++]) != -1; ){
p = move_pattern_table[space][i++];
new_state = &(state_table[rear]);
memcpy( new_state->board, state->board, SIZE );
move_piece( new_state->board, l, space, p );
if( insert_hash( new_state->board ) ){
/* キューに登録 */
new_state->move = state->move + 1;
new_state->space_position = p;
rear++;
}
}
front++;
}
printf("局面の総数 %d\n", rear );
print_answer( rear - 1 );
}
最初にすべての駒が白の局面 (12 通り) を生成してキューとハッシュ表に登録します。あとは、いつもの幅優先探索と同じです。キューからデータを取り出して、関数 move_piece で駒を動かして新しい局面 new_state を生成します。そして、insert_hash で同一局面のチェックを行い、新しい局面であればキューに登録します。キューにデータがなくなったら、print_answer で最長手数の局面を表示します。
あとはとくに難しいところはないでしょう。詳細は プログラムリスト２ をお読みくださいませ。
さっそく実行してみたところ、最長手数の局面は次のようになりました。図では黒石を 1, 白石を 2, 空き場所を 0 で表しています。
1 0 1 1 1 1
1 0 2 1 1 2 2 1 1 2 0 1 1 1 2 1 1 2 1 1 1 2 1 1
2 1 1 1 1 2 2 1 0 2 1 2
1 1 2 1 1 2 2 1 1 2 1 1 1 1 0 1 1 2 1 1 1 2 0 1
1 1 1 1 1 1
1 1 1 0 1 1
0 2 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 2 1
2 2 2 2 1 2 1 1 2 0 2 2
1 1 2 1 1 1 2 0 0 1 1 1 1 2 2 1 1 1 2 1 0 2 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 2 1 1 1 2 2 1 1 1 1 0 0 1 1 1 1 1 2 1 1 1 2 0
2 1 1 1 2 1 1 2 2 1 2 2
1 1 1 0 1 2 2 1 1 2 1 1 1 1 2 1 1 0 2 1 1 2 1 1
1 0 1 1 1 1
1 1 1 1 1 1
1 2 2 1 1 2 1 1 1 0 1 1 1 1 2 1 1 1 0 1 1 2 1 1
1 1 1 2 1 2 0 1 2 1 1 0
1 1 1 1 1 0 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 2 1 1
0 1 1 1 1 1
図：最長手数 (21手) の局面
最長手数は 21 手、その局面は全部で 24 通りになりました。実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) でも約 0.3 秒、ハッシュ法の効果で高速に解くことができました。
/*
* flip_it_star.c : フリップ・イット・スター「六芒星バージョン」
*
* Copyright (C) 2002 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 12
#define LINE 6
#define MAX_MOVE 20
/* 駒の定義 */
#define S 0
#define B 1
#define W 2
/* 駒の跳び先表 (直線の番号と位置）*/
const char move_pattern_table[][SIZE] = {
{0, 5, 0, 7, 1, 6, 1, 10, -1}, /* 0 */
{3, 3, 3, 4, 4, 8, 4, 11, -1}, /* 1 */
{0, 7, 3, 4, -1}, /* 2 */
{1, 10, 3, 1, -1}, /* 3 */
{3, 1, 3, 2, 5, 9, 5, 11, -1}, /* 4 */
{0, 0, 4, 11, -1}, /* 5 */
{1, 0, 5, 11, -1}, /* 6 */
{0, 0, 0, 2, 2, 9, 2, 10, -1}, /* 7 */
{2, 10, 4, 1, -1}, /* 8 */
{2, 7, 5, 4, -1}, /* 9 */
{1, 0, 1, 3, 2, 7, 2, 8, -1}, /* 10 */
{4, 1, 4, 5, 5, 4, 5, 6, -1}, /* 11 */
};
/* 直線 */
const char line[LINE][4] = {
0, 2, 5, 7, 0, 3, 6, 10, 7, 8, 9, 10,
1, 2, 3, 4, 1, 5, 8, 11, 4, 6, 9, 11
};
/* 盤面 */
char board[SIZE];
/* 移動手順 */
int line_number[MAX_MOVE + 1];
int space_position[MAX_MOVE + 1];
int piece_position[MAX_MOVE + 1];
/* 駒を動かす */
void move_piece( int l, int p1, int p2 )
{
int i, temp;
/* p1 と p2 の要素を交換 */
temp = board[p1];
board[p1] = board[p2];
board[p2] = temp;
/* 順番のチェック */
if( p2 < p1 ){
temp = p1;
p1 = p2;
p2 = temp;
}
/* 駒の裏返し */
for( i = 0; i < 4; i++ ){
int p3 = line[l][i];
if( p1 < p3 && p3 < p2 ){
board[p3] = (board[p3] == B ? W : B);
}
}
}
/* 盤面を表示 */
void print_board( void )
{
int i;
printf(" %d\n", board[0] );
for( i = 1; i < 5; i++ ) printf(" %d", board[i] );
printf("\n %d %d\n", board[5], board[6] );
for( i = 7; i < 11; i++ ) printf(" %d", board[i] );
printf("\n %d\n\n", board[11] );
}
/* 手順を表示 */
void print_answer( int n )
{
if( n > 0 ){
move_piece( line_number[n], space_position[n], piece_position[n] );
print_answer( n - 1 );
move_piece( line_number[n], space_position[n], piece_position[n] );
}
printf("----- %d 手 -----\n", n );
print_board();
}
/* piece の個数をカウント */
int count_piece( int piece )
{
int i, c = 0;
for( i = 0; i < SIZE; i++ ){
if( board[i] == piece ) c++;
}
return c;
}
/* 反復深化による探索 */
void solve_id( int n, int limit, int space )
{
if( n == limit ){
if( !count_piece( B ) ){
/* 黒が 0 個だからすべて白 */
print_answer( n ); exit( 1 );
}
} else {
int i, l, p;
for( i = 0; (l = move_pattern_table[space][i++]) != -1; ){
p = move_pattern_table[space][i++];
if( l != line_number[n] || p != space_position[n] ){
/* 移動可能 */
move_piece( l, space, p );
piece_position[n + 1] = p;
space_position[n + 1] = space;
line_number[n + 1] = l;
solve_id( n + 1, limit, p );
/* 元に戻す */
move_piece( l, space, p );
}
}
}
}
int main()
{
int i;
/* 初期化 */
for( i = 0; i < SIZE; i++ ) board[i] = B;
board[0] = S;
piece_position[0] = -1;
space_position[0] = -1;
line_number[0] = -1;
/* 探索 */
for( i = 1; i <= MAX_MOVE ; i++ ){
printf("----- %d 手を探索 -----\n", i );
solve_id( 0, i, 0 );
}
return 0;
}
/*
* flip_max.c : フリップ・イット「六芒星」
*
* 最長手数の局面を求める
*
* Copyright (C) 2002 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 12
#define LINE 6
#define MAX_STATE 24576
/* 駒の定義 */
#define S 0
#define B 1
#define W 2
/* 局面 */
typedef struct {
char board[SIZE];
char move;
char space_position;
} State;
/* 移動パターン表 (ライン番号と位置）*/
const char move_pattern_table[][SIZE] = {
{0, 5, 0, 7, 1, 6, 1, 10, -1}, /* 0 */
{3, 3, 3, 4, 4, 8, 4, 11, -1}, /* 1 */
{0, 7, 3, 4, -1}, /* 2 */
{1, 10, 3, 1, -1}, /* 3 */
{3, 1, 3, 2, 5, 9, 5, 11, -1}, /* 4 */
{0, 0, 4, 11, -1}, /* 5 */
{1, 0, 5, 11, -1}, /* 6 */
{0, 0, 0, 2, 2, 9, 2, 10, -1}, /* 7 */
{2, 10, 4, 1, -1}, /* 8 */
{2, 7, 5, 4, -1}, /* 9 */
{1, 0, 1, 3, 2, 7, 2, 8, -1}, /* 10 */
{4, 1, 4, 5, 5, 4, 5, 6, -1}, /* 11 */
};
/* 直線 */
const char line[LINE][4] = {
0, 2, 5, 7, 0, 3, 6, 10, 7, 8, 9, 10,
1, 2, 3, 4, 1, 5, 8, 11, 4, 6, 9, 11
};
/* キュー */
State state_table[MAX_STATE + 1];
/* ハッシュ表 */
char hash_table[MAX_STATE];
/* 最小完全ハッシュ関数 */
int hash_value( char *board )
{
int i, space, value = 0;
for( i = 0; i < SIZE; i++ ){
switch( board[i] ){
case S: space = i; break;
case B: value = value * 2 + 1; break;
case W: value = value * 2; break;
}
}
/* 2048 = 2 の 11 乗 */
return 2048 * space + value;
}
int insert_hash( char *board )
{
int value = hash_value( board );
if( !hash_table[value] ){
return hash_table[value] = TRUE;
}
return FALSE;
}
/* 駒を動かして新しい盤面を作る */
void move_piece( char *board, int l, int p1, int p2 )
{
int i, temp;
/* p1 と p2 の駒を交換 */
temp = board[p1];
board[p1] = board[p2];
board[p2] = temp;
/* 順番のチェック */
if( p2 < p1 ){
temp = p1;
p1 = p2;
p2 = temp;
}
/* 駒の裏返し */
for( i = 0; i < 4; i++ ){
int p3 = line[l][i];
if( p1 < p3 && p3 < p2 ){
board[p3] = (board[p3] == B ? W : B);
}
}
}
/* 盤面を表示 */
void print_board( char *board )
{
int i;
printf(" %d\n", board[0] );
for( i = 1; i < 5; i++ ) printf(" %d", board[i] );
printf("\n %d %d\n", board[5], board[6] );
for( i = 7; i < 11; i++ ) printf(" %d", board[i] );
printf("\n %d\n\n", board[11] );
}
/* 最長手数の局面を表示 */
void print_answer( int n )
{
int count = 0, max_move = state_table[n].move;
printf("最長手数 %d 手\n", max_move );
do {
print_board( state_table[n].board );
count++;
} while( state_table[--n].move == max_move );
printf("個数 %d \n", count );
}
/* 幅優先探索 */
void solve_breadth( void )
{
int i, front = 0, rear = 0;
/* キューの初期化 */
for( i = 0; i < SIZE; i++ ){
memset( state_table[i].board, W, SIZE );
state_table[i].board[i] = S;
state_table[i].move = 0;
state_table[i].space_position = i;
rear++;
/* ハッシュ表に登録 */
insert_hash( state_table[i].board );
}
while( front < rear ){
State *new_state, *state = &(state_table[front]);
int l, p, space = state->space_position;
for( i = 0; (l = move_pattern_table[space][i++]) != -1; ){
p = move_pattern_table[space][i++];
new_state = &(state_table[rear]);
memcpy( new_state->board, state->board, SIZE );
move_piece( new_state->board, l, space, p );
if( insert_hash( new_state->board ) ){
/* キューに登録 */
new_state->move = state->move + 1;
new_state->space_position = p;
rear++;
}
}
front++;
}
printf("局面の総数 %d\n", rear );
print_answer( rear - 1 );
}
int main()
{
int start = clock();
solve_breadth();
printf("時間 %d\n", clock() - start );
return 0;
}