これは 8 puzzle を解くプログラムである．

-- 8 puzzleのルール

9(3*3)個のマス目に，8個の駒がおいてあり，1マスは空となっている．
例えば，以下の様に．
┌─┬─┬─┐
│０│１│２│
├─┼─┼─┤
│３│４│５│
├─┼─┼─┤
│６│７│  │
└─┴─┴─┘

空のマスには，隣のマスの駒を移動することができる．
空マスの上の駒を，下に動かすと 以下の様になる．
┌─┬─┬─┐      ┌─┬─┬─┐
│０│１│２│      │０│１│２│
├─┼─┼─┤      ├─┼─┼─┤
│３│４│５│  →  │３│４│  │
├─┼─┼─┤      ├─┼─┼─┤
│６│７│  │      │６│７│５│
└─┴─┴─┘      └─┴─┴─┘
空マスの左の駒を，右に動かすと 以下の様になる．
┌─┬─┬─┐      ┌─┬─┬─┐
│０│１│２│      │０│１│２│
├─┼─┼─┤      ├─┼─┼─┤
│３│４│５│  →  │３│４│５│
├─┼─┼─┤      ├─┼─┼─┤
│６│７│  │      │６│  │７│
└─┴─┴─┘      └─┴─┴─┘

この状態↓を「ゴールの状態」とする．
┌─┬─┬─┐
│０│１│２│
├─┼─┼─┤
│３│４│５│
├─┼─┼─┤
│６│７│  │
└─┴─┴─┘

ある状態から，「空マスの隣の駒を動かす」ことを繰り返して，ゴールの状態にすればクリア．

例えば，以下の状態からは，3手でクリアできる．
┌─┬─┬─┐
│０│  │２│
├─┼─┼─┤
│３│１│４│
├─┼─┼─┤
│６│７│５│
└─┴─┴─┘
　　↓１手目
┌─┬─┬─┐
│０│１│２│
├─┼─┼─┤
│３│  │４│
├─┼─┼─┤
│６│７│５│
└─┴─┴─┘
　　↓２手目
┌─┬─┬─┐
│０│１│２│
├─┼─┼─┤
│３│４│  │
├─┼─┼─┤
│６│７│５│
└─┴─┴─┘
　　↓３手目
┌─┬─┬─┐
│０│１│２│
├─┼─┼─┤
│３│４│５│　クリア！
├─┼─┼─┤
│６│７│  │
└─┴─┴─┘

- (問題1)
以下のプログラムを記述せよ．

main()関数の中のローカル変数として，以下を宣言，初期化を記述せよ．
char board[9]={0,1,2,3,4,8,6,7,5};

上記の データ(board)を，
以下の様に 横 3 マス，縦 3 マスの正方形型に表示せよ．
表示のための printf は main 関数の中に記述せよ．
012
34.
675

ただし，board[a]のデータは，正方形の横座標 a%3, 縦座標 a/3 に対応する．
例えば，board[5] は 横座標 2, 縦座標 1に対応する．

配列変数の中身が 0〜7 なら，そのマスに0〜7の駒があることを意味しており，その数字を表示する．
配列変数の中身が 8 なら，そのマスが空であることを意味しており . を表示する．


- (問題2)
以下のプログラムを記述せよ．

横 3 マス，縦 3 マスの正方形型に表示する関数 void print_board(char b[9], int depth) を作成し，
main()関数 より，print_board( board, 4) と呼び出しをせよ．
正方形方に表示する際は，左に depth 個の空白を表示し，その右に正方形方に表示せよ．
以下の様に表示されるはずである．
    012
    34.
    675

当然，表示のための printf は print_board 関数の中に記述せよ．

注意：
board は 参照呼び出しであるので，呼び出し先 print_board 内で配列 b[?] の中身を書き換えると，
呼び出し元の board[?] の値が変わってしまうことに注意せよ．
(基本的に，書き換えは行わない)


- (問題3)
グローバル変数 char log[ 362880 ]; を宣言せよ．
これは，ある状況を調査済みであるか否か を記録する配列で，
値が0なら「未調査」を，1なら「調査済み」を表す．
362880 は 9! である．(後述)

