當前位置:首頁 » 編程語言 » C語言馬踏棋盤

C語言馬踏棋盤

發布時間: 2022-05-15 02:03:56

1. 求數據結構課程設計 馬踏棋盤 c語言

沒看見你說的是非遞歸的。

其實我也不懂,碰巧知道答案,在51CTO上下的。 不能插圖。
9.3 馬踏棋盤(1)
【題目要求】
國際象棋的棋盤為8*8的方格棋盤。現將"馬"放在任意指定的方格中,按照"馬"走棋的規則將"馬"進行移動。要求每個方格只能進入一次,最終使得"馬"走遍棋盤的64個方格。編寫一個C程序,實現馬踏棋盤操作,要求用1~64這64個數字標注馬移動的路徑,也就是按照求出的行走路線,將數字1,2,……64依次填入棋盤的方格中,並輸出。
國際象棋中,"馬"的移動規則如圖9-4所示。

圖9-4 "馬"的移動規則
如圖9-4所示,圖中實心的圓圈代表"馬"的位置,它下一步可移動到圖中空心圓圈標注的8個位置上,該規則叫做"馬走日"。但是如果"馬"位於棋盤的邊界附近,它下一步可移動到的位置就不一定有8個了,因為要保證"馬"每一步都走在棋盤中。
【題目分析】
馬踏棋盤的問題其實就是要將1,2,…,64填入到一個8*8的矩陣中,要求相鄰的兩個數按照"馬"的移動規則放置在矩陣中。例如數字a放置在矩陣的(i,j)位置上,數字a+1隻能放置在矩陣的(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1)之中的一個位置上。將矩陣填滿並輸出。這樣在矩陣中從1,2…遍歷到64,就得到了馬踏棋盤的行走路線。因此本題的最終目的是輸出一個8*8的矩陣,在該矩陣中填有1,2…64這64個數字,相鄰數字之間遵照"馬走日"的規則。
解決馬踏棋盤問題的一種比較容易理解的方法是應用遞歸的深度優先搜索的思想。因為"馬"每走一步都是盲目的,它並不能判斷當前的走步一定正確,而只能保證當前這步是可走的。"馬"走的每一步棋都是從它當前位置出發,向下一步的8個位置中的1個行走(在它下一步有8個位置可走的情況下)。因此"馬"當前所走的路徑並不一定正確,因為它可能還有剩下的可選路徑沒有嘗試,如圖9-5所示。

圖9-5 "馬"的可選路徑
如圖9-5所示,假設最開始"馬"位於棋盤的(0,0)的位置,接下來"馬"有兩處位置可走,即(1,2)和(2,1)。這時"馬"是無法確定走2的位置最終是正確的,還是走3的位置最終是正確的。因此"馬"只能任意先從一個路徑走下去(例如從2的位置)。如果這條路是正確的,那當然是幸運的,如果不正確,則"馬"要退回到第一步,繼續從3的位置走下去。以後"馬"走的每一步行走都遵循這個規則。這個過程就是一種深度搜索的過程,同時也是一種具有重復性操作的遞歸過程。可以用一棵"探索樹"來描述該深度優先搜索過程,如圖9-6所示。

