●プログラムリスト１
/*
* goat.c : スライドパズル Goat
*
* Copyright (C) 2002 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define SIZE 12
#define B1 9
#define B2 10
#define MAX_MOVE 55
/* プロトタイプ宣言 */
void solve( int, int, int );
/* 隣接リスト */
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,-1,-1,-1, /* 8 */
5, 8,10,-1,-1, /* 9 */
6, 9,11,-1,-1, /* 10*/
7,10,-1,-1,-1, /* 11*/
};
/* スタート */
const char init_state[SIZE] = {
1, 8,B1,B2,
2, 0, 7, 5,
3, 8, 4, 6,
};
/* ゴール */
const char final_state[SIZE] = {
1, 8,B1,B2,
2, 5, 7, 0,
3, 8, 4, 6,
};
/* 盤面 */
char board[SIZE];
/* 動かした位置, 移動先の位置 */
char move_position[MAX_MOVE + 1];
char moveto_position[MAX_MOVE + 1];
/* 計測用 */
int start;
/* 初期化 */
void init( void )
{
memcpy( board, init_state, SIZE );
move_position[0] = -1;
moveto_position[0] = -1;
}
/* 盤面の表示 */
void print_board( char *b )
{
const static char *piece_data[11] = {
"□", "┌", "│", "└", "┘", "羊", "狼", "‖", "─", "┐", " ",
};
int i;
for( i = 0; i < SIZE; i++ ){
printf( "%s", piece_data[ b[i] ] );
if( i == 3 || i == 7 || i == 11 ) printf("\n");
}
printf("\n");
}
/* 手順を表示 */
void print_answer( int m )
{
int i;
char work[SIZE];
memcpy( work, init_state, SIZE );
print_board( work );
for( i = 1; i <= m; i++ ){
int from = move_position[i];
int to = moveto_position[i];
if( work[from] == B1 ){
work[to] = B1;
work[to + 1] = B2;
work[from] = 0;
} else if( work[from] == B2 ){
work[to] = B2;
work[to - 1] = B1;
work[from] = 0;
} else {
work[to] = work[from];
work[from] = 0;
}
print_board( work );
}
printf("\n時間 %d\n", clock() - start );
exit( 0 );
}
/* 大きな駒を動かす */
void move_big_piece( int limit, int move, int space, int piece )
{
int new_space, new_place;
if( piece == B1 ){
/* 左へ */
board[space] = B1;
board[space + 1] = B2;
board[space + 2] = 0;
new_space = space + 2;
new_place = space + 1;
} else {
/* 右へ */
board[space] = B2;
board[space - 1] = B1;
board[space - 2] = 0;
new_space = space - 2;
new_place = space - 1;
}
move_position[move + 1] = new_space;
moveto_position[move + 1] = new_place;
/* 再帰呼び出し */
solve( limit, move + 1, new_space );
/* 元に戻す */
if( piece == B1 ){
board[space] = 0;
board[space + 1] = B1;
board[space + 2] = B2;
} else {
board[space] = 0;
board[space - 1] = B2;
board[space - 2] = B1;
}
}
/* 反復深化による探索 */
void solve( int limit, int move, int space )
{
if( move == limit ){
if( !memcmp( board, final_state, SIZE ) ){
print_answer( move );
}
} else {
int i, j;
for( i = 0; (j = adjacent[space][i]) != -1; i++ ){
int piece = board[j];
if( moveto_position[move] == j ) continue;
if( piece == B1 || piece == B2 ){
if( space < 4 ){
/* 移動可能 */
move_big_piece( limit, move, space, piece );
}
} else {
/* 移動する */
board[space] = piece;
board[j] = 0;
move_position[move + 1] = j;
moveto_position[move + 1] = space;
/* 再帰呼び出し */
solve( limit, move + 1, j );
/* 元に戻す */
board[space] = 0;
board[j] = piece;
}
}
}
}
int main()
{
int limit;
start = clock();
init();
for( limit = 1; limit < MAX_MOVE; limit++ ){
printf("***** %d 手目を探索中 *****\n", limit );
solve( limit, 0, 5 );
}
return 0;
}
戻る
●プログラムリスト２
/*
* goat_max.c : スライドパズル Goat
* 最長手数の局面を求める
*
* 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 B1 9
#define B2 10
#define NIL (-1)
#define HVAL 1814400
/* 状態数 */
#define MAX 5443200
/* 隣接リスト */
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,-1,-1,-1, /* 8 */
5, 8,10,-1,-1, /* 9 */
6, 9,11,-1,-1, /* 10*/
7,10,-1,-1,-1, /* 11*/
};
/* 初期状態 */
char init_state[SIZE] = {
1, 8,B1,B2,
2, 5, 7, 0,
3, 8, 4, 6,
};
/* 手数を格納するテーブル */
char *check_table;
/* 数値表 */
const int table[8] ={
181440, /* 9 * 8 * 7 * 6 * 5 * 4 * 3 */
20160, /* 8 * 7 * 6 * 5 * 4 * 3 */
2520, /* 7 * 6 * 5 * 4 * 3 */
360, /* 6 * 5 * 4 * 3 */
60, /* 5 * 4 * 3 */
12, /* 4 * 3 */
3, /* 3 */
1,
};
/* 盤面を数値に変換 */
int board_to_number( char *board )
{
int buffer[8]; /* 0 - 7 までの位置を格納 */
int i, j, b1, value = 0;
for( i = 0; i < SIZE; i++ ){
int p = board[i];
if( p < 8 ){
buffer[p] = i;
} else if( p == B1 ){
b1 = i;
}
}
/* 補正 */
for( i = 0; i < 8; i++ ){
if( buffer[i] > b1 ) buffer[i] -= 2;
}
for( i = 0; i < 8; i++ ){
value += table[i] * buffer[i];
for( j = i + 1; j < 8; j++ ){
if( buffer[i] < buffer[j] ) buffer[j]--;
}
}
return b1 * HVAL + value;
}
/* 数値を盤面に変換：空き場所の位置を返す */
int number_to_board( int num, char *board )
{
int i, j, b1;
char buffer[8];
b1 = num / HVAL;
num %= HVAL;
memset( board, 8, SIZE );
board[b1] = B1;
board[b1 + 1] = B2;
for( i = 0; i < 7; i++ ){
buffer[i] = num / table[i];
num %= table[i];
}
buffer[i] = num;
for( i = 6; i >= 0; i-- ){
for( j = i + 1; j < 8; j++ ){
if( buffer[i] <= buffer[j] ) buffer[j]++;
}
}
/* 補正 */
for( i = 0; i < 8; i++ ){
if( buffer[i] >= b1 ) buffer[i] += 2;
}
for( i = 0; i < 8; 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++ ){
/* 移動 */
int piece = board[n];
if( piece == B1 || piece == B2 ){
if( s >= 4 ) continue; /* 左右しか移動できない */
/* 大駒の移動 */
if( piece == B1 ){
board[s] = B1;
board[s + 1] = B2;
board[s + 2] = 0;
} else {
board[s] = B2;
board[s - 1] = B1;
board[s - 2] = 0;
}
} else {
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++;
}
/* 元に戻す */
if( piece == B1 ){
board[s] = 0;
board[s + 1] = B1;
board[s + 2] = B2;
} else if( piece == B2 ){
board[s] = 0;
board[s - 1] = B2;
board[s - 2] = B1;
} else {
board[n] = board[s];
board[s] = 0;
}
}
return c;
}
void print_board( char *b )
{
const static char *piece_data[11] = {
"□", "┌", "│", "└", "┘", "羊", "狼", "‖", "─", "┐", " ",
};
int i;
for( i = 0; i < SIZE; i++ ){
printf( "%s", piece_data[ b[i] ] );
if( i == 3 || i == 7 || i == 11 ) printf("\n");
}
printf("\n");
}
/* 最長手数の局面を表示 */
void print_answer( int move )
{
int i;
char board[SIZE];
for( i = 0; i < MAX; i++ ){
if( check_table[i] == move ){
number_to_board( i, board );
print_board( board );
}
}
}
/* 探索 */
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;
printf("***** 初期状態 *****\n");
print_board( init_state );
printf("********************\n");
start = clock();
init();
search();
end = clock();
printf("時間 %d\n", end - start );
return 0;
}
戻る
●プログラムリスト３
/*
* goat2.c : スライドパズル Goat
* 最長手数の局面を反復深化で解く
*
* Copyright (C) 2002 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define SIZE 12
#define B1 9
#define B2 10
#define MAX_MOVE 55
/* プロトタイプ宣言 */
void solve( int, int, int, int );
/* 隣接リスト */
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,-1,-1,-1, /* 8 */
5, 8,10,-1,-1, /* 9 */
6, 9,11,-1,-1, /* 10*/
7,10,-1,-1,-1, /* 11*/
};
/* 初期状態
*
* 狼‖┐
* ┘羊│─
* □─└┌
*/
const char init_state[SIZE] = {
6, 7,B1,B2,
4, 5, 2, 8,
0, 8, 3, 1,
};
/* ゴール */
const char final_state[SIZE] = {
1, 8,B1,B2,
2, 5, 7, 0,
3, 8, 4, 6,
};
/* 移動手数 */
int distance[11][SIZE] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* dummy */
0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, /* 1 */
1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, /* 2 */
2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, /* 3 */
4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, /* 4 */
2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, /* 5 */
5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, /* 6 */
3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, /* 7 */
1, 0, 1, 2, 2, 1, 2, 3, 1, 0, 1, 2, /* 8 */
2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, /* 9 */
3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 */
};
/* 盤面 */
char board[SIZE];
/* 動かした位置, 移動先の位置 */
char move_position[MAX_MOVE];
char moveto_position[MAX_MOVE];
/* 計測用 */
int start;
/* 下限値を求める */
int calc_lower_value( const char *board )
{
int i, j, d = 0;
/* B2 は除外する */
for( i = 0; i < SIZE; i++ ){
j = board[i];
if( j > 0 && j != B2 ) d += distance[j][i];
}
return d;
}
/* 初期化 */
void init( void )
{
memcpy( board, init_state, SIZE );
move_position[0] = -1;
moveto_position[0] = -1;
}
/* 盤面を表示する */
void print_board( char *b )
{
const static char *piece_data[11] = {
"□", "┌", "│", "└", "┘", "羊", "狼", "‖", "─", "┐", " ",
};
int i;
for( i = 0; i < SIZE; i++ ){
printf( "%s", piece_data[ b[i] ] );
if( i == 3 || i == 7 || i == 11 ) printf("\n");
}
printf("\n");
}
/* 手順を表示 */
void print_answer( int m )
{
int i;
char work[SIZE];
memcpy( work, init_state, SIZE );
print_board( work );
for( i = 1; i <= m; i++ ){
int from = move_position[i];
int to = moveto_position[i];
if( work[from] == B1 ){
work[to] = B1;
work[to + 1] = B2;
work[from] = 0;
} else if( work[from] == B2 ){
work[to] = B2;
work[to - 1] = B1;
work[from] = 0;
} else {
work[to] = work[from];
work[from] = 0;
}
print_board( work );
}
printf("\n時間 %d\n", clock() - start );
exit( 0 );
}
/* 大きな駒を動かす */
void move_big_piece( int limit, int move, int space, int piece, int low )
{
int new_space, new_place, new_low;
if( piece == B1 ){
/* 左へ */
board[space] = B1;
board[space + 1] = B2;
board[space + 2] = 0;
new_space = space + 2;
new_place = space + 1;
new_low = low + 1;
} else {
/* 右へ */
board[space] = B2;
board[space - 1] = B1;
board[space - 2] = 0;
new_space = space - 2;
new_place = space - 1;
new_low = low - 1;
}
move_position[move + 1] = new_space;
moveto_position[move + 1] = new_place;
/* 下限値による枝刈り */
if( new_low + move <= limit ){
solve( limit, move + 1, new_space, new_low );
}
/* 元に戻す */
if( piece == B1 ){
board[space] = 0;
board[space + 1] = B1;
board[space + 2] = B2;
} else {
board[space] = 0;
board[space - 1] = B2;
board[space - 2] = B1;
}
}
/* 反復深化＋下限値枝刈り法による探索 */
void solve( int limit, int move, int space, int low )
{
if( move == limit ){
if( !memcmp( board, final_state, SIZE ) ){
print_answer( move );
}
} else {
int i, j, new_low;
for( i = 0; (j = adjacent[space][i]) != -1; i++ ){
int piece = board[j];
if( moveto_position[move] == j ) continue;
if( piece == B1 || piece == B2 ){
if( space < 4 ){
/* 大きな駒を動かす */
move_big_piece( limit, move, space, piece, low );
}
} else {
/* 移動する */
board[space] = piece;
board[j] = 0;
move_position[move + 1] = j;
moveto_position[move + 1] = space;
new_low = low - distance[piece][j] + distance[piece][space];
/* 下限値による枝刈り */
if( new_low + move <= limit ){
solve( limit, move + 1, j, new_low );
}
/* 元に戻す */
board[space] = 0;
board[j] = piece;
}
}
}
}
int main()
{
int limit, low, space;
low = calc_lower_value( init_state );
/* 空き場所を探す */
for( space = 0; space < SIZE; space++ ){
if( !init_state[space] ) break;
}
start = clock();
init();
for( limit = low ; limit < MAX_MOVE; limit++ ){
fprintf( stderr, "***** %d 手目を探索中 *****\n", limit );
solve( limit, 0, space, low );
}
return 0;
}
戻る
●プログラムリスト４
/*
* goat3.c : スライドパズル Goat
* 最長手数の局面を反復深化で解く
* 駒 ─ を区別することで下限値を改善する
*
* Copyright (C) 2002 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define SIZE 12
#define B1 9
#define B2 10
#define MAX_MOVE 55
/* プロトタイプ宣言 */
void solve( int, int, int, int );
/* 隣接リスト */
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,-1,-1,-1, /* 8 */
5, 8,10,-1,-1, /* 9 */
6, 9,11,-1,-1, /* 10*/
7,10,-1,-1,-1, /* 11*/
};
/* 初期状態
*
* 狼‖┐
* ┘羊│─
* □─└┌
*/
const char init_state[SIZE] = {
6, 7,B1,B2, /* 5, 2, 0, 0 */
4, 5, 2, 8, /* 3, 0, 2, 3 */
0,11, 3, 1, /* 0, 0, 2, 5 */
};
/* ゴール */
const char final_state[SIZE] = {
1, 8,B1,B2,
2, 5, 7, 0,
3,11, 4, 6,
};
/* 移動手数 */
int distance[12][SIZE] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* dummy */
0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, /* 1 */
1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, /* 2 */
2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, /* 3 */
4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, /* 4 */
2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, /* 5 */
5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, /* 6 */
3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, /* 7 */
1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, /* 8 */
2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, /* 9 */
3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 */
3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, /* 11 */
};
/* 盤面 */
char board[SIZE];
/* 動かした位置, 移動先の位置 */
char move_position[MAX_MOVE];
char moveto_position[MAX_MOVE];
/* 計測用 */
int start;
/* 下限値を求める */
int calc_lower_value( const char *board )
{
int i, j, d = 0;
/* B2 は除外する */
for( i = 0; i < SIZE; i++ ){
j = board[i];
if( j > 0 && j != B2 ) d += distance[j][i];
}
return d;
}
/* 初期化 */
void init( void )
{
memcpy( board, init_state, SIZE );
move_position[0] = -1;
moveto_position[0] = -1;
}
/* 盤面を表示する */
void print_board( char *b )
{
const static char *piece_data[12] = {
"□", "┌", "│", "└", "┘", "羊", "狼", "‖", "─", "┐", " ", "─",
};
int i;
for( i = 0; i < SIZE; i++ ){
printf( "%s", piece_data[ b[i] ] );
if( i == 3 || i == 7 || i == 11 ) printf("\n");
}
printf("\n");
}
/* 手順を表示 */
void print_answer( int m )
{
int i;
char work[SIZE];
memcpy( work, init_state, SIZE );
print_board( work );
for( i = 1; i <= m; i++ ){
int from = move_position[i];
int to = moveto_position[i];
if( work[from] == B1 ){
work[to] = B1;
work[to + 1] = B2;
work[from] = 0;
} else if( work[from] == B2 ){
work[to] = B2;
work[to - 1] = B1;
work[from] = 0;
} else {
work[to] = work[from];
work[from] = 0;
}
print_board( work );
}
printf("\n時間 %d\n", clock() - start );
exit( 0 );
}
/* 大きな駒を動かす */
void move_big_piece( int limit, int move, int space, int piece, int low )
{
int new_space, new_place, new_low;
if( piece == B1 ){
/* 左へ */
board[space] = B1;
board[space + 1] = B2;
board[space + 2] = 0;
new_space = space + 2;
new_place = space + 1;
new_low = low + 1;
} else {
/* 右へ */
board[space] = B2;
board[space - 1] = B1;
board[space - 2] = 0;
new_space = space - 2;
new_place = space - 1;
new_low = low - 1;
}
move_position[move + 1] = new_space;
moveto_position[move + 1] = new_place;
/* 下限値による枝刈り */
if( new_low + move <= limit ){
solve( limit, move + 1, new_space, new_low );
}
/* 元に戻す */
if( piece == B1 ){
board[space] = 0;
board[space + 1] = B1;
board[space + 2] = B2;
} else {
board[space] = 0;
board[space - 1] = B2;
board[space - 2] = B1;
}
}
/* 反復深化による探索 */
void solve( int limit, int move, int space, int low )
{
if( move == limit ){
if( !memcmp( board, final_state, SIZE ) ){
/* 見つけたよ */
print_answer( move );
}
} else {
int i, j, new_low;
for( i = 0; (j = adjacent[space][i]) != -1; i++ ){
int piece = board[j];
if( moveto_position[move] == j ) continue;
if( piece == B1 || piece == B2 ){
if( space < 4 ){
/* 移動可能 */
move_big_piece( limit, move, space, piece, low );
}
} else {
/* 移動する */
board[space] = piece;
board[j] = 0;
move_position[move + 1] = j;
moveto_position[move + 1] = space;
new_low = low - distance[piece][j] + distance[piece][space];
/* 下限値による枝刈り */
if( new_low + move <= limit ){
solve( limit, move + 1, j, new_low );
}
/* 元に戻す */
board[space] = 0;
board[j] = piece;
}
}
}
}
int main()
{
int limit, low, space;
low = calc_lower_value( init_state );
/* 空き場所を探す */
for( space = 0; space < SIZE; space++ ){
if( !init_state[space] ) break;
}
start = clock();
init();
for( limit = low ; limit < MAX_MOVE; limit++ ){
fprintf( stderr, "***** %d 手目を探索中 *****\n", limit );
solve( limit, 0, space, low );
}
return 0;
}
戻る