馬踏棋盤游戲攻略

1、數據結構－－馬踏棋盤問題

採用棧的結構(系統自帶，遞歸就是百)，使用深度優先搜索的方法來處理。度
假設它現在正處在第（x,y）。

Procedure DFS(x,y)
Begin
for (x',y')∈{從(x,y)出發每一個只用走知一步就可以到道達的點} do
if not visited(x,y) then
begin
visited(x,y)<--TRUE
-1
if =1 then print
else DFS(x',y')
Visited(x,y)<--False
+1
end

值得一提的是：馬每走一步，它所在的格子的顏色都專會發生變化，一些棋盤一隻馬屬是可以遍歷的，有的則不能。

2、急求數據結構（C語言版）馬踏棋盤問題解決方案

#include<stdio.h>
#include<conio.h>

#define N 5
void main(){
int x,y;
void horse(int i,int j);
printf("Please input start position:");
scanf("%d%d",&x,&y);
horse(x-1,y-1);
}
void horse(int i,int j){
int a[N][N]={0},start=0,
h[]={1,2,2,1,-1,-2,-2,-1},
v[]={2,1,-1,-2,2,1,-1,-2},
save[N*N]={0},posnum=0,ti,tj,count=0;
int jump(int i,int j,int a[N][N]);
void outplan(int a[N][N]);
a[i][j]=posnum+1;
while(posnum>=0){
ti=i;tj=j;
for(start=save[posnum];start<8;++start){
ti+=h[start];tj+=v[start];
if(jump(ti,tj,a))
break;
ti-=h[start];tj-=v[start];
}
if(start<8){
save[posnum]=start;
a[ti][tj]=++posnum+1;
i=ti;j=tj;save[posnum]=0;
if(posnum==N*N-1){
//outplan(a);
count++;
}
}
else{
a[i][j]=0;
posnum--;
i-=h[save[posnum]];j-=v[save[posnum]];
save[posnum]++;
}
}
printf("%5d",count);
}
int jump(int i,int j,int a[N][N]){
if(i<N&&i>=0&&j<N&&j>=0&&a[i][j]==0)
return 1;
return 0;
}
void outplan(int a[N][N]){
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++)
printf("%3d",a[i][j]);
printf("\n");
}
printf("\n");
getchar();
}

3、求馬踏棋盤C++演算法程序

這個用貪心演算法是最好的。 #include <iostream> using namespace std; #define X 8 #define Y 8 #define N 8 struct child { int x; int y; int wayout;//子節點訪問次數 } node[N]; int chess[X][Y]; int addx[N]={-2,-1,1,2,2,1,-1,-2}; int addy[N]={1,2,2,1,-1,-2,-2,-1}; int way(int x,int y,int m,int n)//計運算元節點出口多少 { int i; int tx; int ty; int count=-1; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]= =0)&&(chess[x][y]==0)&&((tx!=m)||(ty!=n)))//進行子節點出口的判定 { count++; } } return count; } int finalway(int x,int y)//完成最後節點的確定 { chess[x][y]=X*Y-1; int tx; int ty; int i; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]==0)& &((tx!=x)||(ty!=y)))//進行最後節點出口的判定 { chess[tx][ty]=X*Y; return 1; } } return 0; } void sort(child *point) { int i,j; struct child swap; for(i=0;i<N;i++)//採用冒泡排序 { for(j=0;j<N-1;j++) { if(point[j].wayout>point[j+1].wayout) { swap=point[j]; point[j]=point[j+1]; point[j+1]=swap; } } } } int TravelChessBoard(int x,int y,int tag) { int xx=x; int yy=y; int i; if(tag!=X*Y) { for(i=0;i<N;i++) { node[i].x=xx+addx[i]; node[i].y=yy+addy[i]; node[i].wayout=way(node[i].x,node[i].y,xx,yy); } sort(node); for(i=0;(node[i].wayout<0)&&(i<=N);i++);//去掉訪問過的節點和沒有出口的節點 if(i==N) return 0; for(;i<N;i++) { xx=node[i].x; yy=node[i].y; chess[xx][yy]=tag; if(TravelChessBoard(xx,yy,tag+1)==1) return 1; else chess[xx][yy]=0; } } else { if(finalway(xx,yy)) return 1; else { return 0; } } return 0; } int main() { int i,j; for(i=0;i<X;i++) { for(j=0;j<Y;j++) chess[i][j] = 0; } TravelChessBoard(2,0,1); for(i=0;i<X;i++) { for(j=0;j<Y;j++) { cout<<chess[i][j]<<'\t'; } cout<<endl; } return 1; }

