#include <stdio.h>
#include <string.h>



int a[12][12] = {0};
int flag = 0;


int hamilton(int i, int j);


void main(void)
{
	int i, j, k, m;
	//clrscr();

	i = 1;
	j = 1;

	for (i = 0; i < 12; i++) {
		a[0][i] = a[1][i] = a[i][0] = a[i][1] = -1;
		a[10][i] = a[11][i] = a[i][10] = a[i][11] = -1;
	}
	for (k = 0; k <= 11; k++) {
		for (m = 0; m <= 11; m++) {
			printf("%4d", a[k][m]);
		}
		printf("\n");
	}
	getchar();

	i = 1;
	j = 1;
	a[2][2] = 1;
	hamilton(i + 1, j + 1);

	for (k = 0; k <= 11; k++) {
		for (m = 0; m <= 11; m++) {
			printf("%4d", a[k][m]);
		}
		printf("\n");
	}
	getchar();



}


int hamilton(int i, int j)
{

	/*若為已經標記過的方格則返回*/
	if (a[i][j] != 0) {
		return 0;
	}

	flag++;
	a[i][j] = flag;


	/*判斷是否找到最后一個格子*/
	if (flag == 8 * 8) {
		/*判斷是否與第一個格子連成一個閉合和路線*/
		if (a[i - 1][j - 2] == 1) {
			return flag;
		}

		if (a[i - 2][j - 1] == 1) {
			return flag;
		}

		if (a[i - 2][j + 1] == 1) {
			return flag;
		}
		if (a[i - 1][j + 2] == 1) {
			return flag;
		}

		if (a[i + 1][j + 2] == 1) {
			return flag;
		}

		if (a[i + 2][j + 1] == 1) {
			return flag;
		}

		if (a[i + 2][j - 1] == 1) {
			return flag;
		}

		if (a[i + 1][j - 2] == 1) {
			return flag;
		}
	}


	/*尋找下一個有效格子*/
	if (hamilton(i - 1, j - 2)) {
		return flag;
	}

	if (hamilton(i - 2, j - 1)) {
		return flag;
	}

	if (hamilton(i - 2, j + 1)) {
		return flag;
	}
	if (hamilton(i - 1, j + 2)) {
		return flag;
	}

	if (hamilton(i + 1, j + 2)) {
		return flag;
	}

	if (hamilton(i + 2, j + 1)) {
		return flag;
	}

	if (hamilton(i + 2, j - 1)) {
		return flag;
	}

	if (hamilton(i + 1, j - 2)) {
		return flag;
	}

	/*若沒有符合要求的格子，則將格子還原并返回0*/
	a[i][j] = 0;
	flag--;
	return 0;


}