今回は盤面を 六芒星 の形にしたスライドパズルを解いてみましょう。
★ ☆
／ ＼ ／ ＼
★───★───★───★ ☆───☆───☆───☆
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
★───□───☆ ☆───□───★
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
☆───☆───☆───☆ ★───★───★───★
＼ ／ ＼ ／
☆ ★
ＳＴＡＲＴ ＧＯＡＬ
問題：スライドパズル「六芒星」
駒の種類は白（☆）と黒（★）の 2 種類しかありません。□ は空き場所を表しています。駒の動かし方は 15 パズルと同じで、1 回に 1 個の駒を空いている隣の場所に滑らせて移動します。駒を跳び越したり持ち上げたりすることはできません。START から GOAL までの最短手順を求めてください。
それではプログラムを作りましょう。使用するプログラミング言語はＣ言語です。最初、単純な反復深化でプログラムを作ってみたのですが、時間がかかりすぎて途中で断念しました。そこで、オーソドックスに幅優先探索を使うことにします。
局面の総数ですが、空き場所の位置が 13 通りで、残り 12 マスに 6 個の黒駒を置くわけですから、13 * 13Ｃ6 = 13 * 924 = 12012 通りあります。局面の総数はそれほど多くありませんが、今回は最小完全ハッシュ関数を作成して同一局面のチェックを行うことにします。最小完全ハッシュ関数の作成法は、拙作のページ 組み合わせに番号をつける方法 をお読みくださいませ。
組み合わせに番号をつけることができれば、最小完全ハッシュ関数を作るのは簡単です。空き場所の位置は 0 から 12 まであるので、「空き場所の位置 * 組み合わせの番号」が求めるハッシュ値となります。プログラムは次のようになります。空き場所の位置を S (0)、黒石を B (1)、白石を W (2) で表しています。
リスト：最小完全ハッシュ関数
int hash_value( char *board )
{
int space = 0, value = 0;
int i, n = 12, r = 6;
for (i = 0; i < SIZE; i++){
switch( board[i] ){
case S:
space = i; break;
case B:
if( n > r && r > 0 ){
value += comb_table[--n][r--];
}
break;
default:
n--;
}
}
return space * 924 + value;
}
組み合わせに番号をつける方法 で作成したプログラムとほとんど同じなので、難しいところはないと思います。あとのプログラムは、お馴染みの幅優先探索なので簡単です。いつものように、スタートとゴールの両方向から探索を行っています。詳細は プログラムリスト１ をお読みくださいませ。
それでは、スライドパズル「六芒星」の解答を示します。図では黒駒（★）を 1, 白駒（☆）を 2, 空き場所を 0 で表しています。
1
1 1 1 1
1 0 2
2 2 2 2
2
- 1 --- - 2 --- - 3 --- - 4 --- - 5 --- - 6 --- - 7 --- - 8 ---
1 1 1 1 1 1 1 1
1 1 0 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 2 1 1 0 2 1
1 1 2 1 1 0 1 1 2 1 0 2 0 1 2 2 1 2 2 0 2 2 1 2
2 2 2 2 2 2 2 2 2 2 0 2 2 2 1 2 2 2 1 2 2 0 1 2 2 1 1 2 2 1 1 2
2 2 2 2 2 2 2 2
- 9 --- - 10 -- - 11 -- - 12 -- - 13 -- - 14 -- - 15 -- - 16 --
1 1 1 1 1 1 1 1
0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 0 2 1
2 1 2 0 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 0 2 2 1 2
2 1 1 2 2 1 1 2 0 1 1 2 1 0 1 2 1 2 1 2 1 2 0 2 1 2 1 2 1 2 1 2
2 2 2 2 0 1 1 1
- 17 -- - 18 -- - 19 -- - 20 -- - 21 -- - 22 -- - 23 -- - 24 --
0 2 2 2 2 2 2 2
2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 0 2 1 2 2 2 1
2 1 2 2 1 2 2 1 0 2 1 2 2 1 2 2 0 2 2 1 2 0 1 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 0 1 1 2 1 1 1 2 1 1 1 2 1 1
1 1 1 1 1 1 1 1
- 25 -- - 26 -- - 27 -- - 28 -- - 29 -- - 30 --
2 2 2 2 2 2
2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 0 2 2 0 2 2 2 2 2
2 1 2 2 0 2 2 2 0 2 2 1 2 2 1 2 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
図：スライドパズル「六芒星」の解答
最短手数は 30 手になりました。駒が 2 種類しかないスライドパズルは スライディングブロックパズル(1) で 4 行 4 列盤の問題を解きました。そのときの最短手数は 48 手になりましたが、今回のパズルはそれよりも短い手数で解くことができました。
実はこの問題、START の局面からの最長手数になっています。つまり、一番難しい問題だったわけです。ちなみに、最長手数の局面は全部で 7 通りあります。
2 2 2 2 2 2 0
2 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2
2 1 1 2 2 1 2 1 1 2 1 1 2 0 1 2 2 1 2 2 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1
図：スライドパズル「六芒星」最長手数 (30 手) の局面
駒の種類を増やすと、たぶん最長手数はもっと長くなると思われます。興味のある方は挑戦してみてください。
/*
* slide_star.c : スライドパズル「六芒星」
*
* Copyright (C) 2002,2003 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define S 0
#define B 1
#define W 2
#define SIZE 13
#define NIL (-1)
#define FORWARD 1
#define BACKWARD 2
#define MAX_STATE 12012
/* 隣接リスト */
const char adjacent[][SIZE] = {
{2, 3, -1}, /* 0 */
{2, 5, -1}, /* 1 */
{0, 1, 3, 5, 6, -1}, /* 2 */
{0, 2, 4, 6, 7, -1}, /* 3 */
{3, 7, -1}, /* 4 */
{1, 2, 6, 8, 9, -1}, /* 5 */
{2, 3, 5, 7, 9, 10, -1}, /* 6 */
{3, 4, 6, 10, 11, -1}, /* 7 */
{5, 9, -1}, /* 8 */
{5, 6, 8, 10, 12, -1}, /* 9 */
{6, 7, 9, 11, 12, -1}, /* 10 */
{7, 10, -1}, /* 11 */
{9, 10, -1}, /* 12 */
};
/* 初期状態 */
char init_state[SIZE] = {
1,
1,1,1,1,
1,0,2,
2,2,2,2,
2,
};
/* 終了状態 */
char final_state[SIZE] = {
2,
2,2,2,2,
2,0,1,
1,1,1,1,
1,
};
/* ハッシュ表 */
int hash_table[MAX_STATE];
/* キュー */
char state[MAX_STATE][SIZE];
char space_position[MAX_STATE];
char direction[MAX_STATE];
int prev_state[MAX_STATE];
/* パスカルの三角形 */
int comb_table[12][12];
/* 初期化 */
void init( void )
{
int i, j;
comb_table[0][0] = 1;
for( i = 1; i < 12; i++ ){
comb_table[i][0] = comb_table[i][i] = 1;
for( j = 1; j < i; j++ ){
comb_table[i][j] = comb_table[i -1][j - 1] + comb_table[i - 1][j];
}
}
for( i = 0; i < MAX_STATE; i++ ) hash_table[i] = NIL;
}
/* 最少完全ハッシュ関数 */
int hash_value( char *board )
{
int space = 0, value = 0;
int i, n = 12, r = 6;
for (i = 0; i < SIZE; i++){
switch( board[i] ){
case S:
space = i; break;
case B:
if( n > r && r > 0 ){
value += comb_table[--n][r--];
}
break;
default:
n--;
}
}
return space * 924 + value;
}
/* ハッシュへ挿入 */
int insert_hash( char *board, int num )
{
int value = hash_value( board );
if( hash_table[value] != NIL ) return hash_table[value];
hash_table[value] = num;
return -1;
}
/* 盤面を表示 */
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 %d\n", board[5], board[6], board[7] );
for( i = 8; i < 12; i++ ) printf(" %d", board[i] );
printf("\n %d\n\n", board[12] );
}
/* 結果を出力 */
void print_answer_forward( int n )
{
if( n > 1 ) print_answer_forward( prev_state[n] );
print_board( state[n] );
printf("\n");
}
void print_answer_backward( int n )
{
do {
n = prev_state[n];
print_board( state[n] );
printf("\n");
} while( prev_state[n] != -1 );
}
void print_answer( int i, int j )
{
if( direction[i] == FORWARD ){
print_answer_forward( i );
print_answer_backward( j );
} else {
print_answer_forward( j );
print_answer_backward( i );
}
}
/* キューを初期化 */
void init_queue( void )
{
/* 初期化 */
memcpy( state[0], init_state, SIZE );
space_position[0] = 6;
direction[0] = FORWARD;
prev_state[0] = NIL;
insert_hash( init_state, 0 );
memcpy( state[1], final_state, SIZE );
space_position[1] = 6;
direction[1] = BACKWARD;
prev_state[1] = NIL;
insert_hash( final_state, 1 );
}
/* 探索 */
void search( void )
{
int front = 0, rear = 2;
init_queue();
/* 探索 */
while( front < rear ){
int s = space_position[front];
int i, n, m;
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 状態をコピー */
memcpy( state[rear], state[front], SIZE );
/* 移動 */
state[rear][s] = state[rear][n];
state[rear][n] = S;
space_position[rear] = n;
prev_state[rear] = front;
direction[rear] = direction[front];
/* 同一局面のチェック */
m = insert_hash( state[rear], rear );
if( m >= 0 ){
if( direction[m] != direction[rear] ){
/* 前後からの探索が一致した */
print_answer( m, rear );
printf("総数 %d 個\n", rear );
return;
}
} else {
/* 登録 */
rear++;
}
}
front++;
}
}
int main()
{
int start, end;
init();
start = clock();
search();
end = clock();
printf("時間 %d \n", end - start );
return 0;
}
/*
* slide_star_max.c : スライドパズル「六芒星」
* 最長手数の局面を求める
*
* Copyright (C) 2002,2003 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define S 0
#define B 1
#define W 2
#define SIZE 13
#define NIL (-1)
#define MAX_STATE 12012
/* 隣接リスト */
const char adjacent[][SIZE] = {
{2, 3, -1}, /* 0 */
{2, 5, -1}, /* 1 */
{0, 1, 3, 5, 6, -1}, /* 2 */
{0, 2, 4, 6, 7, -1}, /* 3 */
{3, 7, -1}, /* 4 */
{1, 2, 6, 8, 9, -1}, /* 5 */
{2, 3, 5, 7, 9, 10, -1}, /* 6 */
{3, 4, 6, 10, 11, -1}, /* 7 */
{5, 9, -1}, /* 8 */
{5, 6, 8, 10, 12, -1}, /* 9 */
{6, 7, 9, 11, 12, -1}, /* 10 */
{7, 10, -1}, /* 11 */
{9, 10, -1}, /* 12 */
};
/* 初期状態 */
char init_state[SIZE] = {
1,
1,1,1,1,
1,0,2,
2,2,2,2,
2,
};
/* ハッシュ表 */
char hash_table[MAX_STATE];
/* キュー */
char state[MAX_STATE + 1][SIZE]; /* +1 はワーク領域 */
char space_postion[MAX_STATE +1];
char move[MAX_STATE + 1];
/* パスカルの三角形 */
int comb_table[12][12];
/* 初期化 */
void init( void )
{
int i, j;
comb_table[0][0] = 1;
for( i = 1; i < 12; i++ ){
comb_table[i][0] = comb_table[i][i] = 1;
for( j = 1; j < i; j++ ){
comb_table[i][j] = comb_table[i -1][j - 1] + comb_table[i - 1][j];
}
}
}
/* 最少完全ハッシュ関数 */
int hash_value( char *board )
{
int space = 0, value = 0;
int i, n = 12, r = 6;
for (i = 0; i < SIZE; i++){
switch( board[i] ){
case S:
space = i; break;
case B:
if( n > r && r > 0 ){
value += comb_table[--n][r--];
}
break;
default:
n--;
}
}
return space * 924 + value;
}
/* ハッシュへ挿入 */
int insert_hash( char *board )
{
int value = hash_value( board );
if( hash_table[value] == TRUE ) return FALSE;
hash_table[value] = TRUE;
return TRUE;
}
/* 盤面を表示 */
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 %d\n", board[5], board[6], board[7] );
for( i = 8; i < 12; i++ ) printf(" %d", board[i] );
printf("\n %d\n\n", board[12] );
}
/* 結果を出力 */
void print_answer( int n )
{
int m = move[n - 1], c = 0, i;
while( move[--n] == m ){
c++;
print_board( state[n] );
printf("\n");
}
printf("最長手数 %d 手、総数 %d 個\n", m, c );
}
/* 探索 */
void search( void )
{
int front = 0, rear = 1, i;
/* 初期化 */
memcpy( state[0], init_state, SIZE );
space_postion[0] = 6;
move[0] = 0;
/* ハッシュ表への登録 */
insert_hash( init_state );
/* 探索 */
while( front < rear ){
int s = space_postion[front];
int n;
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 状態をコピー */
memcpy( state[rear], state[front], SIZE );
/* 移動 */
state[rear][s] = state[rear][n];
state[rear][n] = 0;
/* 同一局面のチェック */
if( insert_hash( state[rear] ) ){
/* 登録 */
space_postion[rear] = n;
move[rear] = move[front] + 1;
rear++;
}
}
front++;
}
printf("総数 %d 個\n", rear );
print_answer( rear );
}
int main()
{
int start, end;
init();
start = clock();
search();
end = clock();
printf("時間 %d \n", end - start );
return 0;
}