Knight's Tour using non-recursive programing

解法：

騎士的走法，基本上可以使用遞迴來解決，但是純綷的遞迴在維度大時相當沒有效率，一個聰明的解法由J.C. Warnsdorff在1823年提出，簡單的說，先將最難的位置走完，接下來的路就寬廣了，騎士所要走的下一步，「為下一步再選擇時，所能走的步數最少 的一步。」，使用這個方法，在不使用遞迴的情況下，可以有較高的機率找出走法（找不到走法的機會也是有的）。

演算法：

for (step = 1; step < 總格數 ; step++)
{
測試下一步可以走的八個方向，並記錄下步可走的格數。

if ( 下步可走格數 == 0 )
{
return 0;
}
else if ( 可走格數 == 1 )
{
下一步只有一種可能
}
else
{
重複 if 內容找出下一步的下一步可走的最少格來走，藉此提升行走效率，
如果計算到最少格有相同者，則選第一順位來走。
}
檢查stack，找出最少出路的那一步，並replace騎士的位置，
再下一個for loop則由此新位置來走。
}

//----------------------------------------------------------------------------------------------
//若是8*8的棋盤，其中 (5,4) 這點無解
程式碼：

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

#define col_size 8
#define row_size 8

typedef struct NextMove
{
int i;
int j;
}NextMove;

void clear();
int knight(int,int);

int checker[row_size+4][col_size+4];
int step=0;
int ans=0;

// Knight's directions in X-axis and Y-axis.
const int horizontal[8]={ 2, 1,-1,-2,-2,-1, 1, 2};
const int vertical[8]={-1,-2,-2,-1, 1, 2, 2, 1};

NextMove next[row_size];

int main()
{
time_t ticks1,ticks2;
int i,j,p,t;
clear();

ticks1 = time(NULL);

for(p=2;p<row_size+2;p++)
for(t=2;t<col_size+2;t++)
{
clear();
if(knight(p,t)!=0)
{
printf("\nAns : %d\tStep : %d\n",++ans,step);
for(i=2;i<row_size+2;i++)
{
for(j=2;j<col_size+2;j++)
printf("%3d",checker[i][j]);
printf("\n");
}
}
}

ticks2 = time(NULL);

printf("\nStart time : %.24s\r\n",ctime(&ticks1));
printf(" End time : %.24s\r\n",ctime(&ticks2));

system("PAUSE");
return 0;
}

// To avoid that the knight goes out of range.
void clear()
{
int i,j;
for(i=0;i<row_size+4;i++)
for(j=0;j<col_size+4;j++)
if(i<2||i>row_size+1||j<2||j>col_size+1)
checker[i][j]=-1;
else
checker[i][j]=0;
step=0;
}

// Find the path.
int knight(int i,int j)
{
int p,t,k,temp,count;
int temp_i,temp_j,min_way,second_way[row_size];

　// Clear the next step stack
for(p=0;p<8;p++)
{
next[p].i=0;
next[p].j=0;
}

checker[i][j]=1;

for(p=1;p<row_size*col_size;p++)
{
// Clear the number of ways of each next step
for(t=0;t<8;t++)
second_way[t]=0;

　　// Reset index "count"
count=0;

　　// Try the eight directions
for(k=0;k<8;k++)
{
temp_i=i+vertical[k];
temp_j=j+horizontal[k];

// If the direction is passable then set up the knight,
　　　// and ways counting++
if(checker[temp_i][temp_j]==0)
{
next[count].i=temp_i;
next[count++].j=temp_j;
}
}

　// After trying the eight directions
　　// If no ways can move
if(count==0)
return 0;
// If just one way can move then thw way is the smallest-step way
else if(count==1)
// Thw direction was pushed in next[0]
min_way=0;
// Otherwise find the smallest ways of the next ways,
　　// if we got the same ways then choose the first one.
else
{
// Find the ways of each next-step way
for(t=0;t<count;t++)
// Try the eight directions like before
for(k=0;k<8;k++)
{
temp_i=next[t].i+vertical[k];
temp_j=next[t].j+horizontal[k];

if(checker[temp_i][temp_j]==0)
second_way[t]++;
}

temp=second_way[0];
min_way=0;

　　　// Search for the smallest ways of each next-step way
for(t=1;t<count;t++)
if(second_way[t]<temp)
{
temp=second_way[t];
min_way=t;
}
}

　　// Find out the smallest ways of the next step
i=next[min_way].i;
j=next[min_way].j;
checker[i][j]=p+1;
}

step=p;
return 1;
}