跳馬問題、騎士遍歷問題ppt課件

1、跳馬問題 跳馬問題也稱騎士遍歷問題：在n*n方格的棋盤上，從任意指定的方格出發(fā)，為象棋中的馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。 1；.問題分析如下圖所示，一只馬在棋盤的某一點，它可以朝8個方向前進，方向向量分別是： (-2,1)、 (-1,2) (1,2)、 (2,1)、(2,-1) 、(1,-2)、 (-1,-2)、(-2,-1)。2；. 從中任選擇一個方向前進，到達新的位置。在從新的位置選擇一個方向前進，繼續(xù)，直到無法前進為止。無法前進可能有如下原因：下一位置超出邊界、下一位置已經(jīng)被訪問過。當馬已經(jīng)無法前進時，就回退到上一位置，從新選擇一個新的方向前進；如果還是無法前進，就再

2、回退到上一位置，以此類推。3；.經(jīng)分析，本問題可以運用回溯法的思想求解：1.該問題的解空間的組織形式是一顆八叉樹，一個可行的解就是從根節(jié)點到葉子節(jié)點的一條路徑。2.控制策略則是馬必須在棋盤內(nèi)。4；.代碼v#includev#include v#include vconst int n=6; / 表示棋盤的長和高nvint qipann+1n+1; / 記錄棋盤是否被跳過vstatic int cmq; / 步數(shù)vint OK=0; / 沒有被使用vint xLabel,yLabel;vvoid shuchu()vv coutt;v for(int i1=1;i1=n;i1+)v couti1列

3、t;v for(int i=1;i=n;i+)v v coutendl;v couti行t;v for(int j=1;j=n;j+)v v coutqipanijt;v v coutendl;v v 5；.vint tiaoma(int x,int y)vvif(cmq =n*n & (x-2=xLabel & y+1 = yLabel) |(x-1=xLabel & y+2 = yLabel) |(x+1=xLabel & y+2= yLabel) | (x+2 = xLabel & y+1 = yLabel) |(x+2 = xLabel &

4、; y-1 = yLabel) |(x+1= xLabel & y-2=yLabel) |(x-2=xLabel & y-1=yLabel) |(x-1=xLabel & y-2=yLabel)vv shuchu();v OK=1;v return 0;vv v if(1 = x-2 & y+1 = n & qipanx-2y+1 = 0)v v qipanx-2y+1=+cmq; / 1v tiaoma(x-2,y+1);v v if(1=x-1&y+2=n&qipanx-1y+2=0)v v qipanx-1y+2=+cmq; / 2

5、v tiaoma(x-1,y+2);v v if(x+1=n&y+2=n&qipanx+1y+2=0)v v qipanx+1y+2=+cmq; / 3v tiaoma(x+1,y+2);v v if(x+2=n&y+1=n&qipanx+2y+1=0)v v qipanx+2y+1=+cmq; / 4v tiaoma(x+2,y+1);v v 6；.vif(x+2=n&1=y-1&qipanx+2y-1=0)v v qipanx+2y-1=+cmq; / 5v v tiaoma(x+2,y-1);v v if(x+1=n&1=y-2&a

6、mp;qipanx+1y-2=0)v v qipanx+1y-2=+cmq; / 6v tiaoma(x+1,y-2);v v if(1=x-1&1=y-2&qipanx-1y-2=0)v v qipanx-1y-2=+cmq; / 7v tiaoma(x-1,y-2);v v if(1=x-2&1=y-1&qipanx-2y-1=0)v v qipanx-2y-1=+cmq; / 8v tiaoma(x-2,y-1);v v v cmq -;v qipanxy = 0; / 回朔vreturn 0;v7；.vint main()vv for(int i=1;i=n;i+)v for(int j=1;j=n;j+)v qipanij=0;v v for(i=1;i=n;i+) /該處分別計算從點(1,1)到點(n,n)作為起始點，可以找到哪些回路v for(int j=1;j=n;j+)v v xLabel= i;v yLabel = j;v cmq = 1;v for(int k1=1;k1=n;k1+)v for(int k2=1;k2=