问题说明:
骑士游戏,在十八世纪倍受数学家与拼图迷的注意,骑士的走法为西洋棋的走发,骑士可以由任何一个位置出发,它要如何走完所有的位置。
public class Knight {
public boolean travel(int startX,
int startY, int[][] board) {
// 对应骑士可以走的八个方向
int[] ktmove1 = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] ktmove2 = {1, 2, 2, 1, -1, -2, -2, -1};
// 下一个出路的位置 int[] nexti = new int[board.length];
int[] nextj = new int[board.length];
// 记录出路的个数
int[] exists = new int[board.length];
int x = startX;
int y = startY;
board[x][y] = 1;
for(int m = 2; m <= Math.pow(board.length, 2); m++) {
for(int k = 0; k < board.length; k++) {
exists[k] = 0;
}
int count = 0;
// 试探八个方向
for(int k = 0; k < board.length; k++) {
int tmpi = x + ktmove1[k];
int tmpj = y + ktmove2[k];
// 如果是边界,不可以走
if(tmpi < 0 || tmpj < 0 ||
tmpi > 7 || tmpj > 7) {
continue;
}
// 如果这个方向可以走,记录下来
if(board[tmpi][tmpj] == 0) {
nexti[count] = tmpi;
nextj[count] = tmpj;
// 可走的方向加一个
count++;
}
}
int min = -1;
if(count == 0) {
return false;
}
else if(count == 1) {
min = 0;
}
else {
// 找出下个位置的出路数
for(int l = 0; l < count; l++) {
for(int k = 0; k < board.length; k++) {
int tmpi = nexti[l] + ktmove1[k];
int tmpj = nextj[l] + ktmove2[k];
if(tmpi < 0 || tmpj < 0 ||
tmpi > 7 || tmpj > 7) {
continue;
}
if(board[tmpi][tmpj] == 0)
exists[l]++;
}
}
int tmp = exists[0];
min = 0;
// 从可走的方向寻找最少出路的方向
for(int l = 1; l < count; l++) {
if(exists[l] < tmp) {
tmp = exists[l];
min = l;
}
}
}
// 走最少出路的方向
x = nexti[min];
y = nextj[min];
board[x][y] = m;
}
return true;
}
public static void main(String[] args) {
int[][] board = new int[8][8];
Knight knight = new Knight();
if(knight.travel(
Integer.parseInt(args[0]),
Integer.parseInt(args[1]), board)) {
System.out.println("走棋完成!");
}
else {
System.out.println("走棋失败!");
}
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] < 10) {
System.out.print(" " + board[i][j]);
}
else {
System.out.print(board[i][j]);
}
System.out.print(" ");
}
System.out.println();
}
}
}
分享到:
相关推荐
骑士旅游(Knight tour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完[所有的位置?
国际象棋游戏一个经典的例子就是骑士巡游(knight s tour)问题,这个问题要求从棋盘上任意给定的方格开始移动骑士,相继地到达所有的64个方格,进入每个方格一次且仅进入一次。通常情况下,我们用如下方法表示一个...
可以算做非常经典的算法了,骑士的走法,基本上可以使用递回来解决,但是纯綷的递回在维度大时相当没有效率,比较聪明的解法由J.C. Warnsdorff在1823年提出,简单的说,先将最难的位置走完,接下来的路就宽广了,...
骑士漫游,运用堆栈采用回溯法遍历棋盘所有位置,没有重复路线。
骑士周游列国问题(Knight’s Tour Problem)又称跳马问题,马踏棋盘问题,或骑士漫游问题。在一张国际象棋棋盘上(8*8方格),骑士(knight,马)位于任意一个位置。问如何才能让骑士不重不漏的经过棋盘上的每个格...
国际象棋遍历:国际象棋的马或者骑士,在棋盘上面走日子,任意输入起始位置,输出遍历矩阵
用递归算法是实现骑士遍历棋盘问题!!c++语言实现
马走棋盘的实现。用递归实现的。通过递归实现了马走棋盘
Your task is to write a program to calculate the minimum number of moves移动次数 needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov. ...
问题描述:将马随机放在国际象棋的 8X8 棋盘中的某个方格中,马按走棋规则进行移动。要求每个方格上只进入一次,走遍棋盘上全部 64 个方格。编制递归程序,求出马的行走路线 ,并按求出的行走路线,将数字 1,2,…,...
在一张国际象棋棋盘上(8*8方格),骑士(knight,马)位于任意一个位置。问如何才能让骑士不重不漏的经过棋盘上的每个格?本问题中已知骑士位置(m,n),其中0=,n,要求给出骑士行走路径,路径可用8*8矩阵输出,其中...
实习 2.4 马踏棋盘 C++编写, DEV_C++ 编译器下运行通过 PS: 启发式搜索,非递归实现. 应付作业,实用价值一点点... 同时赚资源分 PS PS: 比较经典的题目,不是太过无聊,不过一般都是递归搞定就OK了,理解栈的意义就...
国际象棋马走棋盘:在棋盘中任意选择一个位置,找出一条遍历棋盘的路径.
国际象棋马走棋盘:选择棋盘上的某个位置,找出一条遍历路径.
问题描述:将马随机放在国际象棋的 8X8 棋盘中的某个方格中 马按走棋规则进行移动 要求每个方格上只进入一次 走遍棋盘上全部 64 个方格 编制递归程序 求出马的行走路线 并按求出的行走路线 将数字 1 2 … 64 依次填入...
JAVA实现骑士巡游(马踏棋盘) 8X8格 输入起始X轴Y轴坐标
实现马走日的搜索算法,VC++6.0 和window XP系统下调试通过的
一个简单的数据结构问题,马走遍整个棋盘的C++小程序代码
马走日棋盘算法.doc
骑士游历问题,算法设计与分析,骑士游历问题