4、求馬踏棋盤的源代碼

此程序為百度知道裡面一個兄弟回答過的 十分經典

#include <stdio.h>
main()
{
int a[9][9],object[9][9],step[9][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},
{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};
int i,j,k,x,y,z,m,n,min;
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
a[i][j]=0; /* clear data in array */
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
for(k=1;k<=8;k++)
{
x=i;y=j;
x=x+step[k][1];
y=y+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
a[i][j]++ ; /* initilize array */
} /* start col and row;*/
printf("Please inpute start position x,y\n");
scanf("%d,%d",&m,&n);
for(z=1;z<=64;z++)
{
min =10;
object[m][n]=z;
a[m][n]=0;
for(k=1;k<=8;k++)
{
x=m+step[k][1];
y=n+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
if(a[x][y]!=0)
{
--a[x][y];
if(a[x][y]<min)
{
min=a[x][y];
i=x;
j=y;
}
}
}
m=i;n=j;
}
for(i=1;i<=8;i++)
{
for(j=1;j<=8;j++)
printf("%6d",object[i][j]);
printf("\n");
}
getch();
}

5、回溯演算法馬踏棋盤問題

//我並沒有仔細研究這個演算法，生硬Debug了一下，發現  a = x + Move[i][0];
  b = y + Move[i][1];//這兩行在跳36步以後，導致H[a][b]越界，a和b都有40多。結合你貼的圖第19步（28和8中間）被清零了，這是遞歸沒有正確回溯造成的。
//基本上，全局變數能不用盡量不用，代碼會很混亂，莫明其妙的問題多多。
//改巴改巴之後可以輸出了，頭幾組結果好像還滿正確。總的來說這個演算法效率有點低，我對有生之年能看到全部輸出不抱希望。

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

int Move[8][2] = { 2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1 };
int H[8 + 4][8 + 4] = { 0 };
int cnt;

void Print()
{ 
    int i, j;
    for (i = 2; i < 10; i++) 
    {  
        for (j = 2; j < 10; j++)  
        {   
            printf("%4d", H[i][j]);  
        }  
        printf(" "); 
    } 
    printf(" ");
}

void hourse(int x, int y)
{ 
    int i, j, a, b, aa = x, bb = y;  // aa,bb用於保存最後的位置，回溯的起點
    for (i = 0; i < 8; i++) 
    {  
        a = x + Move[i][0];  
        b = y + Move[i][1];  
        if (H[a][b] == 0)  
        {   
            aa = a; bb = b;   
            H[a][b] = ++cnt;   
            if (cnt == 64)   
            {    
                Print();    
                //exit(0); // 基於這個演算法的效率，為了把有限的生命投入到更有意義的事情，建議啟用這行^^    
                H[a][b] = 0; //回溯    
                cnt--; //回溯    
                return; //回溯   
            }   
            else   
            {    
                hourse(a, b);    
                H[aa][bb] = 0;//回溯    
                cnt--;//回溯  
            }  
        } 
    }
}

int main(void)
{ 
    int i, j; 
    for (i = 0; i < 12; i++) 
    {  
        for (j = 0; j < 12; j++)  
        {   
            if (i <= 1 || j >= 10 || j <= 1 || i >= 10) 
                H[i][j] = -1;  
        } 
    } 
    for (i = 2; i < 10; i++) 
    { 
        for (j = 2; j < 10; j++)  
        {   
            cnt = 0;   
            H[i][j] = ++cnt;   
            hourse(i, j);   
            H[i][j] = 0; // 上一個起點置0，horse()只能回溯到第二步，其實我等了很久，並沒有等到這行運行  
        } 
    } 
    return 0;
}

6、馬踏棋盤的需求分析

將馬隨機放在國際象棋的Board[0～抄7][0～7]的某個方格中，馬按走棋規則進行移動。，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，並按求出的行走路線，將數字1，2，…，64依次填入一個8×8的方陣，輸出zhidao之。

7、演算法馬踏棋盤的問題

