今回は「15 パズルの変形版」を解いてみましょう。
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│●│○│●│ │●│●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│●│ │●│●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│●│ │●│●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│ │ │●│●│●│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘
（１） （２）
図：問題
(1) の場合、赤、青、黄色、水色、桃色、空白の場所がひとつずつで、残りが 10 個が黒ですから、駒の配置は 16 * 15 * 14 * 13 * 12 * 11 = 5,765,760 通りあります。(2) の場合は、空白の場所が 16 通りあり、緑の駒の配置は 15Ｃ5 = 3003 通り、赤の駒の配置は 10Ｃ5 = 252 通りあるので、駒の配置は 16 * 3003 * 252 = 12,108,096 通りあります。どちらも大きな数なので、今回は省メモリな方法を使いましょう。
最小完全ハッシュ関数とその逆関数を作成して、手数を格納する配列を用意します。最初に、配列を NIL (-1) に初期化しておきます。そして、初期状態（0 手）から始めて、1 手で到達する局面を生成して、配列に 1 を書き込みます。次に、配列から 1 手の局面を検索して、2 手で到達する局面を生成します。このとき、配列の値が NIL 以外の値であれば、すでに生成した局面であることがわかります。
あとは手数を延ばしていくだけです。巨大な配列を検索するのは時間がかかりますが、ここは高速 CPU にがんばってもらいましょう。
それでは、問題 (1) から解いていきましょう。いつものように、空いている場所を 0 で表し、ほかの駒を 1 から 6 までの数字で表すことにします。そうすると、初期状態は下記リストのようになります。
リスト：初期状態
char init_state[SIZE] = {
1, 2, 3, 4,
6, 6, 6, 6,
6, 6, 6, 6,
5, 6, 6, 0,
};
最小完全ハッシュ関数は、幅優先探索の高速化(1) で説明した「Ｎ！通りのパターンに 0 から N - 1 までの番号を付ける方法」と同様に作成することができます。次のプログラムを見てください。
リスト：最小完全ハッシュ関数
/* 数値表 */
const int table[6] ={
360360, /* 15 * 14 * 13 * 12 * 11 */
24024, /* 14 * 13 * 12 * 11 */
1716, /* 13 * 12 * 11 */
132, /* 12 * 11 */
11,
1,
};
/* 盤面を数値に変換 */
int board_to_number( char *board )
{
int buffer[6]; /* 0 - 5 までの位置を格納 */
int i, j, value = 0;
for( i = 0; i < SIZE; i++ ){
int p = board[i];
if( p < 6 ) buffer[p] = i;
}
for( i = 0; i < 6; i++ ){
value += table[i] * buffer[i];
for( j = i + 1; j < 6; j++ ){
if( buffer[i] < buffer[j] ) buffer[j]--;
}
}
return value;
}
最初のループで、0 から 5 までの位置を求めて buffer に格納します。次のループで、ハッシュ値を計算します。やっていることは、「Ｎ！通りのパターンに 0 から N - 1 までの番号を付ける方法」と同じです。これで局面を 0 から 5,765,759 までの数値に変換することができます。
次は、逆変換（数値を盤面に変換）を行う関数を作りましょう。
リスト：数値を盤面に変換する
int number_to_board( int num, char *board )
{
int i, j;
char buffer[6];
memset( board, 6, SIZE );
for( i = 0; i < 5; i++ ){
buffer[i] = num / table[i];
num %= table[i];
}
buffer[i] = num;
for( i = 4; i >= 0; i-- ){
for( j = i + 1; j < 6; j++ ){
if( buffer[i] <= buffer[j] ) buffer[j]++;
}
}
for( i = 0; i < 6; i++ ){
board[ buffer[i] ] = i;
}
return buffer[0]; /* 空き場所の位置を返す */
}
関数 number_to_board は空き場所の位置を返します。まず最初のループで、数値を 6 つの数字へ分解します。この段階では、数字はまだ駒の位置を表していません。次のループで、ハッシュ関数と逆の操作を行うことで、駒の位置を求めます。逆方向から数字をチェックし、数字が大きいか等しい場合は、その数字に 1 を加えます。これで駒の位置を復元することができます。あとは、盤面に駒をセットすればいいわけです。
次は駒を移動する処理を作りましょう。
リスト：駒の移動処理
int move_piece( int num, int move )
{
char board[SIZE];
int c = 0; /* 展開した局面数 */
int s, i, n, new_num;
s = number_to_board( num, board );
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 移動 */
board[s] = board[n];
board[n] = 0;
new_num = board_to_number( board );
if( check_table[new_num] == NIL ){
/* 登録 */
check_table[new_num] = move;
c++;
}
/* 元に戻す */
board[n] = board[s];
board[s] = 0;
}
return c;
}
引数 num が局面を表す数値で、move が手数を表します。プログラムはとても簡単です。まず、number_to_board で数値を局面に変換し、それから駒を移動します。次に、新しい局面を board_to_number で数値に変換し、手数を格納する配列 check_table をチェックします。check_table は NIL (-1) で初期化してあるので、NIL 以外の値であれば古い局面、NIL であれば新しい局面であることがわかります。新しい局面であれば、check_table に move を書き込んで登録します。
探索処理を行う関数 search も簡単です。
リスト：探索処理
void search( void )
{
int num, total = 1, move = 1;
/* 初手を展開 */
num = board_to_number( init_state );
check_table[num] = 0; /* 初期値 */
total += move_piece( num, move );
printf("%2d手 --- %d個\n", move, total );
/* ２手目以降の展開 */
for( ; ; move++ ){
int i, c = 0;
for( i = 0; i < MAX; i++ ){
if( check_table[i] == move ){
c += move_piece( i, move + 1 );
}
}
if( c == 0 ) break;
printf("%2d手 --- %d個\n", move + 1, c );
total += c;
}
print_answer( move );
printf("合計 %d 個\n", total );
}
最初に、初期状態を board_to_number で数値に変換し、配列 check_table に登録します。そして、初期状態から 1 手目を展開します。2 手目以降は、配列 check_table から move 手の局面を検索し、駒を移動して move + 1 手の局面を作成します。あとは move を 1 手ずつ増やしていき、新しい局面が作れなくなった時点でループから脱出します。最後に、最長手数となる局面を print_answer で出力します。
あとのプログラムは簡単なので説明は省略します。プログラムリスト１ を参照してください。
それでは実行してみましょう。
1手 --- 3個 2手 --- 3個 3手 --- 4個 ・・・省略・・・ 56手 --- 22個 57手 --- 3個 58手 --- 1個 0 6 6 5 6 6 6 6 6 6 6 6 4 2 3 1 合計 5765760 個
実行時間はオンボロマシン（Pentium 166 MHz）で約 97 秒でした。結果を図で表すと次のようになります。
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│●│○│●│ │ │●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│●│ │●│●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│●│ │●│●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│ │ │●│●│○│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘
ＳＴＡＲＴ 58 moves
図：問題(1) 解答
次は問題 (2) を解きます。空き場所を 0 とし、駒を数値 1, 2, 3 で表すと、初期状態は下記リストのようになります。
リスト：初期状態
char init_state[SIZE] = {
1, 1, 2, 2,
1, 1, 2, 2,
1, 3, 3, 2,
3, 3, 3, 0,
};
最小完全ハッシュ関数は、スライディングブロックパズル(1) で説明した「組み合わせに番号をつける方法」の応用です。駒 1 の場合、空き場所は無視して 2 と 3 を同じ駒と考えれば、配置は 15Ｃ5 = 3003 通りになります。駒 2 の場合、駒 1 と空き場所を無視すると、配置は 10Ｃ5 = 252 通りとなります。これをプログラムすると、次のようになります。
リスト：最小完全ハッシュ関数
/* 盤面を数値に変換 */
int board_to_number( char *board )
{
int space = 0, value1 = 0, value2 = 0;
int i, n1 = 15, r1 = 5, n2 = 10, r2 = 5;
for (i = 0; i < SIZE; i++){
switch( board[i] ){
case 0:
space = i; break;
case 1:
if( n1 > r1 && r1 > 0 ){
value1 += comb_table[--n1][r1--];
}
break;
case 2:
if( n2 > r2 && r2 > 0 ){
value2 += comb_table[--n2][r2--];
}
n1--;
break;
default:
n1--;
n2--;
}
}
return space * 3003 * 252 + value1 * 252 + value2;
}
n1, r1, value1 が駒 1 用の変数で、n2, r2, value2 が駒 2 用の変数です。配列 comb_table は「パスカルの三角形」を表しています。最初に、空き場所の位置を space にセットします。どちらの駒も空き場所は無視するので、n1 と n2 の値はそのままにします。
駒 1 の場合、駒 2 と 3 を同じ駒として扱うので、n1 の値は駒 2 だけではなく駒 3 の場合もデクリメントします。駒 2 の場合は駒 1 を無視するので、n2 の値は駒 1 ではそのままとし、駒 3 のときにデクリメントします。これで、駒 1 と駒 2 の配置を数値に変換することができます。次は、数値を盤面に変換する関数 number_to_board を作ります。
リスト：数値を盤面に変換
int number_to_board( int num, char *board )
{
int space, value1, value2, temp;
space = num / (3003 * 252);
temp = num % (3003 * 252);
value1 = temp / 252;
value2 = temp % 252;
memset( board, 3, SIZE );
board[space] = 0;
decode( value1, board, 15, 5, 1 );
decode( value2, board, 10, 5, 2 );
return space;
}
最初に、空き場所の位置を space に、駒 1 の配置を value1 に、駒 2 の配置を value2 にセットします。次に、配列 board を駒 3 で埋めて、空き場所の位置をセットします。駒 1 と駒 2 のセットは関数 decode で行います。
リスト：組み合わせの数値を変換
void decode( int value, char *board, int n, int r, int piece )
{
int i = 0;
while( n > r && r > 0 ){
int c = comb_table[--n][r];
while( board[i] != 3 ) i++;
if( value >= c ){
board[i] = piece;
r--;
value -= c;
}
i++;
}
while( r > 0 ){
while( board[i] != 3 ) i++;
board[i++] = piece;
r--;
}
}
基本的には、ハッシュ関数の逆変換を行うだけです。変数 i が配列 board に書き込む位置を表します。無視しなければならない駒があるため、board の中で駒 3 以外の場所はスキップします。それから値をチェックして、組み合わせの数以上の場合は駒 piece を書き込みます。そうでなければ、その位置は駒 3 のままです。最後に、r が 0 より大きい場合は、残った駒を board にセットします。
あとのプログラムは「問題 (1)」のプログラムと同じです。説明は省略しますので、プログラムリスト２ を参照してください。
それでは実行してみましょう。
1手 --- 3個 2手 --- 4個 3手 --- 9個 ・・・省略・・・ 55手 --- 119個 56手 --- 27個 57手 --- 2個 3 0 3 3 2 3 3 1 2 2 1 1 2 2 1 1 3 3 3 3 2 2 3 1 2 2 1 1 0 2 1 1 合計 12108096 個
実行時間はオンボロマシン（Pentium 166 MHz）で約 204 秒でした。結果を図で表すと次のようになります。
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│●│●│●│ │●│●│●│●│ │●│ │●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│●│ │●│●│●│●│ │●│●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│●│ │●│●│●│●│ │●│●│●│●│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│●│●│ │ │ │●│●│●│ │●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
ＳＴＡＲＴ 57 moves 57 moves
図：問題(2) 解答
/*
１５パズルの変形バージョン（その２）
Copryright (C) 2001 by M.Hiroi
次の配置の最長手数を求める
1 2 3 4
6 6 6 6
6 6 6 6
5 6 6 0
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define NIL (-1)
#define SIZE 16
#define MAX 5765760
/* 隣接リスト
座標
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
*/
const char adjacent[SIZE][5] = {
1, 4, -1, -1, -1, /* 0 */
0, 2, 5, -1, -1, /* 1 */
1, 3, 6, -1, -1, /* 2 */
2, 7, -1, -1, -1, /* 3 */
0, 5, 8, -1, -1, /* 4 */
1, 4, 6, 9, -1, /* 5 */
2, 5, 7, 10, -1, /* 6 */
3, 6, 11, -1, -1, /* 7 */
4, 9, 12, -1, -1, /* 8 */
5, 8, 10, 13, -1, /* 9 */
6, 9, 11, 14, -1, /* 10 */
7, 10, 15, -1, -1, /* 11 */
8, 13, -1, -1, -1, /* 12 */
9, 12, 14, -1, -1, /* 13 */
10, 13, 15, -1, -1, /* 14 */
11, 14, -1, -1, -1, /* 15 */
};
/* 初期状態 */
char init_state[SIZE] = {
1, 2, 3, 4,
6, 6, 6, 6,
6, 6, 6, 6,
5, 6, 6, 0,
};
/* 手数を格納するテーブル */
char *check_table;
/* 数値表 */
const int table[6] ={
360360, /* 15 * 14 * 13 * 12 * 11 */
24024, /* 14 * 13 * 12 * 11 */
1716, /* 13 * 12 * 11 */
132, /* 12 * 11 */
11,
1,
};
/* 盤面を数値に変換 */
int board_to_number( char *board )
{
int buffer[6]; /* 0 - 5 までの位置を格納 */
int i, j, value = 0;
for( i = 0; i < SIZE; i++ ){
int p = board[i];
if( p < 6 ) buffer[p] = i;
}
for( i = 0; i < 6; i++ ){
value += table[i] * buffer[i];
for( j = i + 1; j < 6; j++ ){
if( buffer[i] < buffer[j] ) buffer[j]--;
}
}
return value;
}
/* 数値を盤面に変換：空白の位置を返す */
int number_to_board( int num, char *board )
{
int i, j;
char buffer[6];
memset( board, 6, SIZE );
for( i = 0; i < 5; i++ ){
buffer[i] = num / table[i];
num %= table[i];
}
buffer[i] = num;
for( i = 4; i >= 0; i-- ){
for( j = i + 1; j < 6; j++ ){
if( buffer[i] <= buffer[j] ) buffer[j]++;
}
}
for( i = 0; i < 6; i++ ){
board[ buffer[i] ] = i;
}
return buffer[0];
}
/* 初期化 */
void init( void )
{
check_table = malloc( MAX );
if( check_table == NULL ){
fprintf(stderr, "out of memory\n"); exit( 1 );
}
memset( check_table, NIL, MAX );
}
/* 駒を移動する */
int move_piece( int num, int move )
{
char board[SIZE];
int c = 0; /* 展開した局面数 */
int s, i, n, new_num;
s = number_to_board( num, board );
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 移動 */
board[s] = board[n];
board[n] = 0;
new_num = board_to_number( board );
if( check_table[new_num] == NIL ){
/* 登録 */
check_table[new_num] = move;
c++;
}
/* 元に戻す */
board[n] = board[s];
board[s] = 0;
}
return c;
}
/* 最長手数の局面を表示 */
void print_answer( int move )
{
int i;
for( i = 0; i < MAX; i++ ){
if( check_table[i] == move ){
int j;
char board[SIZE];
number_to_board( i, board );
for( j = 0; j < SIZE; j++ ){
printf("%d ", board[j] );
}
printf("\n");
}
}
}
/* 探索 */
void search( void )
{
int num, total = 1, move = 1;
/* 初手を展開 */
num = board_to_number( init_state );
check_table[num] = 0; /* 初期値 */
total += move_piece( num, move );
printf("%2d手 --- %d個\n", move, total );
/* ２手目以降の展開 */
for( ; ; move++ ){
int i, c = 0;
for( i = 0; i < MAX; i++ ){
if( check_table[i] == move ){
c += move_piece( i, move + 1 );
}
}
if( c == 0 ) break;
printf("%2d手 --- %d個\n", move + 1, c );
total += c;
}
print_answer( move );
printf("合計 %d 個\n", total );
}
int main()
{
int start, end;
start = clock();
init();
search();
end = clock();
printf("時間 %d\n", end - start );
return 0;
}
/*
* 変形版スライドパズル（その３）
*
* Copyright (C) 2001 by M.Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define NIL (-1)
#define SIZE 16
#define MAX 12108096
/* 隣接リスト
座標
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
*/
const char adjacent[SIZE][5] = {
1, 4, -1, -1, -1, /* 0 */
0, 2, 5, -1, -1, /* 1 */
1, 3, 6, -1, -1, /* 2 */
2, 7, -1, -1, -1, /* 3 */
0, 5, 8, -1, -1, /* 4 */
1, 4, 6, 9, -1, /* 5 */
2, 5, 7, 10, -1, /* 6 */
3, 6, 11, -1, -1, /* 7 */
4, 9, 12, -1, -1, /* 8 */
5, 8, 10, 13, -1, /* 9 */
6, 9, 11, 14, -1, /* 10 */
7, 10, 15, -1, -1, /* 11 */
8, 13, -1, -1, -1, /* 12 */
9, 12, 14, -1, -1, /* 13 */
10, 13, 15, -1, -1, /* 14 */
11, 14, -1, -1, -1, /* 15 */
};
/* 初期状態 */
char init_state[SIZE] = {
1, 1, 2, 2,
1, 1, 2, 2,
1, 3, 3, 2,
3, 3, 3, 0,
};
/* 手数を格納するテーブル */
char *check_table;
/* パスカルの三角形 */
int comb_table[15][15];
/* 初期化 */
void init_comb_table( void )
{
int i, j;
comb_table[0][0] = 1;
for( i = 1; i < 15; 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 board_to_number( char *board )
{
int space = 0, value1 = 0, value2 = 0;
int i, n1 = 15, r1 = 5, n2 = 10, r2 = 5;
for (i = 0; i < SIZE; i++){
switch( board[i] ){
case 0:
space = i; break;
case 1:
if( n1 > r1 && r1 > 0 ){
value1 += comb_table[--n1][r1--];
}
break;
case 2:
if( n2 > r2 && r2 > 0 ){
value2 +=comb_table[--n2][r2--];
}
n1--;
break;
default:
n1--;
n2--;
}
}
return space * 3003 * 252 + value1 * 252 + value2;
}
/* 変換 */
void decode( int value, char *board, int n, int r, int piece )
{
int i = 0;
while( n > r && r > 0 ){
int c = comb_table[--n][r];
while( board[i] != 3 ) i++;
if( value >= c ){
board[i] = piece;
r--;
value -= c;
}
i++;
}
while( r > 0 ){
while( board[i] != 3 ) i++;
board[i++] = piece;
r--;
}
}
/* 数値を盤面に変換 */
int number_to_board( int num, char *board )
{
int space, value1, value2, temp;
space = num / (3003 * 252);
temp = num % (3003 * 252);
value1 = temp / 252;
value2 = temp % 252;
memset( board, 3, SIZE );
board[space] = 0;
decode( value1, board, 15, 5, 1 );
decode( value2, board, 10, 5, 2 );
return space;
}
/* 初期化 */
void init( void )
{
check_table = malloc( MAX );
if( check_table == NULL ){
fprintf(stderr, "out of memory\n"); exit( 1 );
}
memset( check_table, NIL, MAX );
init_comb_table();
}
/* 駒を移動する */
int move_piece( int num, int move )
{
char board[SIZE];
int c = 0; /* 展開した局面数 */
int s, i, n, new_num;
s = number_to_board( num, board );
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 移動 */
board[s] = board[n];
board[n] = 0;
new_num = board_to_number( board );
if( check_table[new_num] == NIL ){
/* 登録 */
check_table[new_num] = move;
c++;
}
/* 元に戻す */
board[n] = board[s];
board[s] = 0;
}
return c;
}
/* 最長手数の局面を表示 */
void print_answer( int move )
{
int i;
for( i = 0; i < MAX; i++ ){
if( check_table[i] == move ){
int j;
char board[SIZE];
number_to_board( i, board );
for( j = 0; j < SIZE; j++ ){
printf("%d ", board[j] );
}
printf("\n");
}
}
}
/* 探索 */
void search( void )
{
int num, total = 1, move = 1;
/* 初手を展開 */
num = board_to_number( init_state );
check_table[num] = 0; /* 初期値 */
total += move_piece( num, move );
printf("%2d手 --- %d個\n", move, total );
/* ２手目以降の展開 */
for( ; ; move++ ){
int i, c = 0;
for( i = 0; i < MAX; i++ ){
if( check_table[i] == move ){
c += move_piece( i, move + 1 );
}
}
if( c == 0 ) break;
printf("%2d手 --- %d個\n", move + 1, c );
total += c;
}
print_answer( move );
printf("合計 %d 個\n", total );
}
int main()
{
int start, end;
start = clock();
init();
search();
end = clock();
printf("時間 %d\n", end - start );
return 0;
}