数字の並べ替え は、「おしどりの遊び」のように数字をペアで空いている場所に動かして、数字を順番に並べるパズルです。おしどりの遊びは 蛙跳びゲーム で簡単に説明しているので参考にしてください。今回の「続・数字の並べ替え」は、数字をペアではなく単独で動かして数字を順番に並べるパズルです。それでは問題です。
┌─┬─┬─┬─┬─┐ │１│２│３│４│ │スタート └─┴─┴─┴─┴─┘ ┌─┬─┬─┬─┬─┐ │ │４│３│２│１│ゴール └─┴─┴─┴─┴─┘ 図：続・数字の並べ替え（Ａ）
上図のスタートのように並んでいる数字を、ゴールのように逆順に並べ替える最短手順を求めてください。数字を動かす規則は次のとおりです。
数字をひとつ跳び越すことができるのは 蛙跳びゲーム と似ていますね。スタートの状態では、4 は隣が空き場所なので移動することができます。また、3 は隣に 4 がありますが、それを跳び越して空き場所へ移動することができます。ほかの数字は空き場所へ移動できません。
このパズルは、高木茂男氏の著書「パズル遊びへの招待」(PHP研究所 1994) の オンライン版 にある おしどりの遊びと入れ替え問題 を参考にさせていただきました。数字を逆順に並べることは同じですが、空き場所の位置が異なっているので少しだけ難しくなっていると思います。「パズル遊びへの招待・オンライン版」には興味深いパズルが多数紹介されています。パズル好きの方は要チェックです。
それから、もうひとつ数字の移動規則を少し変更したパズルを考えてみました。
┌─┬─┬─┬─┬─┐ │１│２│３│４│ │スタート └─┴─┴─┴─┴─┘ ┌─┬─┬─┬─┬─┐ │ │４│３│２│１│ゴール └─┴─┴─┴─┴─┘ 図：続・数字の並べ替え（Ｂ）
上図のスタートのように並んでいる数字を、ゴールのように逆順に並べ替える最短手順を求めてください。数字を動かす規則は次のとおりです。
このパズルは数字をふたつ跳び越すことができます。スタートの状態では、4 は隣が空き場所なので移動することができます。また、2 は隣に 3 と 4 がありますが、それらを跳び越して空き場所へ移動することができます。ほかの数字は空き場所へ移動できません。
興味のある方は、数字の種類を増やしてみるといいでしょう。[1 2 3 4 5 0] や [1 2 3 4 5 6 0] を逆順に並べ替えることができるか、調べてみるのも面白いと思います。
それでは問題１の解答を示します。下図に示すように最短手数は 12 手になります。数字の 0 が空き場所を表しています。
[ 0] 1 2 3 4 0 [ 1] 1 2 0 4 3 [ 2] 0 2 1 4 3 [ 3] 2 0 1 4 3 [ 4] 2 4 1 0 3 [ 5] 2 4 1 3 0 [ 6] 2 4 0 3 1 [ 7] 0 4 2 3 1 [ 8] 4 0 2 3 1 [ 9] 4 3 2 0 1 [10] 4 3 0 2 1 [11] 4 0 3 2 1 [12] 0 4 3 2 1 図：問題１の解答
実は、これが最長手数の局面なのです。ちなみに、[1 2 3 4 0] を [4 3 2 1 0] に並べ替える最短手数は 10 手にしかなりません。そこで、数字の種類を増やして最長手数の局面を探索したところ、結果は次のようになりました。
| 初期値 | 局面数 | 手数 | 最終局面 |
|---|---|---|---|
| 1 2 3 4 0 | 120 | 12 | 0 4 3 2 1 |
| 1 2 3 4 5 0 | 720 | 17 | 0 4 5 2 3 1 5 4 3 2 0 1 |
| 1 2 3 4 5 6 0 | 5040 | 25 | 0 6 5 4 3 2 1 |
| 1 2 3 4 5 6 7 0 | 40320 | 32 | 7 6 5 4 3 2 0 1 |
空き場所 ( 0 ) を含めた数字の種類を N 個とすると、数字の並び方は全部で N! 通りになります。局面数を見ると、どの場合も N! 通りの局面を生成していますね。しがたって、このパズルは数字をランダムに配置しても必ず解くことができます。
[0] 1 2 3 4 0 [1] 1 0 3 4 2 [2] 0 1 3 4 2 [3] 4 1 3 0 2 [4] 4 1 3 2 0 [5] 4 0 3 2 1 [6] 0 4 3 2 1 図：問題２の解答
それでは問題２の解答を示します。左図に示すように最短手数は 6 手になります。数字の 0 が空き場所を表しています。ちなみに、最長手数を調べたところ 8 手になりました。最長手数の局面は 9 個あって、その中のひとつが [4 3 2 1 0] です。この移動手順は示しませんので、息抜きや気分転換に考えてみてください。
次は、数字の種類を増やしてみましょう。[1 2 3 4 5 0] は [0 5 4 3 2 1] へ並び替えることができます。最短手数は 15 手で、これが最長手数の局面になります。ところが、[1 2 3 4 5 6 0] の場合、[0 6 5 4 3 2 1] へ並び替えることはできません。
並び替えが不可能なことは、「転倒数の偶奇性」で説明することができます。転倒数と偶奇性については 数字の並べ替え：偶奇性 をお読みくださいませ。
数字の並びは左から右へと定義し、空き場所は無視します。転倒数が偶数の並びを「偶順列」といい、転倒数が奇数の並びを「奇順列」といいます。たとえば、[1 2 3 4 5 6 0] は順番に並んでいるので転倒数は 0 となり、偶順列であることがわかります。これに対し、逆順 [0 6 5 4 3 2 1] の転倒数は 15 になるので奇順列になります。
このパズルでは、数字を隣の空き場所へ移動しても転倒数に変化はありません。数字を 2 つ跳び越す場合、自分よりも大きな数字と小さな数字、大きな数字 2 つ、小さな数字 2 つという 3 通りのパターンがありますが、どのパターンも転倒数の変化は偶数個にしかなりません。したがって、奇順列から偶順列へは移行できない、並び替えは不可能というわけです。転倒数の変化は 15 パズルの偶奇性 で詳しく説明しているので参考にしてください。
今度は、数字を N 個に増やして、それを逆順に並べ替えることを考えてみます。これは 数字の並べ替え と同じ結果になります。詳しい説明は n 個の数字を逆順に並べる場合 をお読みくださいませ。結果だけ書くと、数字の個数が 4m + 2, 4m + 3 (m = 1, 2, 3 ... ) の場合、逆順の並びが奇順列になるため並べ替えは不可能です。逆に、4m, 4m + 1 (m = 1, 2, 3 ... ) 個の場合は偶順列になりますが、これだけでは不十分で、偶順列ならば並べ替え可能であることを証明する必要があります。
それでは、並べ替えできることを証明してみましょう。なお、この証明は花谷さんから教えてもらいました。花谷さん、どうもありがとうございます。
花谷さんの証明は、N 個の数字の並びを 3 つの数字の並びに帰着させる方法です。説明の都合上、花谷さんの方法を少し変更していますが、基本的な考え方は同じです。今、数字が N 個ある並びを、左から順番に 1 から N - 3 まで並べることを考えます。いちばん小さな数字を見つけて、それを左端まで移動させればいいわけです。
移動させる数字を m としましょう。m の左側に空き場所がある場合は、m をひとつ左へ移動させることができます。これは自明ですね。そして、空き場所は m の右側へ移ります。m の右側に空き場所がある場合は、m の左隣にある数字を空き場所へ移動すればいいわけです。m の右隣が空き場所で、それが右端にある場合、m の左隣の数字は移動できません。この場合は、2 つ隣の数字を空き場所へ移動すればいいでしょう。
この手順を繰り返すことで、m を左端へ移動することができます。そして、今度は N - 1 個の数字の中で、いちばん小さな数字を m の右隣へ移動させればいいわけです。あとは、同じ手順を繰り返すだけです。簡単な例を示しましょう。
(1) ４ ３ ２ １ ０ (2) ４ ０ ２ １ ３ 空き場所を１の左側へ移動 (3) ４ ２ ０ １ ３ 空き場所を１の手前に移動 (4) ４ ２ １ ０ ３ １をひとつ左へ動かす (5) ４ ２ １ ３ ０ 空き場所を右へ移動 (6) ４ ０ １ ３ ２ １の左隣の２を空き場所へ移動 (7) ４ １ ０ ３ ２ １をひとつ左へ動かす (8) ４ １ ３ ０ ２ 空き場所を右へ移動 (9) ０ １ ３ ４ ２ ４を空き場所へ移動 (10) １ ０ ３ ４ ２ １を左へ動かす
(1) の [4 3 2 1 0] の中で、1 を左端へ動かします。(2) で 3 を空き場所へ移動しました。これで、(3), (4) のように 1 を左へひとつ動かすことができます。次は、(5), (6) のように、空き場所を右へひとつ動かし、1 の左隣の数字 2 を移動させれば、(7) のように 1 を左へ動かすことできます。これを繰り返すことで、(10) のように 1 を左端へ動かすことができます。
このように、N 個の数字の並びを 1 から N - 3 まで順番に並べることができます。ここで、最初の並びが偶順列だったとしましょう。この移動により偶奇性は変化しないので、全体の並びは偶順列のままです。ここで、1 から N - 3 までの並びに注目してください。数字は左から順番に並んでいるので、転倒数は 0 になります。全体の並びは偶順列のままですから、残り 3 つの数字 N - 2, N - 1, N の転倒数は偶数になるはずです。したがって、残りの数字の並びは偶順列であることがわかります。
数字 3 つの並びは、全部で 6 通りあります。
(1) N-2, N-1, N 転倒数 0 偶順列 (2) N-2, N, N-1 転倒数 1 (3) N-1, N-2, N 転倒数 1 (4) N-1, N, N-2 転倒数 2 偶順列 (5) N, N-2, N-1 転倒数 2 偶順列 (6) N, N-1, N-2 転倒数 1
偶順列は 3 通りあります。数字が 3 つの場合、図に示すように移動経路は巡路になります。
┌─────┐ Ａ─Ｂ─Ｃ─Ｄ 図：数字の移動経路
数字は経路にそってグルグル回るだけなので、(4) と (5) は (1) へ並べ替えることができますが、奇順列は (1) へ並べ替えることはできません。残り 3 つの数字は偶順列ですから、数字が N 個の偶順列は 1, 2, .... N （正順）に並べ替えることができます。
どの偶順列でも正順に並べ替えることができるのですから、逆に正順からどの偶順列へも並べ替えが可能です。したがって、どの偶順列からでもほかの偶順列へ並べ替えることができる、というわけです。
/*
* change_num1.c : 続・数字の並べ替え（最短手数を求める）
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define NOT_FOUND (-1)
#define MAX_SIZE 8
#define FORWARD 0
#define BACKWARD 1
#define NIL (-1)
/* 最大局面数 ( 8! + 1) */
#define MAX_STATE 40321
/* 連結リスト */
typedef struct {
char board[MAX_SIZE];
int next;
} CELL;
/* 状態 */
CELL *state;
char space_postion[MAX_STATE];
int prev_state[MAX_STATE];
char direction[MAX_STATE];
/* ハッシュ表 */
#define HASH_SIZE 19997
int hash_table[HASH_SIZE];
/* ハッシュ関数 */
int hash_value( int n, int size )
{
int i;
unsigned int 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 size )
{
int h = hash_value( i, size );
int n = hash_table[h];
/* 連結リストの探索 */
while( n != NIL ){
if( memcmp( state[i].board, state[n].board, size ) == 0 ){
return n; /* 登録済み */
}
n = state[n].next;
}
/* 先頭に追加 */
state[i].next = hash_table[h];
hash_table[h] = i;
return NOT_FOUND;
}
/* 結果を出力 */
void print_answer_forward( int n, int size )
{
int i;
if( n > 1 ) print_answer_forward( prev_state[n], size );
for( i = 0; i < size; i++ ){
printf("%d ", state[n].board[i] );
}
printf("\n");
}
void print_answer_backward( int n, int size )
{
do {
int i;
n = prev_state[n];
for( i = 0; i < size; i++ ){
printf("%d ", state[n].board[i] );
}
printf("\n");
} while( prev_state[n] != -1 );
}
void print_answer( int i, int j, int size )
{
if( direction[i] == FORWARD ){
print_answer_forward( i, size );
print_answer_backward( j, size );
} else {
print_answer_forward( j, size );
print_answer_backward( i, size );
}
}
/* 初期化 */
void init_data( int num )
{
int i;
/* 初期値 */
for( i = 0; i < num; i++ ){
state[0].board[i] = i + 1;
};
state[0].board[num] = 0;
space_postion[0] = num;
prev_state[0] = NIL;
direction[0] = FORWARD;
/* ゴール */
for( i = 1; i <= num; i++ ){
state[1].board[i] = num - i + 1;
};
state[1].board[0] = 0;
space_postion[1] = 0;
prev_state[1] = NIL;
direction[1] = BACKWARD;
/* ハッシュ表の初期化 */
for( i = 0; i < HASH_SIZE; i++ ){
hash_table[i] = NIL;
}
/* 登録 */
insert_hash( 0, num + 1 );
insert_hash( 1, num + 1 );
}
/* 探索関数 */
void search( int num )
{
int r = 0, w = 2, size = num + 1;
/* 初期化 */
init_data( num );
printf("----- %d 種類の探索 ----- \n", num );
for( ; r < w; r++ ){
int k = space_postion[r];
int i, j;
for( i = 0; i < size; i++ ){
/*
* 問題２のプログラムは if 文を次のように変更する
*
* if( i - 1 == k || i + 1 == k || i - 3 == k || i + 3 == k ){
*/
if( i - 1 == k || i + 1 == k || i - 2 == k || i + 2 == k ){
/* 盤面をコピーする */
memcpy( state[w].board, state[r].board, size );
state[w].board[k] = state[r].board[i];
state[w].board[i] = 0;
space_postion[w] = i;
direction[w] = direction[r];
prev_state[w] = r;
/* 検索する */
j = insert_hash( w, size );
if( j >= 0 ){
if( direction[j] != direction[w] ){
/* 解けた */
print_answer( j, w, size );
printf("状態数 %d 個\n", w );
return;
}
} else {
w++; /* 登録 */
if( w >= MAX_STATE ){
fprintf( stderr, "状態数オーバー\n" ); exit( 1 );
}
}
}
}
}
printf("状態数 %d 個\n", w );
}
int main()
{
int i, j, start, end;
state = malloc( sizeof( CELL ) * MAX_STATE );
if( state == NULL ){
fprintf( stderr, "Out of Memory\n" );
}
for( i = 3; i < 8; i++ ){
start = clock();
search( i );
end = clock();
printf("時間 %d\n", end - start );
}
return 0;
}
/*
* change_num1_max.c : 続・数字の並べ替え（最長手数の局面を求める）
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define NOT_FOUND (-1)
#define MAX_SIZE 8
#define NIL (-1)
/* 最大局面数 ( 8! + 1) */
#define MAX_STATE 40321
/* 連結リスト */
typedef struct {
char board[MAX_SIZE];
int next;
} CELL;
/* 状態 */
CELL *state;
char space_postion[MAX_STATE];
int prev_state[MAX_STATE];
int move_count[MAX_STATE];
/* ハッシュ表 */
#define HASH_SIZE 19997
int hash_table[HASH_SIZE];
/* ハッシュ関数 */
int hash_value( int n, int size )
{
int i;
unsigned int 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 size )
{
int h = hash_value( i, size );
int n = hash_table[h];
/* 連結リストの探索 */
while( n != NIL ){
if( memcmp( state[i].board, state[n].board, size ) == 0 ){
return n; /* 登録済み */
}
n = state[n].next;
}
/* 先頭に追加 */
state[i].next = hash_table[h];
hash_table[h] = i;
return NOT_FOUND;
}
/* 結果を出力 */
void print_answer( int w, int size )
{
int c = 0;
int max_move = move_count[--w];
printf("状態数 %d, 最長手数 %d 手\n", w + 1, max_move );
do {
int i;
for( i = 0; i < size; i++ ){
printf("%d ", state[w].board[i] );
}
printf("\n");
c++;
} while( move_count[--w] == max_move );
printf("総数 %d 個\n", c );
}
/* 初期化 */
void init_data( int num )
{
int i;
/* 初期値 */
for( i = 0; i < num; i++ ){
state[0].board[i] = i + 1;
};
state[0].board[num] = 0;
space_postion[0] = num;
prev_state[0] = NIL;
move_count[0] = 0;
/* ハッシュ表の初期化 */
for( i = 0; i < HASH_SIZE; i++ ){
hash_table[i] = NIL;
}
/* 登録 */
insert_hash( 0, num + 1 );
}
/* 探索関数 */
void search( int num )
{
int r = 0, w = 1, size = num + 1;
/* 初期化 */
init_data( num );
printf("----- %d 種類の探索 ----- \n", num );
for( ; r < w; r++ ){
int k = space_postion[r];
int i, j;
for( i = 0; i < size; i++ ){
if( i - 1 == k || i + 1 == k || i - 2 == k || i + 2 == k ){
/* 盤面をコピーする */
memcpy( state[w].board, state[r].board, size );
state[w].board[k] = state[r].board[i];
state[w].board[i] = 0;
space_postion[w] = i;
move_count[w] = move_count[r] + 1;
prev_state[w] = r;
/* 検索する */
j = insert_hash( w, size );
if( j < 0 ){
w++; /* 登録 */
}
}
}
}
print_answer( w, size );
}
int main()
{
int i, j, start, end;
state = malloc( sizeof( CELL ) * MAX_STATE );
if( state == NULL ){
fprintf( stderr, "Out of Memory\n" );
}
for( i = 3; i < 8; i++ ){
start = clock();
search( i );
end = clock();
printf("時間 %d\n", end - start );
}
return 0;
}