瑜伽弓步的体式:求哈密尔顿链问题（骑士周游问题）的求解高效算法。

我用C实现了一个高效算法。
此算法用不到1秒钟就可以算出结果啦！

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

int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
int start_i,start_j,end_i,end_j;
int maze[10][10];
int path[64][2];

void init()
{
int i,j;
for (i = 0; i <= 9; i++)
{
maze[0][i] = 0;
maze[9][i] = 0;
maze[i][0] = 0;
maze[i][9] = 0;
}
maze[1][1] = 2;
maze[1][8] = 2;
maze[8][1] = 2;
maze[8][8] = 2;
for (i = 2; i <= 7; i++)
{
maze[1][i] = 3;
maze[8][i] = 3;
maze[i][1] = 3;
maze[i][8] = 3;
}
for (i = 2; i <= 7; i++)
for (j = 2; j <= 7; j++)
{
maze[i][j] = 4;
}
maze[start_i][start_j]++;
maze[end_i][end_j]++;
}

void visit(int i, int j)
{
int k,new_i,new_j;
maze[i][j] = -maze[i][j];
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (maze[new_i][new_j] > 0)
{
maze[new_i][new_j]--;
}
}
}

void undo_visit(int i, int j)
{
int k,new_i,new_j;
maze[i][j] = -maze[i][j];
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (new_i >= 1 && new_i <= 8 && new_j >= 1 && new_j <= 8 && maze[new_i][new_j] >= 0)
{
maze[new_i][new_j]++;
}
}
}

int try_it(int n, int i, int j, int end_i, int end_j, int range)
{
int new_i,new_j,k,l,dir_select_num;
int dir_select[4][2];
int result;
result = 0;
path[n][0] = i;
path[n][1] = j;
if (i == end_i && j == end_j)
{
result = (n == 64 - 1);
return result;
}
dir_select_num = 0;
for (k = 0; k < 4; k++)
{
new_i = i + dir[k][0];
new_j = j + dir[k][1];
if (maze[new_i][new_j] > 0)
{
for (l = dir_select_num - 1; l >= -1; l--)
{
if (l == -1 || maze[new_i][new_j] >= dir_select[l][1])
{
dir_select[l+1][0] = k;
dir_select[l+1][1] = maze[new_i][new_j];
break;
}
dir_select[l+1][0] = dir_select[l][0];
dir_select[l+1][1] = dir_select[l][1];
}
dir_select_num++;
}
}
for (l = 0; l < dir_select_num; l++)
{
if (dir_select[l][1] > dir_select[0][1] + range)
{
break;
}
k = dir_select[l][0];
new_i = i + dir[k][0];
new_j = j + dir[k][1];
visit(i,j);
if (try_it(n+1,new_i,new_j,end_i,end_j,range))
{
undo_visit(i,j);
result = 1;
return result;
}
undo_visit(i,j);
}
return result;
}

int main(int argc, char **argv)
{
int i;
//printf("input start_i start_j end_i end_j: ");
//scanf("%d%d%d%d", &start_i,&start_j,&end_i,&end_j);
if (argc < 5)
{
printf("Usage: %s <start_i> <start_j> <end_i> <end_j>\n", argv[0]);
return 1;
}
start_i = atoi(argv[1]);
start_j = atoi(argv[2]);
end_i = atoi(argv[3]);
end_j = atoi(argv[4]);
if (start_i < 1 || start_i > 8 || start_j < 1 || start_j > 8)
{
printf("Input error!\n");
return 1;
}
if (end_i < 1 || end_i > 8 || end_j < 1 || end_j > 8)
{
printf("Input error!\n");
return 1;
}
if (((start_i + start_j + end_i + end_j)%2) != 1)
{
printf("No solutions!\n");
return 0;
}

init();
if (try_it(0,start_i,start_j,end_i,end_j,0))
{
for (i = 0; i < 64; i++)
{
printf("%d %d\n", path[i][0], path[i][1]);
}
printf("Find a solution!\n");
}
else if (try_it(0,end_i,end_j,start_i,start_j,0))
{
for (i = 64-1; i >= 0; i--)
{
printf("%d %d\n", path[i][0], path[i][1]);
}
printf("Find a solution!\n");
}
else
printf("Cannot find a solutions!\n");
return 0;
}