そして，以下の 関数を作成せよ．
この関数は，与えられた 8 puzzleの状態から，
「空マスの上の駒を下に動かした状態」，「空マスの下の駒を上に動かした状態」，
「空マスの左の駒を右に動かした状態」，「空マスの右の駒を左に動かした状態」
を再帰的に調べる関数である．

	名前が solve で，引数が char b[9], int depth で，戻り値が void で，
	呼び出されると，以下の様に動作する関数．

	print_board(b, depth) を呼び出し，引数b の 8 puzzleの状態を表示する．

	現在の状態が「ゴールの状態」か調べる．
	「ゴールの状態」であるなら"OK"と表示してexit(0);で終了する．

	現在の状態を「調査済みの状態一覧」に登録する．(後述)

	空マスが上端でなければ，
		char b[9] を char tmp[9] にコピーして，
		(memcpy(tmp, b, 9) により可能)
		tmpから「空マスの上の駒を下に(空マスに)移動した状態」を作る．
		その状態が，「調査済みでない」すなわち「調査済みの状態一覧」に登録されていないければ，
		この状態対して solve を呼び出し，この状態も調べる．depthは1増やして呼び出す．
		すなわち solve( tmp, depth+1); と呼び出す．

	空マスが下端でなければ，
		「空マスの下の駒を上に移動した状態」について同様の処理を行う．

	空マスが左端でなければ，
		「空マスの左の駒を右に移動した状態」について同様の処理を行う．

	空マスが右端でなければ，
		「空マスの右の駒を左に移動した状態」について同様の処理を行う．


(同じ状態の再調査による無限の調査と，その回避方法)
ある状態から再帰的に調べていくと，
以下の様に同じ状態を何度も調査してしまい，無限に調査が続いているしまう．
┌─┬─┬─┐
│０│  │２│
├─┼─┼─┤
│３│１│４│←この状態を「Ａ」と呼ぶとする．
├─┼─┼─┤
│６│７│５│
└─┴─┴─┘
      │
      ├───────┬───────┐
      ↓              ↓              ↓
┌─┬─┬─┐  ┌─┬─┬─┐  ┌─┬─┬─┐
│  │０│２│  │０│２│  │  │０│１│２│
├─┼─┼─┤  ├─┼─┼─┤  ├─┼─┼─┤
│３│１│４│  │３│１│４│  │３│  │４│
├─┼─┼─┤  ├─┼─┼─┤  ├─┼─┼─┤
│６│７│５│  │６│７│５│  │６│７│５│
└─┴─┴─┘  └─┴─┴─┘  └─┴─┴─┘
      │
      ├───────┐
      ↓              ↓
┌─┬─┬─┐
│０│  │２│
├─┼─┼─┤
│３│１│４│←再度，状態「Ａ」を調査してしまう．
├─┼─┼─┤
│６│７│５│
└─┴─┴─┘
      │
      ├───────┬───────┐
      ↓              ↓              ↓
┌─┬─┬─┐  ┌─┬─┬─┐  ┌─┬─┬─┐
│  │０│２│  │０│２│  │  │０│１│２│
├─┼─┼─┤  ├─┼─┼─┤  ├─┼─┼─┤
│３│１│４│  │３│１│４│  │３│  │４│←無限に続いてしまう．
├─┼─┼─┤  ├─┼─┼─┤  ├─┼─┼─┤
│６│７│５│  │６│７│５│  │６│７│５│
└─┴─┴─┘  └─┴─┴─┘  └─┴─┴─┘

各状態が「調査済み」であるか「未調査」であるかを 表す配列を作り，
調査済みの状況は再度調べないようにすれば良い．
そのためには，何らかの方法で「状態を一意な数値に変換」する必要がある．
例えば，「ある状態」が「数値 100」に変換されるなら，
log[100] にその状態が調査済みが否かを格納する．
「状態 から 一意な数値 への変換」は，以下の関数により可能．
今回はこれを copy and paste して使って良い．
int enc(char b[9]){
	char t[9];
	static int kaijo[9]={0};
	int sum, i;
	if( kaijo[0] == 0 ){
		int s;
		kaijo[0] = 1;
		for(s=1; s<9; s++){
			kaijo[s] = kaijo[s-1]*s;
		}
	}
	memcpy(t, b, 9);
	sum = 0;
	for(i=0; i<9; i++){
		int j;
		sum += t[i] * kaijo[9-1-i];
		for(j=1+i; j<9; j++){
			if( t[i] < t[j] ){
				t[j] --;
			}
		}
	}
	return sum;
}


- (問題4)
上記の solve 関数で 状態を再帰的に調査する際に，
「正解的に近いと予想される」状態から優先的に調査していくと，より高速に解ける様になる．

例えば「各駒が，正解の位置 と 現在の位置 で縦横何マスずれているか」の合計が少ない状態から
優先的に調査していくなど．