圖9-6 深度優先搜索過程
"馬"的行走過程實際上就是一個深度探索的過程。如圖9-6所示,"探索樹"的根結點為"馬"在棋盤中的初始位置(這里用4*4的棋盤示意)。接下來"馬"有兩種行走方式,於是根結點派生出兩個分支。而再往下一步行走,根結點的兩個孩子又能夠分別派生出其他不同的"行走路線"分支,如此派生下去,就得到了"馬"的所有可能的走步狀態。可以想見,該探索樹的葉子結點只可能有兩種狀態:一是該結點不能再派生出其他的"走步"分支了,也就是"馬"走不通了;二是棋盤中的每個方格都被走到,即"馬"踏遍棋盤。於是從該探索樹的根結點到第二種情況的葉結點構成的路徑就是馬踏棋盤的行走過程。
如何才能通過搜索這棵探索樹找到這條馬踏棋盤的行走路徑呢?可以採用深度優先搜索的方法以先序的方式訪問樹中的各個結點,直到訪問到葉結點。如果葉結點是第二種情況的葉結點,則搜索過程可以結束,因為找到了馬踏棋盤的行走路徑;如果葉結點為第一種情況的葉結點,即走不通了,則需要返回到上一層的結點,順著該結點的下一條分支繼續進行深度優先搜索下去。
因此在設計"馬踏棋盤"的演算法時可以借鑒前面講過的圖的深度優先遍歷演算法和二叉樹的先序遍歷演算法。但是在這里並不需要真正地構建這樣一棵探索樹,我們只需要借用探索樹的思想。在實際的操作過程中,所謂的探索樹實際就是深度優先搜索的探索路徑,每個結點實際就是當前的棋盤狀態,而所謂的葉結點要麼就是在當前棋盤狀態下,"馬"無法再進行下一步行走;要麼就是馬踏棋盤成功。該演算法描述可如下:
int TravelChess Board (int x,int y,int tag)
{
chess[x][y] = tag;
if(tag == 64) { return 1;}
找到"馬"的下一個行走坐標(x1,y1),如果找到返回flag=1,否則返回flag=0;
while(flag ){
if(TravelChessBoard (x1,y1,tag+1))return 1; /*遞歸調用TravelChess , 從x1,y1向下搜索;如果從 x1,y1往下馬踏棋盤成功,返回1*/
else
繼續找到"馬"的下一個行走坐標(x1,y1),如果找到返回flag=1,否則返回flag=0;
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
9.3 馬踏棋盤(2)
http://book.51cto.com 2010-03-17 08:57 楊峰 清華大學出版社 我要評論(0)
摘要:《妙趣橫生的演算法(C語言實現)》第9章綜合題,,本章將列舉一些經典的綜合題編程實例。這些題目生動有趣,同時具有一定的難度,因此作者盡量做到講解深入淺出,把問題講透徹,講清楚。同時希望讀者能從中得到啟發,啟迪思維,提高自身的編程水平。本節為大家介紹馬踏棋盤。
標簽:妙趣橫生 C語言實現 妙趣橫生的演算法(C語言實現)

Oracle幫您准確洞察各個物流環節
9.3 馬踏棋盤(2)
該演算法中通過函數TravelChess()遞歸地搜索"馬"的每一種走法。其中參數x,y指定 "馬" 當前走到棋盤中的位置,tag是標記變數,每走一個棋盤方格,tag自動增1,它標識著馬踏棋盤的行走路線。
演算法首先將當前"馬"處在棋盤中的位置上添加標記tag,然後判斷tag是否等於64,如果等於64,說明這是馬踏棋盤的最後一步,因此搜索成功,程序應當結束,返回1。否則,找到"馬"下一步可以走到的位置(x1,y1),如果找到這個位置坐標,flag置1,否則flag置0。
下面在flag為1的條件下(即找到x1,y1),遞歸地調用函數TravelChess()。也就是從x1,y1指定的棋盤中的位置繼續向下深度搜索。如果從x1,y1向下搜索成功,即程序一直執行下去,直到tag等於64返回1,那就說明"馬"已經踏遍棋盤(馬踏棋盤的過程是:先走到棋盤的(x,y)位置,再從(x1,y1)向下深度搜索,走遍全棋盤),於是搜索結束,返回1;否則繼續找到"馬"的下一個可以行走的坐標(x1,y1),如果找到這個位置坐標,flag置1,並從(x1,y1)向下重復上述的遞歸搜索,否則flag置0,本次遞歸結束。
如果找遍當前位置(x,y)的下一個坐標(x1,y1)(一般情況是8種),但是從(x1,y1)向下繼續深度優先搜索都不能成功地"馬踏棋盤"(此時flag等於0),則表明當前所處的狀態並不處於馬踏棋盤的"行走路徑"上,也就是說"馬"本不應該走到(x,y)的位置上,因此將chess[x][y]置0,表明棋盤中該位置未被走過(擦掉足跡),同時返回0,程序退到上一層的探索狀態。
這里應當知道,所謂當前位置(x,y)的下一個坐標(x1,y1)是指"馬"下一步可以走到的地方,用坐標(x1,y1)返回。在探索樹中它處在(x,y)所在的結點的子結點中,如圖9-7所示。

圖9-7 (x,y)的下一個坐標(x1,y1)
當前位置(x,y)的下一個坐標(x1,y1)的可選個數由當前棋盤的局面決定。一般情況下是有8種可走的位置(如圖9-7所示),但是如果"馬"位於棋盤的邊緣(如圖9-7所示的探索樹的根結點)或者8個可選位置中有的已被"馬"前面的足跡所佔據,在這兩種情況下(x1,y1)的可選個數就不是8個了。
上述搜索演算法相當於先序遍歷探索樹,只不過它不一定是將探索樹完整地遍歷,而是當tag等於64時,也就是棋盤被全部"踏遍"時就停止繼續搜索了。
下面給出完整的程序清單供讀者參考。
程序清單9-3
/*--------------------------------- 9-3.c --------------------------*/
#include "stdio.h"
#define X 8
#define Y 8
int chess[X][Y];

int nextxy(int *x,int *y,int count) /*找到基於x、y位置的下一個可走的位置*/
{
switch(count)
{
case 0: if(*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0) {*x =*x+2;*y = *y-1;return 1; } break;
case 1: if(*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0) {*x = *x+2; *y = *y+1 ;
return 1;}break;
case 2: if(*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0) {*x = *x+1; *y = *y-2; return 1;} break;
case 3: if(*x+1<=X-1 && *y+2<=Y-1 &&chess[*x+1][*y+2]==0) {*x = *x+1; *y = *y+2;
return 1;}break;
case 4: if(*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0) {*x = *x-2; *y = *y-1; return 1;} break;
case 5: if(*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0){*x = *x-2; *y = *y+1; return 1;} break;
case 6:if(*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0) {*x = *x-1; *y = *y-2;return 1;}break;
case 7: if(*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0) {*x = *x-1; *y = *y+2;
return 1;}break;
default: break ;
}
return 0;
}

int TravelChessBoard(int x,int y,int tag) /*深度優先搜索地"馬踏棋盤"*/
{
int xx1 = x, yy1 = y, flag = 0,a,b ,count = 0 ;
chess[x][y] = tag;
if(tag == X*Y) { return 1;}
flag = nextxy(&x1,&y1,count);
while(flag == 0 && count <7){
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
while(flag ){
if(TravelChessBoard(x1,y1,tag+1))return 1;
xx1 = x;yy1 = y;
countcount = count +1;
flag = nextxy(&x1,&y1,count); /*尋找下一個(x,y)*/
while(flag == 0 && count <7){ /*循環地尋找下一個(x,y)*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
main()
{
int i,j;
for(i=0;i<X;i++)
for(j=0;j<Y;j++)
chess[i][j] = 0;
if(TravelChessBoard(2,0,1)) {
for(i=0;i<X;i++) {
for(j=0;j<Y;j++)
printf("%d ",chess[i][j]);
printf("\n");
}
printf("The horse has travelled the chess borad\n");
}
else
printf("The horse cannot travel the chess board\n");
getche();
}
9.3 馬踏棋盤(3)
http://book.51cto.com 2010-03-17 08:57 楊峰 清華大學出版社 我要評論(0)
摘要:《妙趣橫生的演算法(C語言實現)》第9章綜合題,,本章將列舉一些經典的綜合題編程實例。這些題目生動有趣,同時具有一定的難度,因此作者盡量做到講解深入淺出,把問題講透徹,講清楚。同時希望讀者能從中得到啟發,啟迪思維,提高自身的編程水平。本節為大家介紹int nextxy(int *x,int *y,int count)。
標簽:妙趣橫生 C語言實現 妙趣橫生的演算法(C語言實現)

Oracle幫您准確洞察各個物流環節
9.3 馬踏棋盤(3)
【程序說明】
本程序中應用二維數組chess[8][8]作為8*8的棋盤,"馬"每走到棋盤的(i,j)處,就將當前的步數tag賦值給chess[i][j]。為了方便起見,將數組chess設置為外部變數。另外定義字元常量X,Y,它規定棋盤的大小。本程序清單中將X和Y都設置為8。
函數TravelChessBoard()是上述馬踏棋盤演算法的具體實現。本程序中初始的(x,y)位置為(2,0),說明"馬"從chess[8][8]的chess[2][0]位置開始進行"馬踏棋盤"的。在函數TravelChessBoard()中要調用函數nextxy()。
int nextxy(int *x,int *y,int count)
函數nextxy()包含3個參數:x和y為傳遞下來的"馬"當前踏到棋盤上的位置,它是指針變數。變數count的作用是標記調用nextxy()過程的次數,根據count值的不同,返回基於(x,y)的下一個不同的坐標,以此來避免返回同一個坐標,真正實現尋找"針對當前位置(x,y)的下一個位置"的目的。函數nextxy()的作用是找到"馬"當前的位置(x,y)的下一個可以行走的位置,並通過指針修改x、y的內容,將下一個位置坐標用變數x、y返回。
"尋找(x,y)的下一個位置坐標"的操作通過代碼:
xx1 = x; yy1 = y; /*將坐標(x1,y1)初始化為當前訪問的坐標 (x,y),因為(x,y)不能被改動*/
flag = nextxy(&x1,&y1,count); /*尋找(x,y)下一個位置坐標(x1,y1)*/
while(flag == 0 && count <7){ /*循環地尋找(x,y)的下一個坐標*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
實現。程序最開始將(x1,y1)初始化為當前坐標(x,y),因為"馬"的當前位置坐標(x,y)不能被輕易改動。然後將&x1、&y1作為函數nextxy的參數傳遞,並通過參數&x1和&y1返回當前坐標(x,y)的第count個下一個坐標(x1,y1)。只有當flag為1時,才表明找到了下一個坐標,於是循環可以停止。但是如果count的值超過了7,則說明無法找到(x,y)的下一個坐標,也就說明棋走不通了。所謂當前位置(x,y)的"下一個位置",如圖9-8所示。

(點擊查看大圖)圖9-8 (x,y)的"下一個位置"示意
圖中實心的圓圈的坐標為(x,y),它周圍的8個空心的圓圈1~8,為當前坐標(x,y)的可選的"下一個"坐標(x1,y1)。每次調用nextxy()都可能得到這8個坐標其中的一個,當參數count為i時,返回圓圈i所處的坐標。這樣就保證了不返回同一個坐標。
如果像本程序這樣將字元常量X和Y都設置為8,那麼程序就執行8*8的馬踏棋盤。但是這樣一來會非常費時,實踐證明應用本程序運算出8*8的馬踏棋盤的結果要花幾分鍾的時間。因此讀者在調試程序時可以通過設置X和Y的值減小棋盤的規格,從而更快地得到結果。
本程序的運行結果如圖9-9所示。

(點擊查看大圖)圖9-9 程序9-3的運行結果

2. 馬踏棋盤程序解釋

實現馬走完8×8棋盤的路線;
分步解析:
(1)
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}};設定馬可走的八個方向,第二維第一個是序號(沒什麼用),後兩個分別得X坐標,Y坐標增量;
(2)
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 */
}
初始化整個棋盤,a[i][j]表示馬在(i,j)上可走的方向個數;例如a[1][1]=2,說明馬如果在(1,1)只能走(2,3)和(3,2);這步為後面做鋪墊;
(3)
for(z=1;z<=64;z++)
//標記棋盤的64個可達點,起點為1號,終點為64號,object[m][n]=z;

a[m][n]=0;//每走過一個點,就置該點為0,表示不能再走,(if(a[x][y]!=0) );
能走的話(a[i][j])!=0)就選一個小於min的點if(a[x][y]<min) 作為下一步棋; 之所以要選一個a[i][j]最小的點牽扯到一些演算法,只有這樣才能保證走遍所有點並且不重復。
最後列印,不用說了吧。
大概我想說的就這些。

3. 程序設計,馬踏棋盤,求指教

#include<stdio.h>
#define MAXSIZE 100
#define N 8
int board[8][8]; //定義棋盤
int Htry1[8]={1,-1,-2,2,2,1,-1,-2};
/*存儲馬各個出口位置相對當前位置行下標的增量數組*/
int Htry2[8]={2,-2,1,1,-1,-2,2,-1};
/*存儲馬各個出口位置相對當前位置列下標的增量數組*/
struct Stack{ //定義棧類型
int i; //行坐標
int j; //列坐標

}stack[MAXSIZE]; //定義一個棧數組
int top=0; //棧指針

void InitLocation(int xi,int yi); //馬兒在棋盤上的起始位置坐標
int TryPath(int i,int j); //馬兒每個方向進行嘗試,直到試完整個棋盤
void Display(); //輸出馬兒行走的路徑

void InitLocation(int xi,int yi)
{
int x,y; //定義棋盤的橫縱坐標變數
stack[top].i=xi; //將起始位置的橫坐標進棧
stack[top].j=yi; //將起始位置的縱坐標進棧

board[xi][yi]=top+1; //標記棋盤
x=stack[top].i; //將起始位置的橫坐標賦給棋盤的橫坐標
y=stack[top].j; //將起始位置的縱坐標賦給棋盤的縱坐標
if(TryPath(x,y)) //調用馬兒探尋函數,如果馬兒探尋整個棋盤返回1否則返回0
Display(); //輸出馬兒的行走路徑

}

int TryPath(int i,int j)
{
int find,number,min; //定義幾個臨時變數
int i1,j1,h,k,s; //定義幾個臨時變數
int a[8],b1[8],b2[8],d[8]; //定義幾個臨時數組
while(top>-1) //棧不空時循環
{
for(h=0;h<8;h++) //用數組a[8]記錄當前位置的下一個位置的可行路徑的條數
{
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++; //記錄條數
}
a[h]=number; //將條數存入數組a[8]中
}
}
for(h=0;h<8;h++) //根據可行路徑條數小到大按下表排序放入數組d[8]中
{
min=9;
for(k=0;k<8;k++)
if(min>a[k])
{
min=a[k];
d[h]=k; //將下表存入數組d[8]中
s=k;
}
a[s]=9;
}

if(top>=63) //如果走完整個棋盤返回1
return (1);
find=0; //表示沒有找到下一個位置
for(h=0;h<8;h++) //向八個方向進行探尋
{
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) //如果找到下一個位置進棧
{

top++; //棧指針前移進棧
stack[top].i=i;
stack[top].j=j;

board[i][j]=top+1; //標記棋盤
}
else //否則退棧
{
board[stack[top].i][stack[top].j]=0; //清除棋盤的標記
top--; //棧指針前移退棧
}
}
return (0);
}

void Display()
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("\t%d ",board[i][j]); //輸出馬兒在棋盤上走過的路徑
printf("\n\n");
}
printf("\n");
}

void main()
{
int i,j;
int x,y;
for(i=0;i<N;i++) //初始化棋盤
for(j=0;j<N;j++)
board[i][j]=0;
for(;;)
{
printf("Please input importpoint(1<=x<=8 and 1<=y<=8)\n");
printf("Input x = ");
scanf("%d",&x); //輸入起始位置的橫坐標
printf("Input y = ");
scanf("%d",&y); //輸入起始位置的縱坐標
if(x>=1&&x<=8&&y>=1&&y<=8)break;
printf("Your input is worng!!!\n");
}
printf("begin with %d board:\n\n", 8*(x-1)+y);
InitLocation(x-1,y-1); //調用起始坐標函數
}

4. 幫幫忙編程:馬踏棋盤(用數據結構(C語言版))

#include <stdio.h>

int f[11][11] ;
int adjm[121][121];
long fgf;
void creatadjm(void);
void e(int,int,int,int);
void travel(int,int);

int n,m;

int main()
{
int i,j,k,l;
printf("Input n:");scanf("%d",&n);
m=n*n;
creatadjm();
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
printf("\n");
}
getchar();
printf("Input i,j:");
scanf("%d %d",&i,&j);
l=(i-1)*n+j;
while ((i>0)||(j>0))
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=0;
k=0;

travel(l,k);
printf("%d\n",fgf);fgf=0;

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) printf("%4d",f[i][j]);
printf("\n");
}
getchar();
printf("Input i,j:");scanf("%d %d",&i,&j);
l=(i-1)*n+j;
}
return 0;
}

