馬踏棋盤代碼與分析

將馬隨機(jī)放在國際象棋的8×8棋盤Board[0～7][0～7]的某個方格中，馬按走棋規(guī)則進(jìn)行移動。要求每個方格只進(jìn)入一次，走遍棋盤上全部64個方格。求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個8×8的方陣，輸出之。對于這個要求：需要做到，有一個二維數(shù)組（全部置0）來接受這個棋盤，馬走一步，就將此處加一，要進(jìn)行判斷，下一步是否可以走，可以走，進(jìn)棧，不可以走，出棧，判斷時避過這個點，從其他的方向進(jìn)行判斷，將不可以走的路重新置0，這就需要不斷地出棧進(jìn)展判斷；（棧只允許在一段進(jìn)行增加刪除）下面是馬踏棋盤的代碼，及解釋：//定義頭文件和預(yù)定義#include<stdio.h>#defineMAXSIZE100#defineN8//數(shù)據(jù)類型定義intboard[8][8];//定義棋盤intHtry1[8]={1,-1,-2,2,2,1,-1,-2};//存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的增量數(shù)組intHtry2[8]={2,-2,1,1,-1,-2,2,-1};//存儲馬各個出口位置相對當(dāng)前位置列下標(biāo)的增量數(shù)組structStack{//定義棧類型inti;//行坐標(biāo)intj;//列坐標(biāo)intdirector;//存儲方向}stack[MAXSIZE];//定義一個棧數(shù)組inttop=-1;//棧指針//函數(shù)聲明voidInitLocation(intxi,intyi);//馬兒在棋盤上的起始位置坐標(biāo)intTryPath(inti,intj);//馬兒每個方向進(jìn)行嘗試，直到試完整個棋盤voidDisplay();//輸出馬兒行走的路徑//起始坐標(biāo)函數(shù)模塊voidInitLocation(intxi,intyi){intx,y;//定義棋盤的橫縱坐標(biāo)變量 top++;//棧指針指向第一個棧首 stack[top].i=xi;//將起始位置的橫坐標(biāo)進(jìn)棧 stack[top].j=yi;//將起始位置的縱坐標(biāo)進(jìn)棧 stack[top].director=-1;//將起始位置的嘗試方向賦初值 board[xi][yi]=top+1;//標(biāo)記棋盤 x=stack[top].i;//將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo) y=stack[top].j;//將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo) if(TryPath(x,y))//調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回1否則返回0 { Display(); }//輸出馬兒的行走路徑 else printf("無解");}//探尋路徑函數(shù)模塊intTryPath(inti,intj){intfind,director,number,min;//定義幾個臨時變量inti1,j1,h,k,s;//定義幾個臨時變量inta[8],b1[8],b2[8],d[8];//定義幾個臨時數(shù)組while(top>-1)//棧不空時循環(huán){for(h=0;h<8;h++)//用數(shù)組a[8]記錄當(dāng)前位置的下一個位置的可行路徑的條數(shù) { number=0; i=stack[top].i+Htry1[h]; j=stack[top].j+Htry2[h]; b1[h]=i; b2[h]=j;if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置 {for(k=0;k<8;k++) {i1=b1[h]+Htry1[k];j1=b2[h]+Htry2[k];if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)//如果找到下一位置number++;//記錄條數(shù) }a[h]=number;//將條數(shù)存入數(shù)組a[8]中 } }for(h=0;h<8;h++)//根據(jù)可行路徑條數(shù)小到大按下標(biāo)排序放入數(shù)組d[8]中{min=9;for(k=0;k<8;k++)if(min>a[k]) {min=a[k];d[h]=k;//將下標(biāo)存入數(shù)組d[8]中s=k; }a[s]=9;}director=stack[top].director;if(top>=63)//如果走完整個棋盤返回return(1);find=0;//表示沒有找到下一個位置for(h=director+1;h<8;h++)//向八個方向進(jìn)行探尋{i=stack[top].i+Htry1[d[h]];j=stack[top].j+Htry2[d[h]];if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置 {find=1;//表示找到下一個位置break; }}if(find==1)//如果找到下一個位置進(jìn)棧{ stack[top].director=director;//存儲棧結(jié)點的方向 top++;//棧指針前移進(jìn)棧 stack[top].i=i; stack[top].j=j; stack[top].director=-1;//重新初始化下一棧結(jié)點的嘗試方向 board[i][j]=top+1;//標(biāo)記棋盤}else//否則退棧{board[stack[top].i][stack[top].j]=0;//清除棋盤的標(biāo)記top--;//棧指針前移退棧}}return(0);}//輸出路徑函數(shù)模塊voidDisplay(){inti,j;for(i=0;i<N;i++) {for(j=0;j<N;j++)printf("\t%d",board[i][j]);//輸出馬兒在棋盤上走過的路徑printf("\n\n"); }printf("\n");}//主程序模塊voidmain(){inti,j;intx,y;for(i=0;i<N;i++)//初始化棋盤for(j=0;j<N;j++)board[i][j]=0;for(;;){ printf("請輸入馬兒的初始位置(1<=x<=8and1<=y<=8)\n"); printf("Inputx="); scanf("%d",&x);//輸入起始位置的橫坐標(biāo) printf("Inputy="); scanf("%d",&y);//輸入起始位置的縱坐標(biāo) if(x>=1&&x<=8&&y>=1&&y<=8) { break;//若輸入的坐標(biāo)超出所給棋盤的允許范圍則跳出循環(huán) } printf("Yourin