(10.1.1)--ch10-01theKnight'stourproblem-E.pdf

《(10.1.1)--ch10-01theKnight'stourproblem-E.pdf》由会员分享，可在线阅读，更多相关《(10.1.1)--ch10-01theKnight'stourproblem-E.pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Data Structures and AlgorithmsThe Knights Tour ProblemData Structures and AlgorithmsData Structures and Algorithms2Problem Description:Experiment：The Knights Tour ProblemThe knight is placed on a square on the chessboard.It moves according to the rules of chess.Each square can only be entered once.G

2、o through all sixty-four squares on the chessboard.Write a non-recursive program to find out the route of the knight.According to the route,fill the chessboard with Numbers 1 to sixty-four,and output it.Data Structures and AlgorithmsData Structures and Algorithms3problem analysisExperiment：The Knigh

3、ts Tour ProblemBoard：int Board88=0;0：the position has not been passed i:164 the ith step has reached hereSet the starting position;Step=1;Set the chessboard;Step64Find the next step;Updata the Step;Updata the Board;output start over0123456701234567YNstep number：int Step;/he number of steps completed

4、Data Structures and AlgorithmsData Structures and Algorithms4problem analysisExperiment：The Knights Tour ProblemThe Knights move0123456701234567Position point type：typedef struct int x;/row number（07）int y;/column number（07）Spot;Define Variable：Spot Cur，Next;/Represents the current and next position

5、 points.Data Structures and AlgorithmsData Structures and Algorithmsdirection12345678Line changeColumn change5problem analysisExperiment：The Knights Tour Problem12345678defining array：int direction29=0,-2,-1,1,2,2,1,-1,-2 ,0,1,2,2,1,-1 -2,-2,-1 ;-21-1212212-11-2-1-2-2-1If the current position is Cur

6、，Go in the i-th direction,Then the next point is：Next.x=Cur.x+direction0 i;Next.y=Cur.y+direction1 i;0123456701234567Data Structures and AlgorithmsData Structures and Algorithmsint Feasible(int x,int y)if(0=x)&(x8)&(0=y)&(y8)&(Boardxy=0)）return 1；else return 0；6Experiment：The Knights Tour Problempro

