骑士周游问题 --- 递归解法 --- java代码
2024-10-19 03:38:31
骑士游历：
定义了向量的数组M，行数组X，列数组Y， 棋盘plane，计数器count，走动步数step
需要注意的是，递归函数的进入前的验证，原先的想法是传入来时的方向参数，可是这样的想法被实践否定了，
从理论上看，一个棋子走向哪里是不受它的过去制约的，最近的过去也不例外，
详情请见：http://en.wikipedia.org/wiki/Knights_tour
代码如下：
/**
* Created by kodoyang on 2014/5/3.
*/
public class KnightTour {
private static final int[][] M= {
{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}
};
private static final int[] X = {0, 1, 2, 3, 4, 5, 6, 7}, Y = {0, 1, 2, 3, 4, 5, 6, 7};
private static final int[][] plane = new int[X.length][Y.length];
public final static void main(String[] args){
int[] O = {0, 0};
next(X[0], Y[0], 1);
}
private static int count = 0;
private final static void next(final int x, final int y, final int step){
plane[x][y] = step;
if(step == 64)
print( ++count );
else {
for(int i = 0; i < M.length; i++){
int[] v = M[i];
int _x = x + v[0], _y = y + v[1];
if (valid(_x, _y))
next(_x, _y, step + 1);
}
}
plane[x][y] = 0;
}
private static final boolean valid(final int x, final int y){
boolean result = false;
if(x >= X[0] && x <= X[7] && y >= Y[0] && y <= Y[7]){
result = plane[x][y] == 0;
}
return result;
}
private static final void print(int step){
System.out.println("---------------------------------- " + step + " ------");
for(int i = X[0]; i <= X[7]; ++i) {
for (int j = Y[0]; j <= Y[7]; ++j) {
System.out.print("\t" + plane[i][j]);
}
System.out.println();
}
System.out.println("---------------------------------------------------");
}
}
这里一共有26,534,728,821,064种结果，程序被我提前停掉了，运行结果如下：
---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- ---------------------------------- ------ --------------------------------------------------- Process finished with exit code -
最新文章
- [No00007D]2016-面经[上]
- PHP的 Mysqli扩展库的多语句执行
- docker学习笔记一：基本安装和设置容器静态ip
- hdu - 4608 - I-number
- 获得sql对应的binary
- js 只能输入数字和小数点
- 数据结构学习——shell排序的C语言实现
- CentOS允许/禁止ping的方法
- 原生JS添加节点方法与jQuery添加节点方法的比较及总结
- Rx RxJava【Operators】操作符
- 【转】java读写二进制文件的解决方法
- VPN工作原理
- eclipse远程调试Linux环境下的web项目
- 【转】GAMITBLOBK中固定解、浮点解、约束解、松弛解等解类型解释
- LoadRunner 11 error:Cannot initialize driver dll
- 黑盒测试实践——day04
- vue学习笔记——组件的优化
- flutter学习地址
- (转)获取 request 中用POST方式"Content-type"是"application/x-www-form-urlencoded;charset=utf-8"发送的 json 数据
- 使用Python制作第一个爬虫程序