void creatadjm()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
adjm[i][j]=0;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]==0)
{
f[i][j]=1;
if((i+2<=n)&&(j+1<=n)) e(i,j,i+2,j+1);
if((i+2<=n)&&(j-1>=1)) e(i,j,i+2,j-1);
if((i-2>=1)&&(j+1<=n)) e(i,j,i-2,j+1);
if((i-2>=1)&&(j-1>=1)) e(i,j,i-2,j-1);
if((j+2<=n)&&(i+1<=n)) e(i,j,i+1,j+2);
if((j+2<=n)&&(i-1>=1)) e(i,j,i-1,j+2);
if((j-2>=1)&&(i+1<=n)) e(i,j,i+1,j-2);
if((j-2>=1)&&(i-1>=1)) e(i,j,i-1,j-2);
}
return;
}

void travel(int p,int r)
{
int i,j,q;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]>r) f[i][j]=0;
r=r+1;
i=((p-1)/n)+1;
j=((p-1)%n)+1;

f[i][j]=r;

fgf++;
//if(r==25)printf("%d\n",p);
/*
printf("i=%d,j=%d,r=%d\n",i,j,r); getchar();
*/

for(q=1;q<=m;q++)
{
i=((q-1)/n)+1;
j=((q-1)%n)+1;
if((adjm[p][q]==1)&&(f[i][j]==0)) travel(q,r);
}
return;
}

