/June 8,2018 Author GH /
/该代码用递归实现了马踏棋盘算法/
/反思，在实现过程中滥用全局变量导致了许多fatal的错误！/
/此外代码的算法效率还有待改进——————可以将回退的代码进行重构 Line62~110/

include <stdio.h>

include <stdlib.h>

int move_x_array[8] = {1,2,2,1,-1,-2,-2,-1}; //x方向移动步骤 (x>0向下，x<0向上)
int move_y_array[8] = {2,1,-1,-2,-2,-1,1,2}; //y方向的移动步骤(y>0向右, y<0向左)
int L,C;
int Whether_passing[8][8] = {{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}}; //标志位，0表示没有走过，1表示已经走过;

int Cheese_value[8][8] = {{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}}; //记录每一个位置是在 "第几部" 走过的;
int key; //Find_next()的返回值
int Kind = 0,layer = 0; //Kind是合格方案个数,layer当前所递归的层数;
void printf_cheese(void) //目的是判断是否棋盘上所有位置都被走过，如果没有则跳过，否则将当前情况打印出来
{
int line,column;
for(line=0;line<8;line++)
{
for(column=0;column<8;column++)
{
if(Cheese_value[line][column]<10) //使输出更加规整,列之间对齐;
{
printf("%d ",Cheese_value[line][column]);
}
else
{
printf("%d ",Cheese_value[line][column]);
}
}
printf("\n\n");
}
//printf("%d",move_y_array[4]);
}
int Find_next(int move_x,int move_y) //核心函数
{
int inner_counter =0,i; //inner_counter用于判断该位置是否已经无路可走,
int Adds_value = 0,mid_variable =0; //mid_variable用于判断是否需要回退一层，Adds_value用于计算总和;
layer++; //递归层数
if(move_x<0 || move_x>7 || move_y<0 || move_y>7) //判断位置是否在棋盘内
{
layer--;
return 0;
}
else if(Whether_passing[move_x][move_y]==1) //判断 是否已经走过
{
layer--;
return 0;
}
else
{
Cheese_value[move_x][move_y] = layer; //把当前步骤 赋值给Cheese_value数组;
Whether_passing[move_x][move_y] = 1; //标记 为已经走过
for(i=0;i<8;i++)
{
key = Find_next(move_x+move_x_array[i],move_y+move_y_array[i]);
if(key == 0)
{
inner_counter++;
}
} //递归
for(L=0;L<8;L++)
{
for(C=0;C<8;C++)
{
Adds_value += Cheese_value[L][C];
}
} //获取当前所有位置的值的总和;
if(inner_counter == 8) //回退一层
{
layer--;
}
if(inner_counter == 8 && Adds_value==2080 )// && && Adds_value < 2080
{
//inner_counter = 0;
Kind++;
printf("Kind=%d ###layer=%d ###Add_value= %d\n",Kind,layer+1,Adds_value); //总的种类数量
printf_cheese(); //伪代码，执行操作operator ,目的是判断是否棋盘上所有位置都被走过，如果没有则跳过，否则将当前情况打印出来
printf("\n");
}
if(inner_counter == 8 && layer==0)
{
printf("Game over;");
exit(0);
}
mid_variable = inner_counter; //因为inner_counter不得不清零所已用mid_variable来存储它的值;
inner_counter = 0;
Cheese_value[move_x][move_y] = 0; //步骤清零
Whether_passing[move_x][move_y]=0; //标志位清零
if(mid_variable == 8){ //如果无路可走必须要返回0，不然后面程序将不会回退一层，即layer--;不会执行
mid_variable = 0;
return 0;
}
else
return 1;
}
}
int main()
{
int start_x = 7,start_y = 0; //起始位置
Find_next(start_x,start_y);
return 0;
}