15PuzzleSolver.c

#include <stdio.h>
#include <stdlib.h>
//#include <time.h> //デバッグ用

#define INF 1000000 //無限として定義する
#define FOUND -10 //完成したときに返す数字(なんでも良い)
#define SIZE 4 //ゲームの1辺の大きさ
#define SIZE_M SIZE-1 //計算時間短縮用引数
#define SIZE_S SIZE*SIZE //計算時間短縮用引数
#define SIZE_SM SIZE_S-1 //計算時間短縮用引数

#define ABS(a) ((a) * (((a) > 0) ? 1 : -1)) //絶対値を返す

typedef struct Puzzle Puzzle;
typedef struct Moves Moves;

// パズル面情報を保管する構造体
struct Puzzle{
	int *state; //タイルの状態を保管
	int bx; //空タイルのx座標
	int by; //空タイルのy座標
	char lm; //最後に動いた方向
};

// 推定最大動作回数とパズル面情報を保管する構造体
struct Moves{
	int h;
	Puzzle *p;
};

//パズル面動作クイックソート用
int comp(const void *a, const void *b){
	return (((Moves*)a)->h - ((Moves*)b)->h);
}

//ふたつのパズル面を比較する
int compare(Puzzle *p1, Puzzle *p2){
	int i;
	for (i = 0; i < SIZE_S; i++){
		if (p1->state[i] != p2->state[i]) return 0;
	}
	return 1;
}

// 入力を数字に変換する
int convert(char a){
	if ('1' <= a && a <= '9') return a - '0' - 1;
	else if ('a' <= a && a <= 'z') return a - 'a' + 9;
	else return SIZE_SM;
}

// マンハッタン距離を返す関数
int MD(Puzzle *puzzle){
	int i, md = 0;
	for (i = 0; i < SIZE_S; i++){
		if (puzzle->state[i] != SIZE_SM)
			md += (ABS(puzzle->state[i]%SIZE - i%SIZE) + ABS(puzzle->state[i]/SIZE - i/SIZE));
	}
	return md;
}

// インヴァージョンの合計を返す関数
int INV(Puzzle *puzzle){
	int i, j, inv = 0;
	for (i = 0; i < SIZE_S; i++){
		if (puzzle->state[i] != SIZE_SM){
			for (j = i+1; j < SIZE_S; j++){
				if (puzzle->state[i] > puzzle->state[j]) inv++;
			}
		}
	}
	return inv;
}

// パズル面aをbにコピーする
void copy_state(int *a, int *b){
	int i;
	for (i = 0; i < SIZE_S; i++) b[i] = a[i];
}

void swap(int *a, int *b){
	int t = *a;
	*a = *b;
	*b = t;
}

// パズルを動かす際に必ず行う動作
void move(Puzzle *p, Puzzle *mp){
	mp->state = malloc(SIZE_S * sizeof(int));
	copy_state(p->state, mp->state);
	swap(&mp->state[p->by*SIZE+p->bx], &mp->state[mp->by*SIZE+mp->bx]);
}

// 移動方向特有の動作
Puzzle* move_up(Puzzle *p){
	Puzzle *mp = malloc(sizeof(Puzzle));
	mp->bx = p->bx;
	mp->by = p->by-1;
	mp->lm = 'u';
	move(p, mp);
	return mp;
}

// 移動方向特有の動作
Puzzle* move_down(Puzzle *p){
	Puzzle *mp = malloc(sizeof(Puzzle));
	mp->bx = p->bx;
	mp->by = p->by+1;
	mp->lm = 'd';
	move(p, mp);
	return mp;
}

// 移動方向特有の動作
Puzzle* move_right(Puzzle *p){
	Puzzle *mp = malloc(sizeof(Puzzle));
	mp->bx = p->bx+1;
	mp->by = p->by;
	mp->lm = 'r';
	move(p, mp);
	return mp;
}

// 移動方向特有の動作
Puzzle* move_left(Puzzle *p){
	Puzzle *mp = malloc(sizeof(Puzzle));
	mp->bx = p->bx-1;
	mp->by = p->by;
	mp->lm = 'l';
	move(p, mp);
	return mp;
}

