java骑士巡游问题源码a
需求分析
编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘 — 问题无解）。
输出形式： 输出骑士所走的路线，用数字标记第几步的位置。
2.2 概要设计
本题的主要思路：首先确定骑士所走的方向，用两个数组标志。然后用回溯方法进行求解，若遇到没走过（0标记），则走到这个位置上（1标记），否则返回，进行下一个未走方向判断。若超过总大小，表示已经走完，返回true，最后打印各位置的数字，用以标记所走的路线。
2.3 详细设计与编码
见上传源程序。
2.4 调试分析
在这个程序中，主要是用了回溯的思想。回溯思想中，有初值的设置，回溯的结束的设置。
2.5 用户使用与说明
用户根据提示输入适当的值。而在这个程序中，我把它固化了，无需用户输入。如果要输入，在主函数中改变初始横纵坐标。
2.6 测试数据
2.7 心得体会
通过这次实验，让我更深地理解了回溯的基本思想。回溯是要有回溯结束的条件，才能退出回溯，否则会进入无限循环，从而使程序无法结束。设置走法有许多种，我用了两个数组来表示，这主要是简化程序代码的复杂度。class Queen
{
Queen()
{
for(int i=0;i<QueenNum;++i)
chess[i]=-1;
solve(0);
}
public void solve(int num) //num为现在要放置的行数
{
boolean[] qsave=new boolean[QueenNum]; //判断能否放置皇后
for(int i=0;i<QueenNum;++i)
qsave[i]=true; //首先设置每一行都能放置
int i=0; //从第一行开始检查
while(i<num) //若所检查的行数小于要放置的行数，执行一下代码
{
qsave[chess[i]]=false; //先将步数设在棋盘外
int k=num-i;
if((chess[i]+k>=0)&&(chess[i]+k<QueenNum))
qsave[chess[i]+k]=false;
if((chess[i]-k>=0)&&(chess[i]-k<QueenNum))
qsave[chess[i]-k]=false;
++i;
}
for(i=0;i<QueenNum;++i)
{
if(qsave[i]==false)continue;
chess[num]=i;
if(num<QueenNum-1)
solve(num+1);
else //最后一位皇后的位置
{
System.out.println("1 2 3 4 5 6 7 8");
for(i=0;i<QueenNum;++i)
{
String row="";
if(chess[i]==0);
else for(int j=0;j<chess[i];++j)row+="+ ";
row+="Q";
原文请找腾讯752018766辣,文-论'文.网http://www.751com.cn/ System.out.println(row);
}
System.exit(1); //只取一种解法
}
}
}
private final int QueenNum=8; //皇后的个数
private int[] chess=new int[QueenNum]; //每一个皇后放置的位置
}
class QueenTest
{
public static void main(String[] args)
{
System.out.print("/*************************************************\n\n"+
"File name: 软件设计课程设计提高题17（提高题17.java）\n\n"+
"Author: 计06-1 郭献铮 Date: 08.12.1\n\n"+
"Description: 八皇后问题；\n\n"+
"Function List: // 主要函数列表，每条记录应包括函数名及功能简要说明\n\n"+
"1.main()函数 完成各种提示与主操作输入输出\n\n"+
"2.solve()函数 解决八皇后的排列；\n\n"+
"*****************************************************/\n\n");
Queen q=new Queen();1829