/June 8,2018 Author GH /
/該代碼用遞歸實現(xiàn)了馬踏棋盤算法/
/反思雷厂，在實現(xiàn)過程中濫用全局變量導(dǎo)致了許多fatal的錯誤忧勿！/
/此外代碼的算法效率還有待改進——————可以將回退的代碼進行重構(gòu) 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表示已經(jīng)走過;
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是合格方案個數(shù),layer當前所遞歸的層數(shù);
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) //使輸出更加規(guī)整,列之間對齊;
{
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) //核心函數(shù)
{
int inner_counter =0,i; //inner_counter用于判斷該位置是否已經(jīng)無路可走,
int Adds_value = 0,mid_variable =0; //mid_variable用于判斷是否需要回退一層，Adds_value用于計算總和;
layer++; //遞歸層數(shù)
if(move_x<0 || move_x>7 || move_y<0 || move_y>7) //判斷位置是否在棋盤內(nèi)
{
layer--;
return 0;
}
else if(Whether_passing[move_x][move_y]==1) //判斷 是否已經(jīng)走過
{
layer--;
return 0;
}
else
{
Cheese_value[move_x][move_y] = layer; //把當前步驟 賦值給Cheese_value數(shù)組;
Whether_passing[move_x][move_y] = 1; //標記 為已經(jīng)走過
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); //總的種類數(shù)量
printf_cheese(); //偽代碼瓶逃，執(zhí)行操作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厢绝，不然后面程序?qū)⒉粫赝艘粚悠跄磍ayer--;不會執(zhí)行
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;
}
