马走日棋盘算法

2016-01-29 12:14 505 1 收藏

马走日棋盘算法,马走日棋盘算法

【 tulaoshi.com - C语言心得技巧 】

马走日棋盘算法
作者:哈达

下载本文示例源代码

问题描述

在给定大小的方格状棋盘上, 将棋子”马”放在指定的起始位置 , 棋子”马” 的走子的规则为必须在棋盘上走”日”字; 从棋子”马”的起始位置开始, 搜索出一条可行的路径, 使得棋子”马”能走遍棋盘上的所有落子点, 而且每个落子点只能走一次;

例如: 棋盘大小为5*5 , 棋子马放的起始落子点为 ( 3 , 3 ) ; 算法需要搜索一条从位置( 3 , 3 ) 开始的一条包括从( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) … ( 5 , 1 ) , ( 5 , 2 ) , ( 5 , 3 ) , ( 5 , 4 ) , ( 5 , 5 ) 总共25个可以落子的全部位置;


问题分析
通过上面的问题描述,我们对问题的内容有了正确的理解,接下来我们开始对问题进行具体细致的分析,以求找到解决问题的正确的可行的合理的方法;

首先我们需要在程序中用合适的数据结构表示在问题中出现的棋盘 , 棋子 , 棋子的走子过程 ; 接下来我们需要对核心问题进行分析, 即如何搜索一条可行的路径 , 搜索采取何种策略 , 搜索的过程如何表示 ;

对于一个大小为n*m大小的棋盘 , 棋子从当前位置( x , y ) 出发,可以到达的下一个位置( x’ , y’ ):

(1) ( x +1 , y +2 )
(2) ( x +1 , y –2 )
(3) ( x – 1, y +2 )
(4) ( x – 1, y – 2 )
(5) ( x +2, y +1)
(6) ( x +2, y – 1)
(7) ( x -2, y + 1)
(8) ( x -2, y – 1 )

限制条件:

1. 1 <= x’ <= n , 1 <= y’ <= m; ( n : 棋盘的高度 , m: 棋盘的宽度 );
2. ( x’ , y’ ) 必须是棋子记录表中没有包括的新位置;
3. 棋子走子过程记录表中没有包括棋盘上的所有可以落子的位置;


对这个过程不停迭代的过程也就是对解空间搜索的过程, 搜索直到棋子走子记录表中包括棋盘上的所有可以落子的位置 , 就搜索到了一条可行的路径,路径包括棋盘上的所有落子点;或者搜索完整个解空间,仍然找不到一条可行的解,则搜索失败;

(本文来源于图老师网站,更多请访问https://www.tulaoshi.com)


下面我们举例来说明搜索的过程;

棋盘大小 : 5 * 5
棋子起始位置 : ( 3 , 3 )
搜索过程 :

(1) 从当前位置( 3 , 3 )出发可以有8个新的位置选择; 首先选择新位置1 , 将新位置1
作为当前棋子位置 , 开始新的搜索;
如果搜索不成功, 则搜索回退, 选择新位置2 ,以此类推,就可以搜索完整个解空间,只要从该问题有解 , 则可以保证一定可以搜索到;


2) 从新位置1 开始新的搜索,可以选择的新位置有两个,先选择位置1 , 从位置1开始新的搜索;


(3) 下图是经过18步搜索之后的状态, 从位置18出发, 已经没有没走过的新位置可以选择, 则搜索失败;

搜索回退到17步, 从位置17开始搜索除了18之外的新位置, 从图上可以看出已经没有新位置可以选择,继续回退到16步, 搜索除了17的新位置; 以此类推.知道搜索完整个解空间 , 或者搜索到一个可行解;

(本文来源于图老师网站,更多请访问https://www.tulaoshi.com)

(4) 下图展示了搜索成功的整个搜索过程;

系统设计

一. 用例图


二. 类设计

三. 顺序图

四. 核心算法设计

通过上面的分析, 我们现在可以将算法的大概框架写出来了 , 具体的代码请参考本

来源:https://www.tulaoshi.com/n/20160129/1485170.html

延伸阅读
标签: 黄油 鸡蛋
负责任的说:这将是你吃过最好吃的饼干! 1.熟杏仁打磨成粉,也可以用其他坚果粉代替; 2.蛋白加糖到到干性发泡,就是成为固体状。 3.混合1+2,装进裱花袋或保险模,在铺锡纸的烤盘上挤成圆圈或其他形状。 4.烤箱预热,150度15分钟。 真的相当好吃,不试不知道哦! 猫爪饼干 1.黄油软化后加入糖,打到体积变大颜色变淡,加盐、低粉...
标签: 黄油 鸡蛋 烘焙
手绘蕾丝饼干 1、那么先从做饼干底开始:低粉65G,可可粉10G和泡打粉1/8茶匙混合过筛。 2、黄油32.5G室温软化后加糖粉35G打发。 3、分次加入全蛋液15G搅拌均匀。 4、筛入第一步的混合粉类。用翻拌和切拌的手法混合至没有干粉。我个人是不喜欢过度搅拌饼干面团的,所以一直是这样做。 5、把拌好的面团放进保鲜袋,冰箱冷藏1小时以上。 ...
标签: 猪肉
棋盘饼干 1、75g黄油室温软化,加入40g白糖打发至颜色变浅,体积稍微有点点膨胀。 2、逐次加入30g打散的鸡蛋,搅拌均匀。(方子里剩下的10g蛋液是用来做粘合剂的) 3、将拌入蛋液的黄油平均分成2份。一份加入80g低筋面粉,揉成白面团;另一份加入75g低筋面粉和5g可可粉揉成黑面团。(揉的时候可能会觉得很干,怎么揉都是粉粉,没关系,多...
标签: 甜品 点心
手绘蕾丝饼干 1、那么先从做饼干底开始:低粉65G,可可粉10G和泡打粉1/8茶匙混合过筛。 2、黄油32.5G室温软化后加糖粉35G打发。 3、分次加入全蛋液15G搅拌均匀。 4、筛入第一步的混合粉类。用翻拌和切拌的手法混合至没有干粉。我个人是不喜欢过度搅拌饼干面团的,所以一直是这样做。 5、把拌好的面团放进保鲜袋,冰箱冷藏1小时以上。 ...
已知一棵二叉树按顺序方式存储在数组 A[1..n]中。设计算法求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。 武汉大学2000年第五(1)题(8’) #inlcude stdio.h parent(int A[],int i,int j) {int k,m; m=k=0; if(i==1j==1A[i]==0A[j]==0i==j) // A[i]==0或A[j]==0表示不存在该结点 ...

经验教程

309

收藏

82
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部