１───２───３ ４───１───３ ４───３───６
│ │ │ │ │ │ │ │ │
│ Ａ │ Ｂ │ │ Ａ │ Ｂ │ │ Ａ │ Ｂ │
│ │ │ │ │ │ │ │ │
４───５───６ ５───２───６ ５───１───２
│ │ │ │ │ │ │ │ │
│ Ｃ │ Ｄ │ │ Ｃ │ Ｄ │ │ Ｃ │ Ｄ │
│ │ │ │ │ │ │ │ │
７───８───９ ７───８───９ ７───８───９
(1) 初期状態 (2) Ａを右回転 (3) Ｂを左回転
図：回転パズルの動作
1 から 9 までの数字が 4 つの正方形 (A, B, C, D) の頂点に配置にされています。回転パズルは 4 つの正方形を回転して数字の順番を並べ替えるパズルです。
(1) の状態で、正方形 A を右回転（時計回り）すると、数字 1, 2, 5, 4 が回転して (2) の状態になります。次に、正方形 B を左回転（反時計回り）すると、数字 1, 3, 6, 2 が回転して (3) の状態になります。このように、4 つの正方形を左回転または右回転して数字を並べ替えます。
それでは問題です。
９───８───７ １───２───３
│ │ │ │ │ │
│ Ａ │ Ｂ │ │ Ａ │ Ｂ │
│ │ │ │ │ │
４───５───６ ４───５───６
│ │ │ │ │ │
│ Ｃ │ Ｄ │ │ Ｃ │ Ｄ │
│ │ │ │ │ │
３───２───１ ７───８───９
ＳＴＡＲＴ ＧＯＡＬ
図：問題
START から GOAL までの最短手数を求めてください。この問題では、正方形の右回転または左回転を 1 手と数えることにします。同じ正方形を 2 回続けて右回転する場合は 1 手ではなく 2 手となります。ご注意くださいませ。
「回転パズル」の解答です。
今回の規則では、この問題が最長手数の局面になります。最長手数の局面を幅優先探索で求めたところ、最長手数の局面は全部で 20 通りありました。今回の問題はそのひとつです。生成された局面の総数は 362880 ( 9! ) 通りなので、このパズルは数字をランダムに配置しても解くことができます。
もちろん、規則を変更すると最長手数も変わります。たとえば、正方形は右回転だけに限定するとか、同じ正方形の連続回転を 1 手と数えるなど、興味のある方は試してみてください。
9 8 7 9 8 7 9 8 7 9 4 7 3 8 7 9 8 7 9 8 7 9 8 7 6 5 1 4 5 6 6 2 4 8 5 2 6 5 4 6 4 5 6 5 4 6 5 4 3 2 4 3 2 1 3 5 1 3 6 1 9 2 1 3 2 1 2 3 1 3 1 2 9 8 7 9 8 7 9 6 7 9 8 4 9 8 1 9 8 7 9 5 7 9 2 7 3 5 4 5 6 4 2 5 8 6 5 7 6 5 4 6 5 4 6 8 4 6 5 4 6 2 1 3 2 1 3 4 1 3 2 1 3 2 7 1 2 3 3 2 1 3 8 1 6 8 7 7 8 9 9 7 8 8 9 7 9 5 4 6 5 4 6 5 4 6 5 4 3 2 1 3 2 1 3 2 1 3 2 1
/*
* ccc.c : 回転パズル
*
* Copyright (C) 2004-2006 Makoto Hiroi
*/
/*
0 1 2 0-1-4-3 : 0
3 4 5 1-2-5-4 : 1
6 7 8 3-4-7-6 : 2
4-5-8-7 : 3
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 9
#define NIL (-1)
/* 回転の方向 */
#define R 0x00
#define L 0x01
/* 素数が良い */
#define HASH_SIZE 19997
/* 状態数 9! */
#define MAX_STATE 362880
/* 回転リスト */
char rotate_table[4][4] = {
0, 1, 4, 3,
1, 2, 5, 4,
3, 4, 7, 6,
4, 5, 8, 7,
};
/* 連結リスト */
typedef struct {
char board[SIZE];
int next;
} CELL;
/* ハッシュ表 */
int hash_table[HASH_SIZE];
/* キュー */
CELL state[MAX_STATE + 1]; /* +1 はワーク領域 */
int prev_state[MAX_STATE];
/* 初期状態 */
char init_state[SIZE] = {
9, 8, 7, 4, 5, 6, 3, 2, 1,
};
char final_state[SIZE] = {
1, 2, 3, 4, 5, 6, 7, 8, 9,
};
/* ハッシュ関数 */
int hash_value( int n )
{
int i, value = 0;
for( i = 0; i < SIZE; i++ ){
value = value * 10 + state[n].board[i];
}
return value % HASH_SIZE;
}
/* ハッシュ表への登録 */
int insert_hash( int i )
{
/* ハッシュ表のチェック */
int h = hash_value( i );
int n = hash_table[h];
/* 探索 */
while( n != NIL ){
if( memcmp( state[i].board, state[n].board, SIZE ) == 0 ){
return FALSE; /* 登録済み */
}
n = state[n].next;
}
/* 先頭に追加 */
state[i].next = hash_table[h];
hash_table[h] = i;
return TRUE;
}
/* 結果を出力 */
void print_answer( int n )
{
int i;
if( n > 0 ) print_answer( prev_state[n] );
for( i = 0; i < SIZE; i++ ){
printf("%d ", state[n].board[i] );
if( i == 2 || i == 5 || i == 8 ) printf("\n");
}
printf("\n");
}
/* 盤面の回転 */
void rotate_board( char *board, int n, int dir )
{
int piece;
char *rotate = rotate_table[n];
if( dir == R ){
/* 0, 1, 2, 3 -> 3, 0, 1, 2 */
piece = board[ rotate[3] ];
board[ rotate[3] ] = board[ rotate[2] ];
board[ rotate[2] ] = board[ rotate[1] ];
board[ rotate[1] ] = board[ rotate[0] ];
board[ rotate[0] ] = piece;
} else {
/* 0, 1, 2, 3, -> 1, 2, 3, 0 */
piece = board[ rotate[0] ];
board[ rotate[0] ] = board[ rotate[1] ];
board[ rotate[1] ] = board[ rotate[2] ];
board[ rotate[2] ] = board[ rotate[3] ];
board[ rotate[3] ] = piece;
}
}
/* 探索 */
void search( void )
{
int front = 0, rear = 1;
/* 初期化 */
memcpy( state[0].board, init_state, SIZE );
prev_state[0] = -1;
/* ハッシュ表への登録 */
insert_hash( 0 );
while( front < rear ){
int i;
for( i = 0; i < 8; i++ ){
/* 状態をコピー */
memcpy( state[rear].board, state[front].board, SIZE );
/* 回転 */
rotate_board( state[rear].board, i / 2, i & 0x01 );
prev_state[rear] = front;
if( !memcmp( state[rear].board, final_state, SIZE ) ){
/* 発見 */
print_answer( rear );
printf("総数 %d 個\n", rear );
return;
} else if( insert_hash( rear ) ){
/* 登録 */
rear++;
}
}
front++;
}
}
int main()
{
int i, start, end;
/* ハッシュ表の初期化 */
for( i = 0; i < HASH_SIZE; i++ ){
hash_table[i] = NIL;
}
start = clock();
search();
end = clock();
printf("時間 %d \n", end - start );
return 0;
}
/* end of file */
/*
* ccc_max.c : 回転パズル 最長手数を求める
*
* Copyright (C) 2004-2006 Makoto Hiroi
*/
/*
0 1 2 0-1-4-3 : 0
3 4 5 1-2-5-4 : 1
6 7 8 3-4-7-6 : 2
4-5-8-7 : 3
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 9
#define NIL (-1)
/* 回転の方向 */
#define R 0x00
#define L 0x01
/* 素数が良い */
#define HASH_SIZE 19997
/* 状態数 9! */
#define MAX_STATE 362880
/* 回転リスト */
char rotate_table[4][4] = {
0, 1, 4, 3,
1, 2, 5, 4,
3, 4, 7, 6,
4, 5, 8, 7,
};
/* 連結リスト */
typedef struct {
char board[SIZE];
int next;
} CELL;
/* ハッシュ表 */
int hash_table[HASH_SIZE];
/* キュー */
CELL state[MAX_STATE + 1]; /* +1 はワーク領域 */
char move[MAX_STATE];
/* 初期状態 */
char init_state[SIZE] = {
1, 2, 3, 4, 5, 6, 7, 8, 9,
};
/* ハッシュ関数 */
int hash_value( int n )
{
int i, value = 0;
for( i = 0; i < SIZE; i++ ){
value = value * 10 + state[n].board[i];
}
return value % HASH_SIZE;
}
/* ハッシュ表への登録 */
int insert_hash( int i )
{
/* ハッシュ表のチェック */
int h = hash_value( i );
int n = hash_table[h];
/* 探索 */
while( n != NIL ){
if( memcmp( state[i].board, state[n].board, SIZE ) == 0 ){
return FALSE; /* 登録済み */
}
n = state[n].next;
}
/* 先頭に追加 */
state[i].next = hash_table[h];
hash_table[h] = i;
return TRUE;
}
/* 結果を出力 */
void print_answer( int n )
{
int m = move[n - 1], c = 0, i;
while( move[--n] == m ){
c++;
for( i = 0; i < SIZE; i++ ){
printf("%d ", state[n].board[i] );
if( i == 2 || i == 5 || i == 8 ) printf("\n");
}
printf("\n");
}
printf("最長手数 %d 手、総数 %d 個\n", m, c );
}
/* 盤面の回転 */
void rotate_board( char *board, int n, int dir )
{
int piece;
char *rotate = rotate_table[n];
if( dir == R ){
/* 0, 1, 2, 3 -> 3, 0, 1, 2 */
piece = board[ rotate[3] ];
board[ rotate[3] ] = board[ rotate[2] ];
board[ rotate[2] ] = board[ rotate[1] ];
board[ rotate[1] ] = board[ rotate[0] ];
board[ rotate[0] ] = piece;
} else {
/* 0, 1, 2, 3, -> 1, 2, 3, 0 */
piece = board[ rotate[0] ];
board[ rotate[0] ] = board[ rotate[1] ];
board[ rotate[1] ] = board[ rotate[2] ];
board[ rotate[2] ] = board[ rotate[3] ];
board[ rotate[3] ] = piece;
}
}
/* 探索 */
void search( void )
{
int front = 0, rear = 1;
/* 初期化 */
memcpy( state[0].board, init_state, SIZE );
move[0] = 0;
/* ハッシュ表への登録 */
insert_hash( 0 );
while( front < rear ){
int i, n;
for( i = 0; i < 8; i++ ){
/* 状態をコピー */
memcpy( state[rear].board, state[front].board, SIZE );
/* 回転 */
rotate_board( state[rear].board, i / 2, i & 0x01 );
if( insert_hash( rear ) ){
/* 登録 */
move[rear] = move[front] + 1;
rear++;
}
}
front++;
}
printf("総数 %d 個\n", rear );
print_answer( rear );
}
int main()
{
int i, start, end;
/* ハッシュ表の初期化 */
for( i = 0; i < HASH_SIZE; i++ ){
hash_table[i] = NIL;
}
start = clock();
search();
end = clock();
printf("時間 %d \n", end - start );
return 0;
}
/* end of file */
(0) 9 8 7 A B 4 5 6 C D R : 右回転 3 2 1 L : 左回転 (1) (2) (3) (4) (5) (6) A:R A:R B:L A:R D:L C:R 4 9 7 5 4 7 5 7 6 8 5 6 8 5 6 8 5 6 5 8 6 8 9 6 8 4 9 4 7 9 4 9 1 3 4 1 3 2 1 3 2 1 3 2 1 3 2 1 3 7 2 7 9 2 (7) (8) (9) (10) (11) A:R A:R D:L B:R A:L 3 8 6 4 3 6 4 3 6 4 1 3 1 2 3 4 5 1 5 8 1 5 1 2 5 2 6 4 5 6 7 9 2 7 9 2 7 8 9 7 8 9 7 8 9