7、blem analysis1、The position must be within the checkboard：(0=x)&(x8)&(0=y)&(y8)）The condition under which the position is feasible：2、The position has not been visited：Boardxy=0 int NextDirection(Spot Cur)int i,x,y;for(i=1;i=8;i+)x=Cur.x+Direction0i;y=Cur.y+Direction1i;if(Feasible(x,y)return i;return

8、 0;Data Structures and AlgorithmsData Structures and Algorithms7Experiment：The Knights Tour Problemproblem analysis495241301105053313811401348514229149254323722391274743281583243336214423617462734191625435204526518Conclusion1：When we cant find the next feasible position,that is to say,the return val

9、ue of the NextDirection is 0,we need to back off.Conclusion2：Positions passed by the knight should be stored in the stack.That is,when the NextDirection returns a non-zero value,the current position is pushed,and then go to the next step.Conclusion3：Do two things when back off The Cur position on th

10、e Board set 0,Step-；Pop a position,set as the Cur.0123456701234567123456783054Step:Cur.x:Cur.y:Data Structures and AlgorithmsData Structures and Algorithms8problem analysisExperiment：The Knights Tour Problem k=NextDirection(Cur);k!=0？Find the Next position；Push(Stack,Cur);Cur=Next;Step+;BoardCur.xCu

11、r.y=Step;BoardCur.xCur.y=0,Step-;Cur=Pop(Stack);设置起始点;step=1;设置棋盘;Step64 output start overCur.x=m;Cur.y=n;Step=1;BoardCur.xCur.y=Step;1212YNYNFind the next step;Updata the Step;Updata the Board;Data Structures and AlgorithmsData Structures and Algorithms9Experiment：The Knights Tour Problemproblem an

12、alysis4952413011050533138114013485142291492323722391274743281583243336214423617462734191625435204526518012345670123456712345678typedef struct int x;/line number（07）int y;/column number（07）int d;/Number of directions explored（08）Spot;Modify the definition of the Spot type：Conclusion4：After back off,w

13、e can only continue to detect from the direction of the last detection,but not from the beginning.1153Step:Cur.x:Cur.y:Data Structures and AlgorithmsData Structures and Algorithms10problem analysisExperiment：The Knights Tour Problemk=NextDirection(Cur);k!=0？Find the Next position；Push(Stack,Cur);Cur

14、=Next;Step+;BoardCur.xCur.y=Step;BoardCur.xCur.y=0,Step-;Cur=Pop(Stack);设置起始点;step=1;设置棋盘;step64 output start overCur.x=m;Cur.y=n;Step=1;BoardCur.xCur.y=Step;1212YNYNCur.d=k;Cur.d=0;Next.d=0;Data Structures and AlgorithmsData Structures and Algorithms11Experiment：The Knights Tour Problemproblem anal

15、ysis49524130110505331381140134851422914923237223912747432815832433362144236174627341916254352045265180123456701234567678int NextDirection(Spot Cur)int i,x,y;for(i=1;i=8;i+)x=Cur.x+Direction0i;y=Cur.y+Direction1i;if(Feasible(x,y)return i;return 0;for(i=Cur.d+1;i=8;i+)5Backoff：The top of stack is:e.x

16、e.y e.d:03611553Step:Cur.x:Cur.y:Cur.d:Backoff：The top of stack is:e.x e.y e.d:Data Structures and AlgorithmsData Structures and AlgorithmsExperiment：The Knights Tour Problemproblem analysis49524130110505331381140134851422914923237223912747432815832433362144236174627341916254352045265180123456701234

17、56712rollback：point Cur set to 0，Step-；BoardCur.xCur.y=0;Step-;pop stack a point，set the Cur.Pop(&s,&Cur);121155352036Step:Cur.x:Cur.y:Cur.d:Backoff：The top of stack is:e.x e.y e.d:Data Structures and AlgorithmsData Structures and Algorithms13Experiment：The Knights Tour Problemproblem analysis495241

18、30110503138114013485142291492323722391274743281583243336214423617462734191625435204526518012345670123456778int NextDirection(Spot Cur)int i,x,y;for(i=Cur.d+1;i=8;i+)x=Cur.x+Direction0i;y=Cur.y+Direction1i;if(Feasible(x,y)return i;return 0;22103652Step:Cur.x:Cur.y:Cur.d:Backoff：The top of stack is:e.

19、x e.y e.d:Data Structures and AlgorithmsData Structures and Algorithms14Experiment：The Knights Tour Problemproblem analysis495241301105031381140134851422914923237223912747432815832433362144236174627341916254352045265180123456701234567rollback：point Cur set to the 0，Step-；BoardCur.xCur.y=0;Step-;pop

20、stack a point，set the Cur.Pop(&s,&Cur);0365251221Step:Cur.x:Cur.y:Cur.d:Backoff：The top of stack is:e.x e.y e.d:Data Structures and AlgorithmsData Structures and Algorithms15Experiment：The Knights Tour Problemproblem analysis494130110503138114013485142291492323722391274743281583243336214423617462734

21、19162543520452651801234567012345672345678int NextDirection(Spot Cur)int i,x,y;for(i=Cur.d+1;i=8;i+)x=Cur.x+Direction0i;y=Cur.y+Direction1i;if(Feasible(x,y)return i;return 0;Move on：direction522151Step:Cur.x:Cur.y:Cur.d:Data Structures and AlgorithmsData Structures and AlgorithmsStep:Cur.x:Cur.y:5116

22、Experiment：The Knights Tour Problemproblem analysis494130110503138114013485142291492323722391274743281583243336214423617462734191625435204526518Take a step in the direction of number 5：Find the next position；Next.x=Cur.x+direction05;Next.y=Cur.y+direction15;Next.d=0;Record the direction as the d of

23、Cur，Push the Cur into the stack;Cur.d=5;push(Cur);Set Cur to Next;Cur=Next;Step+;Updata the Board;BoardCur.xCur.y=(+Step);012345670123456752Move on：direction5Into the stack:Cur.x:Cur.y:Cur.d:22151525Cur.d:225410Data Structures and AlgorithmsData Structures and Algorithms17Experiment：The Knights Tour

24、 Problemproblem analysisStart at（0，0）：Start at（4，2)Start at（3，0）：1、Successful instances：2、Unsuccessful instance：When the starting point is(2,4)or(0,6),After running for a few minutes,there was still no result.Data Structures and AlgorithmsData Structures and Algorithms18Experiment：The Knights Tour P

25、roblemproblem analysis（1）Count the times of back-off Add variable count Record the number of setbacks.Its initially set to 0,Every time back count+;When the loop ends,Print its count value.（2）Analyze the solution space tree of the problem This paper analyzes the reason of the long running time of th

26、e algorithm and tries to find the method to improve the efficiency.Data Structures and AlgorithmsData Structures and Algorithms19Experiment：The Knights Tour Problem In this experiment,we use the stack to complete the solution of the knights tour problem.we need to focus on：1.The purpose of using the stack.2.The timing of push and pop stack.3.How to record the detected directions,to avoid trapped in an endless loop.problem analysisData StructuresThank you allThank you all！