雖然我不知道你看的是什麼演算法，但是這問題應該是用的深度優先搜索演算法。在走到死路後就需要回溯，回溯的時候肯定是要進行取消標記的操作的。

8、解釋這段馬踏棋盤 每步注釋

LZ貼出來的代碼已經把關鍵的點交代清楚了啊。額，好吧。再注釋詳細點。
#include<stdio.h>
int HTry1[8]={-2,-1,1,2,2,1,-1,-2,};
int HTry2[8]={1,2,2,1,-1,-2,-2,-1,};
int board[8][8]={{0}}; // 棋盤是 8*8的，初始化成0
int nexti[8],nextj[8],npos,s_row,s_col,step,outwrite=1;

/*（i，j）的馬可以走到的新位置是在棋盤范圍內的（i+HTry1[h]，j+HTry2[h]），其中h=0,1,…7。*/
int newposition(int i,int j,int a[8],int b[8])
{
// newposition的思路還是挺簡單的，馬每走一步的新位置最多隻有8種情況而且是可預知的，
// 將這些位置預先儲存到數組HTry1,HTry2中，兩個數組分別代表橫縱向的偏移格數。
// 實際可走的步數要除掉超出棋盤范圍的和已經走過了不能重復走的。
int flag=0,h,i1,j1; // flag 記錄實際下一步可選數目
for(h=0;h<8;h++)
{
i1=i+HTry1[h]; // (i, j) 加上偏移就是新位置(i1, j1)了
j1=j+HTry2[h];
if(i1>7 || i1<0 || j1>7 || j1<0) //（i1，j1）的位置不超出棋盤范圍
continue;
else if(board[i1][j1]!=0) //新位置的值不為零
continue;
else // OK，是可選的了
{
a[flag]=HTry1[h]; // 記錄下這個備選走法
b[flag]=HTry2[h];
++flag; // 可選數目增1
}
}
return(flag); // 返回可選數目，具體的可選走法內容由參數 a， b帶回。
}

/*函數movenext在有多出口時，選擇適當出口推進一步 */
int movenext(int *i,int *j,int a[],int b[])
{
// movenext是整個演算法中最關鍵的，也是這裡面寫得最晦澀難理解的部分。要在多個可走的位置// 中選擇一個試探，從代碼來看，是採用了貪心策略，即每次都選最好的一步來走。

int temp,flag=8,a1[8],b1[8], // 各個變數的具體看代碼中的夾注
nexti_like[8],nextj_like[8],
s_row_like,s_col_like,h,t;
for(h=0;h<npos;h++) // h用來將npos個可走位置選擇遍歷，逐個對比
{
// 每種h選擇用newposition看下下步有多少種可走選擇，記為temp
temp=newposition(*i+nexti[h],*j+nextj[h],a1,b1);
if(temp<flag) // 如果h選擇的下下步選擇數temp比目前最優情況flag還要少的話
// 這里的if條件有問題，假設剛好第一步是在棋盤中央，則對每個h選擇，temp應該
// 全是8，則if條件對全部的h都不成立，結果會出錯。將flag初始化成9(大於8)以上
// 可解決。
{
// 選h選擇為新的當前最優選擇
s_row_like=*i+nexti[h]; // 記錄h選擇的下一步位置
s_col_like=*j+nextj[h]; // 記錄到(s_row_like,s_col_like)
flag=temp; // 記錄h選擇的下下步可走數，記為flag
for(t=0;t<flag;t++)
{
nexti_like[t]=a1[t]; // 記錄newposition計算出來的
nextj_like[t]=b1[t]; // 下下步走法選擇的具體內容
}
}
}
// 循環結束，最優結論已經得出了，選最優的一步走了
*i=s_row_like; // 將對應的下一步位置作為新的位置記到 (*i, *j)，
*j=s_col_like; // 注意這里i，j是用了指針了的，所以其結果是會傳回去的，
// 要對應著看 main 中調用 movenext 的語句才清楚。
// 至於棋盤上的位置標記要等函數返回後才做。別扭！
for(h=0;h<flag;h++)
{
a[h]=nexti_like[h]; // 對應的下下步選擇現在就是下一步的選擇了
b[h]=nextj_like[h]; // 更新到參數 a, b 中帶回。
// 從這里看，其他未選中的走法被直接棄掉沒有保存，
// 所以也就無法回溯了。
}
return flag; // 返回是新的下一步的可選擇數
}

