「15 パズル」でお馴染みのスライドパズルです。それでは問題です。
┌───┬─┬─┐ ┌─┬─┬───┐ ┌───┬─┬─┐
│ 電球 │Ｏ│Ｎ│ │Ｎ│Ｏ│ 電球 │ │ 電球 │Ｎ│Ｏ│
├─┬─┼─┼─┤ ├─┼─┼─┬─┤ ├─┬─┼─┼─┤
│Ｏ│Ｆ│Ｆ│ │ │Ｆ│Ｏ│Ｆ│ │ │Ｏ│Ｆ│Ｆ│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
問題Ａ 問題Ｂ ＧＯＡＬ
図：NO-OFF
問題 A, B から GOAL までの最短手順を求めてください。
スライドパズル NO-OFF は、問題 A の "ON-OFF" を GOAL のように "NO-OFF" にチェンジするパズルです。NO-OFF は芦ヶ原伸之氏が考案されたパズルで、C MAGAZINE 1991 年 1 月号の「Ｃマガ電脳クラブ」でも出題されています。問題 B は GOAL からの最長手数の局面のひとつです。このパズルは局面の総数が少ないにもかかわらず、手数がけっこうかかる面白いパズルです。
このパズルは局面の総数が 540 通りしかありません。
電球(3 通り) * 空き場所(6 通り) * N (5 通り) * O (4C2 = 6 通り) = 540 通り
プログラムを作るのであれば、幅優先探索で簡単に解を求めることができます。ちなみに、GOAL までの最長手数は 56 手で、局面は全部で 3 通りあります。問題 B はその中の 1 つです。
┌─┬─┬───┐ ┌─┬─┬───┐ ┌─┬─┬───┐
│Ｆ│Ｎ│ 電球 │ │Ｎ│Ｏ│ 電球 │ │Ｏ│Ｆ│ 電球 │
├─┼─┼─┬─┤ ├─┼─┼─┬─┤ ├─┼─┼─┬─┤
│Ｏ│Ｏ│Ｆ│ │ │Ｆ│Ｏ│Ｆ│ │ │Ｎ│Ｏ│ │Ｆ│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
図：最長手数の局面
/*
* no_off.c : NO-OFF puzzle
*
* Copyright (C) 2004-2006 Makoto Hiroi
*/
/*
大駒 [L] = 3 通り
3 * 6 * 5 * 4C2 = 3 * 6 * 5 * 6 = 540
space = 0
[L] 1, 2
N 3
F 4
O 5
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 8
#define MAX_STATE 540
#define S 0
#define L1 1
#define L2 2
#define N 3
#define F 4
#define O 5
/* 隣接リスト */
/* 0 1 2 3
4 5 6 7 */
const char adjacent[SIZE][4] = {
1, 4, -1, -1, /* 0 */
0, 2, 5, -1, /* 1 */
1, 3, 6, -1, /* 2 */
2, 7, -1, -1, /* 3 */
0, 5, -1, -1, /* 4 */
1, 4, 6, -1, /* 5 */
2, 5, 7, -1, /* 6 */
3, 6, -1, -1, /* 7 */
};
/* キュー */
char state[MAX_STATE + 1][SIZE]; /* +1 はワーク領域 */
char space_position[MAX_STATE];
short prev_state[MAX_STATE];
/* 問題 A : 44 move*/
char init_state0[SIZE] = {
L1, L2, O, N,
O, F, F, S,
};
/* 36 move */
char init_state1[SIZE] = {
O, N, L1, L2,
O, F, F, S,
};
/* 問題 B: 56 move */
char init_state[SIZE] = {
N, O, L1, L2,
F, O, F, S,
};
/* 最終状態 */
char final_state[SIZE] = {
L1, L2, N, O,
O, F, F, S,
};
/* 同じ状態があるか */
int check_same_state( int n )
{
int i;
for( i = 0; i < n; i++ ){
if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
}
return FALSE;
}
/* 結果を出力 */
void print_answer( int n )
{
int i;
static char piece_table[6] = {
'_', 'L', 'L', 'N', 'F', 'O',
};
if( n != 0 ) print_answer( prev_state[n] );
for( i = 0; i < SIZE; i++ ){
if( i == 4 ) printf("\n");
printf("%c ", piece_table[ state[n][i] ] );
}
printf("\n\n");
}
/* 探索 */
void search( void )
{
int front = 0, rear = 1, i;
/* 初期化 */
memcpy( state[0], init_state, SIZE );
space_position[0] = 7;
prev_state[0] = -1;
while( front < rear ){
int s = space_position[front];
int n, piece;
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 状態をコピー */
memcpy( state[rear], state[front], SIZE );
/* 移動 */
piece = state[rear][n];
if( piece == L1 && s > n ) continue; /* 電球は左へ動けない */
if( piece == L2 && s > 3 ) continue; /* 電球は右へ動けない */
if( piece == L1 ){
/* 電球を左へ動かす */
state[rear][s] = state[rear][n];
state[rear][n] = state[rear][n + 1];
state[rear][n + 1] = S;
space_position[rear] = n + 1;
} else if( piece == L2 ){
/* 電球を右へ動かす */
state[rear][s] = state[rear][n];
state[rear][n] = state[rear][n - 1];
state[rear][n - 1] = S;
space_position[rear] = n - 1;
} else {
state[rear][s] = state[rear][n];
state[rear][n] = S;
space_position[rear] = n;
}
prev_state[rear] = front;
if( !memcmp( state[rear], final_state, SIZE ) ){
print_answer( rear );
printf("状態数 %d 個\n", rear );
return;
} else if( !check_same_state( rear ) ){
/* 登録 */
rear++;
}
}
front++;
}
}
int main()
{
int start, end;
start = clock();
search();
end = clock();
printf("時間 %d \n", end - start );
return 0;
}
/*
* no_off_max.c : NO-OFF puzzle 最長手数を求める
*
* Copyright (C) 2004-2006 Makoto Hiroi
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 8
#define MAX_STATE 540
#define S 0
#define L1 1
#define L2 2
#define N 3
#define F 4
#define O 5
/* 隣接リスト */
/* 0 1 2 3
4 5 6 7 */
const char adjacent[SIZE][4] = {
1, 4, -1, -1, /* 0 */
0, 2, 5, -1, /* 1 */
1, 3, 6, -1, /* 2 */
2, 7, -1, -1, /* 3 */
0, 5, -1, -1, /* 4 */
1, 4, 6, -1, /* 5 */
2, 5, 7, -1, /* 6 */
3, 6, -1, -1, /* 7 */
};
/* キュー */
char state[MAX_STATE + 1][SIZE]; /* +1 はワーク領域 */
char space_position[MAX_STATE];
short move[MAX_STATE];
/* 初期状態 */
char init_state[SIZE] = {
L1, L2, N, O,
O, F, F, S,
};
/* 同じ状態があるか */
int check_same_state( int n )
{
int i;
for( i = 0; i < n; i++ ){
if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
}
return FALSE;
}
/* 結果を出力 */
void print_answer( int n )
{
int i, m = move[n];
static char piece_table[6] = {
'_', 'L', 'L', 'N', 'F', 'O',
};
printf( "最長手数 %d 手\n", m );
while( move[n--] == m ){
for( i = 0; i < SIZE; i++ ){
if( i == 4 ) printf("\n");
printf("%c ", piece_table[ state[n][i] ] );
}
printf("\n\n");
}
}
/* 探索 */
void search( void )
{
int front = 0, rear = 1, i;
/* 初期化 */
memcpy( state[0], init_state, SIZE );
space_position[0] = 7;
move[0] = 0;
while( front < rear ){
int s = space_position[front];
int n, piece;
for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
/* 状態をコピー */
memcpy( state[rear], state[front], SIZE );
/* 移動 */
piece = state[rear][n];
if( piece == L1 && s > n ) continue; /* 電球は左へ動けない */
if( piece == L2 && s > 3 ) continue; /* 電球は右へ動けない */
if( piece == L1 ){
/* 電球を左へ動かす */
state[rear][s] = state[rear][n];
state[rear][n] = state[rear][n + 1];
state[rear][n + 1] = S;
space_position[rear] = n + 1;
} else if( piece == L2 ){
/* 電球を右へ動かす */
state[rear][s] = state[rear][n];
state[rear][n] = state[rear][n - 1];
state[rear][n - 1] = S;
space_position[rear] = n - 1;
} else {
state[rear][s] = state[rear][n];
state[rear][n] = S;
space_position[rear] = n;
}
if( !check_same_state( rear ) ){
/* 登録 */
move[rear] = move[front] + 1;
rear++;
}
}
front++;
}
printf("状態数 %d\n", rear );
print_answer( rear - 1 );
}
int main()
{
int start, end;
start = clock();
search();
end = clock();
printf("時間 %d \n", end - start );
return 0;
}
L L が電球を表し、_ が空き場所を表します。
(0) (1) (2) (3) (4) (5) (6) (7) L L O N L L O _ L L _ O _ L L O O L L O O L L O O L L O O L L O O F F _ O F F N O F F N O F F N _ F F N F _ F N F F _ N F F N _ (8) (9) (10) (11) (12) (13) (14) (15) O L L _ O _ L L _ O L L F O L L F O L L F _ L L F L L _ F L L O F F N O F F N O F F N O _ F N O F _ N O F O N O F O N O F O N _ (16) (17) (18) (19) (20) (21) (22) (23) F L L O F L L O F L L O _ L L O L L _ O L L O _ L L O N L L O N F O _ N F _ O N _ F O N F F O N F F O N F F O N F F O _ F F _ O (24) (25) (26) (27) (28) (29) (30) (31) L L _ N _ L L N F L L N F L L N F L L N F L L N F L L _ F _ L L F F O O F F O O _ F O O F _ O O F O _ O F O O _ F O O N F O O N (32) (33) (34) (35) (36) (37) (38) (39) F O L L F O L L _ O L L O _ L L O L L _ O L L N O L L N O L L N F _ O N _ F O N F F O N F F O N F F O N F F O _ F F _ O F _ F O (40) (41) (42) (43) (44) O L L N _ L L N L L _ N L L N _ L L N O _ F F O O F F O O F F O O F F O O F F _
L L が電球を表し、_ が空き場所を表します。
(0) (1) (2) (3) (4) (5) (6) (7) N O L L N O L L N O L L N _ L L N L L _ N L L F N L L F N L L F F O F _ F O _ F F _ O F F O O F F O O F F O O _ F O _ O F _ O O (8) (9) (10) (11) (12) (13) (14) (15) N L L F _ L L F L L _ F L L F _ L L F O L L F O L L _ O _ L L O _ F O O N F O O N F O O N F O O N F O _ N F _ O N F F O N F F O (16) (17) (18) (19) (20) (21) (22) (23) N L L O N L L O N L L O N L L O N L L _ N _ L L _ N L L F N L L _ F F O F _ F O F F _ O F F O _ F F O O F F O O F F O O _ F O O (24) (25) (26) (27) (28) (29) (30) (31) F N L L F _ L L F L L _ F L L O F L L O F L L O F L L O _ L L O F _ O O F N O O F N O O F N O _ F N _ O F _ N O _ F N O F F N O (32) (33) (34) (35) (36) (37) (38) (39) L L _ O L L N O L L N O L L N _ L L _ N _ L L N F L L N F L L N F F N O F F _ O F F O _ F F O O F F O O F F O O _ F O O F _ O O (40) (41) (42) (43) (44) (45) (46) (47) F L L N F L L N F L L _ F _ L L F O L L F O L L _ O L L O _ L L F O _ O F O O _ F O O N F O O N F _ O N _ F O N F F O N F F O N (48) (49) (50) (51) (52) (53) (54) (55) O L L _ O L L N O L L N O L L N O L L N _ L L N L L _ N L L N _ F F O N F F O _ F F _ O F _ F O _ F F O O F F O O F F O O F F O (56) L L N O O F F _