今回は Memorandum 2002 年 9 月 23 日 に出題したスライドパズル Goat を解いてみましょう。
[問題] スライドパズル Goat
┌─┬─┬───┐ ┌─┬─┬───┐
│┌┼─┼┐ │ │┌┼─┼┐ │
├┼┼─┼┼┬─┤ ├┼┼─┼┼┬─┤
│││ │‖│羊│ │││羊│‖│ │
├┼┼─┼┼┼─┤ ├┼┼─┼┼┼─┤
│└┼─┼┘│狼│ │└┼─┼┘│狼│
└─┴─┴─┴─┘ └─┴─┴─┴─┘
ＳＴＡＲＴ ＧＯＡＬ
図：スライドパズル Goat
‖ は扉を表します。当然ですが、大きな駒 (2 マス) は左右に動かすことができます。START から羊を囲いの中に入れる GOAL までの最短手順を求めてください。
このパズルは Goat や Get My Goat と呼ばれていて、スライドパズルではよく知られている問題です。今回のパズルは駒の種類と配置をちょっと変更しているので、最短手順はオリジナルの Goat とは異なります。ご注意ください。オリジナルの Goat については、未菜実さんの 数理パズル入門 にある スライドパズル が参考になります。
このパズルの場合、大きな駒の置き方は 3 通りしかありません。残りの場所は 10 か所ありますが、7 種類の駒 (┘ ┌ └ │ ‖ 羊 狼) と空き場所を配置して残り 2 か所に駒 ─ を配置すると 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 = 1,814,400 通りの置き方があります。したがって、局面の総数は 3 * 1814400 = 5,443,200 通りになります。ちょっと大きな数なので、今回は反復深化で解くことにしましょう。
最初は下限値枝刈り法を使わないでプログラムを作りましょう。盤面は 1 次元配列 board で表します。配列の添字と盤面の対応は下図のようになります。
┌─┬─┬─┬─┐ 0 : 空き場所 7 : ‖（扉）
│０│１│２│３│ 1 : ┌ 8 : ─
├─┼─┼─┼─┤ 2 : │ 9 : B1 大きな駒１
│４│５│６│７│ 3 : └ 10 : B2 大きな駒２
├─┼─┼─┼─┤ 4 : ┘
│８│９│10│11│ 5 : 羊
└─┴─┴─┴─┘ 6 : 狼
(1) 配列と盤面の対応 (2) 駒と番号の対応
図：盤面と駒の定義
次に駒を定義します。いつものように空き場所を 0 で表し、小さな駒を 1 から 8 までの数字で、大きな駒を B1 (9) と B2 (10) の 2 つに分けて表します。大きな駒を移動するときは、B1 と B2 をいっしょに動かすようにします。この処理がちょっとだけ複雑になりますが、あとのプログラムは単純な反復深化なので簡単です。
次はグローバル変数を定義します。
リスト：グローバル変数の定義
/* スタート */
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_postion[MAX_MOVE]; /* 動かした位置 */
char moveto_postion[MAX_MOVE]; /* 移動先の位置 */
配列 init_state は START の局面、final_state は GOAL の局面を表します。このパズルは駒 ─ が 2 つあるので、移動手順は動かす駒の位置で表すことにします。動かした駒の位置は配列 move_postion に格納します。それから、同じ駒を続けて動かすと元の局面に戻ってしまい、無駄な探索を行うことになります。これをチェックするために、移動先の位置を配列 moveto_postion に格納しておきます。
次は、反復深化で解を探索するプログラムを作ります。次のリストを見てください。
リスト：反復深化による探索
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;
}
}
}
}
関数 solve の引数 limit が反復深化の上限値、move が手数、space が空き場所の位置を表します。move が limit と等しくなったら、ゴールに到達したかチェックします。そうでなければ、駒を動かして次の局面を生成します。駒を動かす場合、同じ駒を続けて動かさないように moveto_postion をチェックします。このチェックを入れないと、実行速度はかなり遅くなるので注意してください。配列 adjacent はお馴染みの「隣接リスト」です。
動かす駒は変数 piece にセットします。piece が大きな駒ならば、左右にしか動かすことができません。space が 4 より小さければ、関数 move_big_piece で大きな駒を動かします。小さな駒を動かす処理は簡単ですね。詳細はリストをお読みくださいませ。
次は大きな駒を動かす関数 move_big_piece を作ります。
リスト：大きな駒を動かす
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;
}
}
引数 limit, move, space は関数 solve と同じです。piece は動かす駒の種類を表します。大きな駒は左から B1 (9), B2 (10) と並んでいるので、piece が B1 (9) ならば大きな駒を左へ動かすことになります。次の図を見てください。
０ １ ２ ３ ０ １ ２ ３
┌─┬─┬───┐ ┌─┬───┬─┐
│羊│空│B1 B2│ <=> │羊│B1 B2│空│
└─┴─┴───┘ └─┴───┴─┘
図：大きな駒の移動
space の位置に B1 を、space + 1 の位置に B2 を移動し、space は space + 2 の位置に移動します。B2 を動かす場合は、space の位置に B2 を、space - 1 の位置に B1 を移動し、space は space - 2 の位置に移動します。
このとき、move_position と moveto_position にセットするデータに注意してください。上図の状態で 2 にある駒 B1 を 1 へ移動した場合、空き場所は 1 から 3 へ移動します。このあと、2 の位置にある駒 B2 を 3 へ動かせば元の局面に戻りますね。したがって、B1 を移動したとき move_position に 2 を moveto_position に 1 をセットすると、同じ駒を連続で動かさないようにチェックする処理が動作しなくなるのです。
この場合は 3 にある駒 B2 を 2 に移動したとして、move_position には 3 を moveto_position には 2 をセットします。move_big_piece では、移動後の空き場所の位置を new_space に、new_space に隣接している大きな駒の位置を new_place に求めて、それを move_position と moveto_position にセットします。
あとはとくに難しいところはないと思います。詳細は プログラムリスト１ をお読みくださいませ。
それでは実行結果を示します。図では空き場所を □ で表しています。
(START)
┌─┐
│□‖羊
└─┘狼
(1) (2) (3) (4) (5)
┌□┐ ┌┐ □ ┌┐ 羊 ┌┐ 羊 ┌┐ 羊
│─‖羊 │─‖羊 │─‖□ │─□‖ │□─‖
└─┘狼 └─┘狼 └─┘狼 └─┘狼 └─┘狼
(6) (7) (8) (9) (10)
┌┐ 羊 ┌┐ 羊 ┌┐ 羊 ┌┐ 羊 ┌┐ □
│──‖ │──‖ │──‖ │──□ │──羊
└□┘狼 └┘□狼 └┘狼□ └┘狼‖ └┘狼‖
(11) (12) (13) (14) (15)
┌□┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
│──羊 │□─羊 │─□羊 │─羊□ │─羊‖
└┘狼‖ └┘狼‖ └┘狼‖ └┘狼‖ └┘狼□
(16) (17) (18) (19) (20)
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
│─羊‖ │─羊‖ │□羊‖ │羊□‖ │羊‖□
└┘□狼 └□┘狼 └─┘狼 └─┘狼 └─┘狼
図：実行結果
最短手数は 20 手になります。これは Memorandum 2002 年 9 月 30 日 で Y. N. さんが求めた手順と同じです。手数が短いので M.Hiroi のオンボロマシン (Pentium 166 MHz) でも 1 秒未満で解くことができました。
次は GOAL から始めて最長手数となる局面を幅優先探索で求めてみましょう。局面の総数は 5,443,200 通りもあるので、今回は スライディングブロックパズル(2) と同様に省メモリな方法を採用します。
最小完全ハッシュ関数とその逆関数を作成して、手数を格納する配列を用意します。最初に、配列を NIL (-1) に初期化しておきます。そして、初期状態（0 手）から始めて、1 手で到達する局面を生成して、配列に 1 を書き込みます。次に、配列から 1 手の局面を検索して、2 手で到達する局面を生成します。このとき、配列の値が NIL 以外の値であれば、すでに生成した局面であることがわかります。
あとは手数を延ばしていくだけです。巨大な配列を検索するのは時間がかかりますが、ここは高速 CPU にがんばってもらいましょう。
最小完全ハッシュ関数は、幅優先探索の高速化(1) で説明した「Ｎ！通りのパターンに 0 から N - 1 までの番号を付ける方法」と同様に作成することができます。
このパズルは、大きな駒の置き方が 3 通り、残りの駒の置き方は 1,814,400 通りあります。大きな駒を除いた盤面は、7 種類の駒 (┘ ┌ └ │ ‖ 羊 狼) と空き場所の配置により、0 から 1814399 までの数値に変換することができます。この値を I とすると、盤面のハッシュ値は大きな駒 B1 の位置 J (0, 1, 2) を使って、1814400 * J + I という式で計算することができます。これで盤面を 0 から 5443199 のハッシュ値に変換することができます。
それでは、ハッシュ値を求める関数 board_to_number を作りましょう。次のリストを見てください。
リスト：最小完全ハッシュ関数
/* 数値表 */
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;
}
最初のループで、0 から 7 までの駒の位置を求めて配列 buffer にセットし、大きな駒 B1 の位置を変数 b1 にセットします。次に駒の位置を補正します。大きな駒を除外して、0 から 9 までのマス 10 か所に駒を配置すると考えるわけです。そして、次のループで数値を計算します。やっていることは、「Ｎ！通りのパターンに 0 から N - 1 までの番号を付ける方法」と同じです。これで小さな駒の配置は 0 から 1814399 までの数値に変換され、
変数 value にセットされます。あとは b1 * HVAL (1814400) + 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] = 10;
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];
}
関数 number_to_board は空き場所の位置を返します。最初に、大きな駒 B1 の位置を求めて変数 b1 にセットし、num を小さな駒の配置を表す数値に変換します。そして、盤面を 8 で初期化してから、大きな駒をセットします。
次のループで、数値 num を 8 つの数字へ分解します。この段階では、数字はまだ駒の位置を表していません。次のループで、ハッシュ関数と逆の操作を行うことで、駒の位置を求めます。逆方向から数字をチェックし、数字が大きいか等しい場合は、その数字に 1 を加えます。これで駒の位置を復元することができます。
ただし、ここで求めた位置は 0 から 9 までのマス 10 か所に駒を配置する場合です。大きな駒は除外されているので、補正を行ってから駒を盤面にセットします。
あとは「スライディングブロックパズル(2)」で作成したプログラムとほとんど同じです。詳細は スライディングブロックパズル(2) と プログラムリスト２ をお読みくださいませ。
それでは実行結果を示します。最長手数は 52 手で、その局面は全部で 7 通りありました。
狼┐ ┌ □‖┐ □‖┐ ‖狼┐ ‖狼┐ 狼‖┐ 狼‖┐
‖羊│─ 狼┘│┌ 狼┘│─ ┘羊┌□ ┘羊│┌ ┘羊└┌ ┘羊│─
┘─└□ 羊─└─ ─羊└┌ ─└│─ □─└─ □─│─ □─└┌
図：最長手数 (52 手) の局面
実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で約 123 秒かかりました。ちなみに、生成した局面は全部で 5,443,200 個あります。しがたって、このパズルは小さな駒をランダムに配置しても、必ず GOAL に到達できることがわかります。
次は最長手数の局面を「反復深化」で解いてみましょう。
┌─┬─┬───┐ ┌─┬─┬───┐
│狼│‖├┐ │ │┌┼─┼┐ │
├┬┼─┼┼┬─┤ ├┼┼─┼┼┬─┤
├┘│羊││├─┤ │││羊│‖│ │
├─┼─┼┼┼─┤ ├┼┼─┼┼┼─┤
│ ├─┤└┤┌┤ │└┼─┼┘│狼│
└─┴─┴─┴┴┘ └─┴─┴─┴─┘
ＳＴＡＲＴ ＧＯＡＬ
問題：最長手数の局面
手数が 52 手と長いので、今回は「下限値枝刈り法」を使います。下限値を求める方法ですが、「ライン・パズル」下限値枝刈り法による高速化 で説明した「移動手数」を採用します。駒 ─ は 2 つありますが、その移動手数を求める方法がポイントです。次の図を見てください。
┌─┬─┬───┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│┌┼─┼┐ │ │１│０│１│２│ │０│１│２│３│
├┼┼─┼┼┬─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│││羊│‖│ │ │２│１│２│３│ │４│５│６│７│
├┼┼─┼┼┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│└┼─┼┘│狼│ │１│０│１│２│ │８│９│10│11│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
ＧＯＡＬ 駒 ─ の移動手数 番号
図：駒 ─ の移動手数表
駒 ─ に注目してください。1 番と 9 番は正しい位置なので、移動手数は 0 でいいですね。─ が 0 番にある場合、1 番に移動すれば 1 手ですが 9 番に移動すれば 3 手かかります。この場合は短い方の手数を移動手数とします。このとき、もうひとつの駒 ─ が 1 番にある場合は 9 番へ移動しなければいけませんが、それでも移動手数は 1 手とします。つまり、もうひとつの駒の位置を考慮しないで移動手数を求めるのです。下限値の精度は低下しますが、そのかわりプログラムは簡単になります。
移動手数は 2 次元配列 distance に格納します。
リスト：移動手数
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, /* B1 (9) */
3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* B2 (10) */
};
大きな駒は B1 と B2 に分けて表しているので、下限値を求めるときは移動手数を重複してカウントしないように注意してください。
次は、下限値枝刈り法のプログラムを作ります。次のリストを見てください。
リスト：下限値枝刈り法
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;
}
}
}
}
関数 solve の引数 limit が反復深化の上限値、move が手数、space が空き場所、low が下限値を表します。駒を動かしたら差分を計算して、新しい下限値 new_low を求めます。そして、new_low + move が上限値 limit を越えたら枝刈りを行います。limit 以下であれば solve を再帰呼び出しします。追加する処理はこれだけで、あとは反復深化のプログラムと同じです。
大きな駒を動かす関数 move_big_piece にも同様の処理を追加します。次のリストを見てください。
リスト：大きな駒を動かす（下限値枝刈り法）
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;
}
}
大きな駒を動かす場合、移動手数表 distance を使わなくても新しい下限値を簡単に求めることができます。大きな駒を左へ動かすと下限値 low は 1 つ増加し、右へ動かすと 1 つ減少します。新しい下限値を new_low にセットして、条件を満たしていれば solve を再帰呼び出しします。
あとは START の局面の下限値を求め、その手数から反復深化を実行するだけです。詳細は プログラムリスト３ をお読みくださいませ。
さっそく実行してみたところ、当然ですが手数は 52 手で、実行時間は M.Hiroi のオンボロマシンで 1012 秒（約 17 分）かかりました。下限値の精度が低いので、長い手数の問題はやっぱり時間がかかりますね。そこで、下限値の精度を改善してみましょう。
下限値の精度を改善するいちばん簡単な方法は、2 つある駒 ─ を区別することです。次のリストを見てください。
リスト：駒 ─ を区別する場合
/* ゴール */
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 */
};
GOAL の状態で上にある駒 ─ を 8 とし、下にある駒を 11 と定義します。そうすると、START の配置は「偶奇性」により決定することができます。15 パズルのようなスライドパズルの場合、Puzzle DE Programming 数字の並べ替え で説明した「転倒数」を使って偶奇性をチェックすることができます。次の図を見てください。
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│Ｉ┼Ｊ┼Ｋ┼Ｌ│ │１┼８┼９┼10│
├┼┼─┼─┼─┤ ├┼┼─┼─┼─┤
│Ｈ┼Ｇ┼Ｆ┼Ｅ│ │２┼５┼７┼０│
├─┼─┼─┼┼┤ ├─┼─┼─┼┼┤
│Ａ┼Ｂ┼Ｃ┼Ｄ│ │３┼11┼４┼６│
└─┴─┴─┴─┘ └─┴─┴─┴─┘
（１）経路 （２）ＧＯＡＬ
図：経路の定義
駒は位置 A から始まって経路 (A - B - C - F - E - D - G - H - I - J - K - L) に沿って並んでいると定義します。このとき、空き場所は無視してください。すると、GOAL の並びは [3, 11, 4, 6, 7, 5, 2, 1, 8, 9, 10] となります。ここで、数字の順番が逆になっているところに注目してください。
数字が順番に並んでいる場合、各数字の左側には自分より大きな数字はありません。ところが、GOAL の並びでは 3 以外の数字は左側に 11 がありますね。5 の左側には 6 と 7 もあります。このように、数字の順番が逆になっている個数を数え、その総数を「転倒数」と呼びます。そして、転倒数が奇数の場合を「奇順列」、偶数の場合を「偶順列」といいます。GOAL の場合、転倒数は次のようになります。
駒の並び [3, 11, 4, 6, 7, 5, 2, 1, 8, 9, 10] 転倒数 [0, 0, 1, 1, 1, 3, 6, 7, 1, 1, 1] = 22 (偶順列)
15 パズルのようなスライドパズルでは偶順列から奇順列へ移行することはできないので、START の局面も偶順列でなければいけません。詳しい説明は拙作のページ 偶奇性のお話 をお読みください。START の局面の偶奇性を調べると、次のようになります。
駒の並び [11, 3, 1, 8, 2, 5, 4, 6, 7, 9, 10] 転倒数 [ 0, 1, 2, 1, 3, 2, 3. 2, 2, 1, 1] = 18（偶順列） 駒の並び [8, 3, 1, 11, 2, 5, 4, 6, 7, 9, 10] 転倒数 [0, 1, 2, 0, 3, 2, 3. 2, 2, 1, 1] = 17（奇順列）
したがって、START の駒の配置は次のようになります。
const char init_state[SIZE] = {
6, 7,B1,B2,
4, 5, 2, 8,
0,11, 3, 1,
};
あとは盤面を表示する関数 print_board で、駒 11 の表示を追加します。プログラムの主な修正はこれだけです。詳細は プログラムリスト４ をお読みください。
さっそく実行してみたところ、実行時間は M.Hiroi のオンボロマシンで 511 秒（約 8.5 分）まで短縮することができました。約 2 倍の高速化に成功しましたが、移動手数を下限値とする方法では、これ以上の高速化は難しいかもしれません。
このほかには、高橋謙一郎さん が考案された ID (Invert Distance) や WD (Walking Distance) という方法があります。それらを使った 15 パズルの解法プログラムは抜群の性能を発揮しているようです。興味のある方は高橋さんのページ １５パズル自動解答プログラムの作り方 をご覧くださいませ。