void main()
{
int i,j;
printf(" 輸入起始位置(row,col):");
scanf("%d,%d",&s_row,&s_col);/*輸入起始位置*/
board[s_row][s_col]=1; // 將起始位置標記為1，即第1步，0則表示對應位置還沒走過
npos=newposition(s_row,s_col,nexti,nextj); // 看下一步有哪幾個位置可走
for(step=2;step<=64;step++) // 如果這個循環完成，說明成功遍歷了棋盤 64 個位置
{
if(npos==0) // 下一步有0個位置可走，失敗了
{
outwrite=0;
break;
}
else if(npos==1) // 下一步只有1個位置可走。走吧，不用多想了。
{
s_row+=nexti[0]; //nexti和nextj記錄了下一步位置的縱橫偏移
s_col+=nextj[0];
board[s_row][s_col]=step; // 對應位置標記上第step步
npos=newposition(s_row,s_col,nexti,nextj); //接著看下下步，循環
}
else
{
// 有多種走法，通過movenext函數來選擇一步，並且看下下步，循環
npos=movenext(&s_row,&s_col,nexti,nextj);
board[s_row][s_col]=step; // 對應位置標記上第step步
}
}
if(outwrite==0) //是循環中途失敗時跳出的嗎？
printf("\n 沒有解決方式\n");
else
{ // 不是循環中途跳出的，說明循環完成了，找到一個成功遍歷的解法了。
printf("\n 解決方式之一 :\n");
// 把整個棋盤列印出來，對應位置的數表示走的步驟。
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
printf("%4d",board[i][j]);
printf("\n");
}
}
}

9、用回溯法求馬踏棋盤問題是不是效率很低

雖然我不知道你看的是什麼演算法，但是這問題應該是用的深度優先搜索演算法。在走到死路後就需要回溯，回溯的時候肯定是要進行取消標記的操作的。
這個用貪心演算法是最好的。 #include <iostream> using namespace std; #define X 8 #define Y 8 #define N 8 struct child { int x; int y; int wayout;//子節點訪問次數 } node[N]; int chess[X][Y]; int addx[N]={-2,-1,1,2,2,1,-1,-2}; int addy[N]={1,2,2,1,-1,-2,-2,-1}; int way(int x,int y,int m,int n)//計運算元節點出口多少 { int i; int tx; int ty; int count=-1; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]= =0)&&(chess[x][y]==0)&&((tx!=m)||(ty!=n)))//進行子節點出口的判定 { count++; } } return count; } int finalway(int x,int y)//完成最後節點的確定 { chess[x][y]=X*Y-1; int tx; int ty; int i; for(i=0;i<N;i++) { tx=x+addx[i]; ty=y+addy[i]; if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]==0)& &((tx!=x)||(ty!=y)))//進行最後節點出口的判定 { chess[tx][ty]=X*Y; return 1; } } return 0; } void sort(child *point) { int i,j; struct child swap; for(i=0;i<N;i++)//採用冒泡排序 { for(j=0;j<N-1;j++) { if(point[j].wayout>point[j+1].wayout) { swap=point[j]; point[j]=point[j+1]; point[j+1]=swap; } } } } int TravelChessBoard(int x,int y,int tag) { int xx=x; int yy=y; int i; if(tag!=X*Y) { for(i=0;i<N;i++) { node[i].x=xx+addx[i]; node[i].y=yy+addy[i]; node[i].wayout=way(node[i].x,node[i].y,xx,yy); } sort(node); for(i=0;(node[i].wayout<0)&&(i<=N);i++);//去掉訪問過的節點和沒有出口的節點 if(i==N) return 0; for(;i<N;i++) { xx=node[i].x; yy=node[i].y; chess[xx][yy]=tag; if(TravelChessBoard(xx,yy,tag+1)==1) return 1; else chess[xx][yy]=0; } } else { if(finalway(xx,yy)) return 1; else { return 0; } } return 0; } int main() { int i,j; for(i=0;i<X;i++) { for(j=0;j<Y;j++) chess[i][j] = 0; } TravelChessBoard(2,0,1); for(i=0;i<X;i++) { for(j=0;j<Y;j++) { cout<<chess[i][j]<<'\t'; } cout<<endl; } return 1; }