int search(Puzzle *puzzle, int g, int bound, Puzzle *goal){
	// バウンドを超えた計算をする際にはバウンドを拡張して再探査を要求
	int f = g + MD(puzzle);
	if (f > bound) return f;
	// ゴール状態が受理された場合は終了
	if (compare(puzzle, goal)) return FOUND;
	int min = INF;
	int available = 0;
	Moves moves[4];
	// 上下左右移動のパズル状態を生成し、マンハッタン距離と共にmovesに代入
	// 移動不可能な場合はマンハッタン距離の無限にする
	if (puzzle->bx > 0 && puzzle->lm != 'r'){
		moves[0].p = move_left(puzzle);
		moves[0].h = MD(moves[0].p);
		available++;
	}
	else moves[0].h = INF;
	if (puzzle->bx < SIZE_M && puzzle->lm != 'l'){
		moves[1].p = move_right(puzzle);
		moves[1].h = MD(moves[1].p);
		available++;
	}
	else moves[1].h = INF;
	if (puzzle->by > 0 && puzzle->lm != 'd'){
		moves[2].p = move_up(puzzle);
		moves[2].h = MD(moves[2].p);
		available++;
	}
	else moves[2].h = INF;
	if (puzzle->by < SIZE_M && puzzle->lm != 'u'){
		moves[3].p = move_down(puzzle);
		moves[3].h = MD(moves[3].p);
		available++;
	}
	else moves[3].h = INF;
	// 各移動先のマンハッタン距離が小さくなるようにソート
	qsort((void*)moves, 4, sizeof(moves[0]), comp);
	// マンハッタン距離が小さい順に次の移動を探査
	int t, i;
	for(i = 0; i < available; i++){
		t = search(moves[i].p, g+1, bound, goal);
		// 終了する場合はメモリ解放して終了を返す
		if (t == FOUND){
			int j;
			for (j = i; j < available; j++){
				free(moves[j].p->state);
				free(moves[j].p);
			}
			return FOUND;
		}
		if (t < min) min = t;
		free(moves[i].p->state);
		free(moves[i].p);
	}
	return min;
}

// IDA* による探査
// https://en.wikipedia.org/wiki/Iterative_deepening_A* のpseudocode参照
int ida_star(Puzzle *root, Puzzle *goal){
	int bound = MD(root), t;
	while(1){
		t = search(root, 0, bound, goal);
		if (t == FOUND)return bound;
		if (t == INF) return -1;
		bound = t;
	}
}


// THE UNIVERSITY OF BIRMINGHAM School of Computer Science 参照
// https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
int solvable(Puzzle *puzzle){
	int inv = INV(puzzle);
	if (SIZE % 2) return !(inv%2);
	else{
		if ((SIZE-puzzle->by-1)%2)return inv%2;
		else return !(inv%2);
	}
}

//入力を処理する関数
Puzzle *input_state(void){
	int i;
	char tmp;
	Puzzle *puzzle = malloc(sizeof(Puzzle));
	puzzle->state = malloc(SIZE_S * sizeof(int));
	for (i = 0; i < SIZE_S; ){
		scanf("%c", &tmp);
		if (tmp != ' ' && tmp != '\n' && tmp != '\t'){
			puzzle->state[i] = convert(tmp);
			i++;
		}
	}
	for (i = 0; i < SIZE_S; i++){
		if (puzzle->state[i] == SIZE_SM) break;
	}
	puzzle->bx = i%SIZE;
	puzzle->by = i/SIZE;
	puzzle->lm = '-';
	return puzzle;
}

int main(void){
	//clock_t t1 = clock(); // デバッグ用
	int i;
	// 入力処理
	Puzzle *initial_puzzle = input_state();
	Puzzle *final_puzzle = malloc(sizeof(Puzzle));
	final_puzzle->state = malloc(16 * sizeof(int));
	for (i = 0; i < SIZE_S; i++) final_puzzle->state[i] = i;
	// 完成可能であるか確認
	if (solvable(initial_puzzle)){
		printf("%d\n", ida_star(initial_puzzle, final_puzzle));
	}
	else{
		// 不可能である場合はメモリを解放し、終了
		printf("impossible\n");
		free(initial_puzzle->state);
		free(initial_puzzle);
	}
	// 終了状態のメモリ解放
	free(final_puzzle->state);
	free(final_puzzle);
	//printf("%f\n", ((float)(clock() - t1) / 1000000.0F ) * 1000); // デバッグ用
	return 0;
}