void e(int i1,int j1,int i2,int j2)
{
adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
return;
}

5. 數據結構課程設計 用棧完成馬踏棋盤的C語言的代碼,急!急!

#include<string.h> #include<ctype.h> #include<stdio.h> #include<math.h> #include<process.h> #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int status; /* pointtype */ typedef struct PT{ int r; int c; }PTT,*LPT; /* stacktype */ typedef struct ST{ int step; int reach[8]; struct PT seat; }ST; struct SD{ ST *base; ST *top; int size; }SD; /* QUEUE */ typedef struct QT{ int r,c,n; }QT; typedef struct QN{ QT data; struct QN *next; }QN,*QNPtr; struct QD{ QNPtr front; QNPtr rear; }QD;

6. 急求數據結構(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();
}

7. 能給我一個馬踏棋盤的c語言程序嗎,要能運行的。

#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define M 8//宏定義棋盤大小#define SIZE 100int board[M][M];typedef struct direct { int r,c,pathnum ;}dir ;typedef struct nodetype { int r,c,pathnum ; //在棋盤中的位置坐標r,c及結點可走方向數目 pathnum struct nodetype*next,*prior ;}node ;//用來計算當前位置可走的方向數目int pathnum(int row,int cn){ int a,b,count=0 ; a=row ; b=cn ; //當前位置可選方向可以走通,則數目加一 if(a-2>=0&&b-1>=0&&board[a-2][b-1]==0)count++; if(a-2>=0&&b+1<M&&board[a-2][b+1]==0)count++; if(a+2<M&&b-1>=0&&board[a+2][b-1]==0)count++; if(a+2<M&&b+1<M&&board[a+2][b+1]==0)count++; if(a-1>=0&&b+2<M&&board[a-1][b+2]==0)count++; if(a-1>=0&&b-2>=0&&board[a-1][b-2]==0)count++; if(a+1<M&&b+2<M&&board[a+1][b+2]==0)count++; if(a+1<M&&b-2>=0&&board[a+1][b-2]==0)count++; return count ;}//尋找路徑函數void findway(int m,int n){ dir f[8],path ; int i,j,k, stepnum ; stepnum=1 ; i=m ; j=n ; while(stepnum<M*M&&i<M&&j<M&&i>=0&&j>=0) { board[i][j]=stepnum ;printf("%d,%d,%d ",i,j,board[i][j]); //用來標志可走方向數的最小值 path.pathnum=8 ; //對方向數組賦初值 for(k=0;k<8;k++) { f[k].r=-1 ; f[k].c=-1 ; } //如果第一個方向可走,則將坐標及可選方向數賦給f[0],以下同理 if(i-2>=0&&j-1>=0) { f[0].r=i-2 ; f[0].c=j-1 ; f[0].pathnum=pathnum(f[0].r,f[0].c); } if(i-2>=0&&j+1<M) { f[1].r=i-2 ; f[1].c=j+1 ; f[1].pathnum=pathnum(f[1].r,f[1].c); } if(i+2<M&&j-1>=0) { f[2].r=i+2 ; f[2].c=j-1 ; f[2].pathnum=pathnum(f[2].r,f[2].c); } if(i+2<M&&j+1<M) { f[3].r=i+2 ; f[3].c=j+1 ; f[3].pathnum=pathnum(f[3].r,f[3].c); } if(i-1>=0&&j+2<M) { f[4].r=i-1 ; f[4].c=j+2 ; f[4].pathnum=pathnum(f[4].r,f[4].c); } if(i-1>=0&&j-2>=0) { f[5].r=i-1 ; f[5].c=j-2 ; f[5].pathnum=pathnum(f[5].r,f[5].c); } if(i+1<M&&j-2>=0) { f[6].r=i+1 ; f[6].c=j-2 ; f[6].pathnum=pathnum(f[6].r,f[6].c); } if(i+1<M&&j+2<M) { f[7].r=i+1 ; f[7].c=j+2 ; f[7].pathnum=pathnum(f[7].r,f[7].c); } //尋找當前位置的八個方向中的可走方向數最少的方向作為新的方向 for(k=0;k<8;k++) if(f[k].r>=0&&f[k].c>=0&&f[k].pathnum<=path.pathnum&&board[f[k].r][f[k].c]==0&&f[k].pathnum>0) { path.pathnum=f[k].pathnum; path.r=f[k].r ; path.c=f[k].c ; } i=path.r ; j=path.c ; stepnum++; } board[i][j]=M*M-1 ; if(i-2>=0&&j-1>=0&&board[i-2][j-1]==0) { i=i-2 ; j=j-1 ; } else if(i-2>=0&&j+1<M&&board[i-2][j+1]==0) { i=i-2 ; j=j+1 ; } else if(i-1>=0&&j+2<M&&board[i-1][j+2]==0) { i=i-1 ; j=j+2 ; } else if(i+1<M&&j+2<M&&board[i+1][j+2]==0) { i=i+1 ; j=j+2 ; } else if(j+2<M&&i+1<=M&&board[i+2][j+1]==0) { i=i+2 ; j=j+1 ; } else if(i+2<M&&j-1>=0&&board[i+2][j-1]==0) { i=i+2 ; j=j-1 ; } else if(i+1<M&&j-2>=0&&board[i+1][j-2]==0) { i=i+1 ; j=j-2 ; } else if(i-1>=0&&j-2>=0&&board[i-1][j-2]==0) { i=i-1 ; j=j-2 ; } board[i][j]=M*M ;printf("%d,%d,%d",i,j,board[i][j]);}
void main(){ int r,c,i,j ; printf("請輸入馬在棋盤上的首位置\n"); scanf("%d,%d",&r,&c); findway(r,c); printf("\n"); //輸出棋盤上的路徑 for(i=0;i<M;i++) { for(j=0;j<M;j++) printf("%3d",board[i][j]); printf("\n"); }}

8. 馬踏棋盤的演算法

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

9. 數據結構中馬踏棋盤問題,求c程序

1。建立無向圖,應該是棋盤格數的方陣,比如64×64(國際象棋)或者90×90,初始化為全零.根據馬的走法,對可以直達的兩格建立一條邊,就是對應位置為1。
2。然後指定一個出發點(當然也可以是從所有點出發一一去試),沿著這些邊到達下一格,並記錄已達到的格中。
3.如果不重復完成,則成功。如果無法繼續走到未到達的格,只能到已到達的格子,則失敗。
4.這個走棋的過程需要一種策略來遍歷各種情況。比如我們可以規定如果有最多八種可能,則馬先測試走那種,這個編寫成遞歸就非常方便。

10. 馬踏棋盤的核心代碼(c語言)

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -2
#define OK 1
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
int Board[8][8]={0};
int HTry1[8]={2,-1,1,-2,2,1,-1,-2};
int HTry2[8]={1,2,2,1,-1,-2,-2,-1};
typedef struct{
int i;
int j;
}PosType;
typedef struct{
int ord;
PosType seat;
int di;
}SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack *s1){
(*s1).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*s1).base) exit(OVERFLOW);
(*s1).top=(*s1).base;
(*s1).stacksize=STACK_INIT_SIZE;
return(OK);
}
SElemType Pop(SqStack *s,SElemType e){
e=*--(*s).top;
return e;
}
int Push(SqStack *s1,SElemType e){
if((*s1).top-(*s1).base>=(*s1).stacksize){
(*s1).base=(SElemType *)realloc((*s1).base,
((*s1).stacksize+STACKINCREMENT)*sizeof
(SElemType));
if(!(*s1).base) exit(OVERFLOW);
(*s1).top=(*s1).base+(*s1).stacksize;
(*s1).stacksize+=STACKINCREMENT;
}
*(*s1).top++=e;
return OK;
}
int StackEmpty(SqStack *s){
if((*s).base==(*s).top)
return(1);
else
return(0);
}
int curstep=0;
int Pass(PosType s){
if((Board[s.i][s.j]==0)&&(s.i<=7)&&(s.i>=0)&&(s.j<=7)&&(s.j>=0))
return(1);
else
return(0);
}
PosType NextPos(PosType s,int i){
s.i=s.i+HTry1[i-1];
s.j=s.j+HTry2[i-1];
return(s);
}
void horsesteps(int Board[8][8],PosType start){
int k,j;
SqStack S;
SElemType e;
PosType curpos=start;
InitStack(&S);
do{
if(Pass(curpos)){
curstep++;
Board[curpos.i][curpos.j]=curstep;
e.seat=curpos;
e.ord=curstep;
e.di=1;
Push(&S,e);
if(curstep==64)
break;
else
curpos=NextPos(curpos,1);
}//if
else{
if(!StackEmpty(&S)){
Pop(&S,e);
if(e.di==8) Board[e.seat.i][e.seat.j]=0;
while(e.di==8&&!StackEmpty(&S)){
e=Pop(&S,e);
if(e.di==8) Board[e.seat.i][e.seat.j]=0;
curstep=e.ord;
}//while
if(e.di<8){
e.di++;
Push(&S,e);
curpos=NextPos(e.seat,e.di);
}//if
}//if
}//else
}while(!StackEmpty(&S));
if(StackEmpty(&S)){
printf(馬兒從這個初始位置不能踏遍棋盤 );
printf(請按任意鍵推出本程序 );
getchar();
exit(OVERFLOW);
}
for(j=0;j<8;j++){
printf( );
for(k=0;k<8;k++)
printf(%3d,Board[j][k]);
}// for
}//函數結束
void main(){
int k,j;
PosType t;
char a,b;
printf(請輸入馬兒的初始位置 );
fflush(stdin);
scanf(%c%d,%d%c,&a,&k,&j,&b);
t.i=k;
t.j=j;
printf(馬兒走的路線為 );
horsesteps(Board,t);
}
小弟只能寫出自己的回溯法的演算法,效率很低,有時要21分鍾出結果 ,但思路是對的。
【原創】我給出我寫的試探法代碼
#include <iostream>
using namespace std;
typedef struct _point
{
int x;
int y;
}point;
class Horse
{
public:
Horse(int n);
~Horse();
void MoveNext(int hang,int lie);
void Print();
public:
int shu;
int qipan[20+1][20+1];
point pt[400+1];
int ci;
};
Horse::Horse(int n)
{
ci=0;
shu=n;
for(int i=1;i<=shu;i++)
for(int j=1;j<=shu;j++)
qipan[i][j]=0;
}
Horse::~Horse()
{
}
void Horse::Print()
{
if(pt[0].x==shu*shu)
{
ci++;
cout<<ci<< Yes!<<endl;
for(int i=1;i<=shu;i++)
for(int j=1;j<=shu;j++)
{
cout<<qipan[i][j]<<' ';
if(j==shu)
cout<<endl;
}
}
}
void Horse::MoveNext(int hang,int lie)
{
if(hang==1&&lie==1&&qipan[hang][lie]==0)
{
pt[0].x=1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
}
if(hang-1>0&&lie-2>0&&qipan[hang-1][lie-2]==0)
{
pt[0].x++;
hang=hang-1;
lie=lie-2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie); //返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+1<=shu&&lie-2>0&&qipan[hang+1][lie-2]==0)
{
pt[0].x++;
hang=hang+1;
lie=lie-2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang-2>0&&lie-1>0&&qipan[hang-2][lie-1]==0)
{
pt[0].x++;
hang=hang-2;
lie=lie-1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+2<=shu&&lie-1>0&&qipan[hang+2][lie-1]==0)
{
pt[0].x++;
hang=hang+2;
lie=lie-1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang-2>0&&lie+1<=shu&&qipan[hang-2][lie+1]==0)
{
pt[0].x++;
hang=hang-2;
lie=lie+1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+2<=shu&&lie+1<=shu&&qipan[hang+2][lie+1]==0)
{
pt[0].x++;
hang=hang+2;
lie=lie+1;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang-1>0&&lie+2<=shu&&qipan[hang-1][lie+2]==0)
{
pt[0].x++;
hang=hang-1;
lie=lie+2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
if(hang+1<=shu&&lie+2<=shu&&qipan[hang+1][lie+2]==0)
{
pt[0].x++;
hang=hang+1;
lie=lie+2;
pt[pt[0].x].x=hang;
pt[pt[0].x].y=lie;
qipan[hang][lie]=pt[0].x;
MoveNext(hang,lie);//返回點
}
hang=pt[pt[0].x].x;
lie=pt[pt[0].x].y;
Print();
{
qipan[hang][lie]=0;
pt[0].x--;
}
}
int main()
{
printf(Input the num:);
int n;
scanf(%d,&n);
Horse h(n);
h.MoveNext(1,1);
return 0;
}
翹了一學期的數據結構,趕工補作業中,我用的是貪心演算法,速度不錯,秒出。。
#include<iostream>
#define M 12
#define D 8
using namespace std;
int pathnum(int x,int y);
void initdata();
int pathnum(int x,int y);
void findway(int x , int y );
int board[M][M]={0,0};
int HTry1[D]={ -2, -1, 1, 2, 2, 1, -1, -2 };
int HTry2[D]={ 1, 2, 2, 1, -1, -2, -2, -1 };
void initdata()
{
int i , j;
for ( i=0 ; i<2 ; i++ )
{
for ( j=0;j<M;j++)
{
board[i][j]=1;
board[M-i-1][j]=1;
board[j][i]=1;
board[j][M-i-1]=1;
}
}
}
int main()
{
void findway(int x , int y );
int startx,starty,i,j;
cout<<請輸入初始坐標值<<endl;
initdata();
cin>>startx>>starty;
findway(startx,starty);
for(i=2;i<M-2;i++)
{
//以圖形方式顯示行走步數
for(j=2;j<M-2;j++)
printf(%4d,board[i][j]);
cout<<endl<<endl;
}
return 0;
}
void findway(int x , int y )
{
x=x+1;
y=y+1;
int stepnum=1;
int num[D];
int i,min,minx,miny;
board[x][y]=stepnum;
for ( stepnum=2; stepnum<=(M-4)*(M-4) ;stepnum++ )
{
min=8;
for (i=0;i<D;i++)
{
if (board[x+HTry1[i] ][ y+HTry2[i] ] ==0)
{
num[i]=pathnum( x+HTry1[i] , y+HTry2[i] );
if (num[i]<min)
{
min=num[i];
minx = x+HTry1[i];
miny = y+HTry2[i];
}
}
}
x=minx;
y=miny;
board[x][y]=stepnum;
}
}
int pathnum(int x,int y)
{
//返回當前位置可走的方向數目
int count=0 ;
for (int i=0;i<D;i++)
{
if (board[ x+HTry1[i] ][ y+HTry2[i] ]==0)
{
count++;
}
}
return count ;
}

熱點內容
銀行密碼泄露應該辦理什麼手續 發布:2024-03-29 05:01:40 瀏覽:521
sql插入二進制 發布:2024-03-29 05:00:32 瀏覽:21
安卓外部資源怎麼下載 發布:2024-03-29 04:01:17 瀏覽:244
華為被加密碼的相冊在哪裡查看 發布:2024-03-29 04:00:27 瀏覽:747
自動欣悅版有哪些配置 發布:2024-03-29 03:48:26 瀏覽:287
如何用腳本搶 發布:2024-03-29 03:01:59 瀏覽:120
火影忍者手游配置怎麼調 發布:2024-03-29 02:53:53 瀏覽:103
編程畫櫻花 發布:2024-03-29 02:11:24 瀏覽:473
騰訊雲伺服器1mb老掉線 發布:2024-03-29 01:56:11 瀏覽:215
執行sql語句的存儲過程 發布:2024-03-29 01:52:37 瀏覽:697