#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

void initail(int *,int *,int);
int game(int *,int);
void display(int *,int,int);
void swap(int *,int *);
void up(int *,int);
void down(int *,int);
void left(int *,int);
void right(int *,int);
void f1();
int find(int *,int);
int test(int *,int);
void end();

int count;

int main(){
int i,j,n;
int *table,*mark;
randomize();
clrscr();
fflush(stdin);
printf("Please input n : ");
scanf("%d",&n);
table = (int *)malloc(sizeof(int) * (n + 2) * (n + 2));
mark = (int *)malloc(sizeof(int) * n * n);
while(1){
	initail(table,mark,n);
	if(game(table,n) == 0)
		break;
	}
end();
return 0;
}
void initail(int *table,int *mark,int n){
	int i,j,ran;
	for(i = 0;i < n * n;i++)
		*(mark + i) = 1;
	for(i = 0;i < (n + 2) * (n + 2);i++)
		*(table + i) = -1;
	for(i = 1;i <= n;i++)
		for(j = 1;j <= n;j++){
			while(1){
				ran = random(n * n);
				if(*(mark + ran) == 1){
					*(mark + ran) = 0;
					break;
					}
				}
			*(table + i * (n + 2) + j) = ran;
			}
	}
int game(int *table,int n){
	int key;
	count = 0;
	while(1){
		display(table,n,count);
		key = getch();
		if(key == 27)
			return 0;
		else if(key == 59)
			f1();
		else if(key == 60)
			return 1;
		else if(key == 72)
			up(table,n);
		else if(key == 80)
			down(table,n);
		else if(key == 75)
			left(table,n);
		else if(key == 77)
			right(table,n);
		if(test(table,n) == 1){
			printf("\nPress any key to continue...!!");
			getch();
			return 1;
			}
		}
	}
void display(int *table,int n,int count){
	int i,j;
	clrscr();
	for(i = 1;i <= n;i++){
		printf("\n");
		for(j = 1;j <= n;j++)
			printf("[%3d]",*(table + i * (n + 2) + j));
			}
	printf("\n\n Total %d step !",count);
	}
int test(int *table,int n){
	int i,j;
	int count = 0;
	for(i = 1;i <= n;i++)
		for(j = 1;j <= n;j++)
			if(*(table + i * (n + 2) + j) == (i - 1) * n + j)
				count++;
	if(count == n * n - 1)
		return 1;
	else
		return 0;
	}
void swap(int *x,int *y){
	int temp;
	temp = *x;
	*x = *y;
	*y = temp;
	}
int find(int *table,int n){
	int i,j;
	for(i = 1;i <= n;i++)
		for(j = 1;j <= n;j++)
			if(*(table + i * (n + 2) + j) == 0)
				return (i * (n + 2) + j);
	return 0;
	}
void up(int *table,int n){
	if(*(table + find(table,n) + (n + 2)) != -1){
		swap(table + find(table,n),table + find(table,n) + (n + 2));
		count++;
		}
	}
void down(int *table,int n){
	if(*(table + find(table,n) - (n + 2)) != -1){
		swap(table + find(table,n),table + find(table,n) - (n + 2));
		count++;
		}
	}
void left(int *table,int n){
	if(*(table + find(table,n) + 1) != -1){
		swap(table + find(table,n),table + find(table,n) + 1);
		count++;
		}
	}
void right(int *table,int n){
	if(*(table + find(table,n) - 1) != -1){
		swap(table + find(table,n),table + find(table,n) - 1);
		count++;
		}
	}
void f1(){
	clrscr();
	printf("\n   ************************* Help Page ***********************");
	printf("\n   Esc : Exit this game .");
	printf("\n   F1 : This help page .");
	printf("\n   F2 : Start a new game .");
	printf("\n   -----------------------------------------------------------");
	printf("\n   Use \"up\",\"down\",\"left\" and \"right\" to control this puzzle !");
	printf("\n   ***********************************************************\n");
	getch();
	}
void end(){
	clrscr();
	printf("\nPuzzle version 1.0");
	printf("\nWritten by Einstein 1999/04/28");
	printf("\nThanks for your using !");
	printf("\nAll rights reserved !");
	printf("\nPress any key to continue....!");
	getch();
	}