java题目：骑士周游

==========================================================

如果单纯只要解法，貌似用递归更好一点。。。

==========================================================

public class KnightTraval{

public static void main(String[] args){

long startTime=System.currentTimeMillis()

Knight me=new Knight(new Grid(0,0))

Grid[] result=me.getPath()

for(Grid g:result){

System.out.format("%1$c%2$d-->",g.column()+'A',g.row()+1)

}

System.out.println("结束")

System.out.format("世档耗时衡乎%1$d毫咐返悉秒\n",System.currentTimeMillis()-startTime)

}

}

class Knight{

private Grid start

private boolean[][] arrived

public Knight(Grid start){

this.start=start

arrived=new boolean[8][8]

}

public Grid[] getPath(){

Grid[] result=new Grid[64]

for(int i=0i<64i++){

arrived[i/8][i%8]=false

}

arrived[start.row()][start.column()]=true

result[0]=start

if(next(result,1)){

return result

}

else{

return null

}

}

private boolean next(Grid[] path,int step){

Grid[] next=path[step-1].optimizeNext()

int x,y

for(int i=0i<next.lengthi++){

x=next[i].column()

y=next[i].row()

if(!arrived[y][x]){

arrived[y][x]=true

path[step]=next[i]

if(step==63){

return true

}

else{

if(next(path,step+1)){

return true

}

}

arrived[y][x]=false

}

}

return false

}

}

class Grid{

private int x,y

private static int[][] priority={

{2,3,4,4,4,4,3,2},

{3,4,6,6,6,6,4,3},

{4,6,8,8,8,8,6,4},

{4,6,8,8,8,8,6,4},

{4,6,8,8,8,8,6,4},

{4,6,8,8,8,8,6,4},

{3,4,6,6,6,6,4,3},

{2,3,4,4,4,4,3,2}

}

private static int[] deltaX=new int[]{1,1,-1,-1,2,2,-2,-2},deltaY=new int[]{2,-2,2,-2,1,-1,1,-1}

public Grid(int row,int column){

this.x=row

this.y=column

}

public Grid[] optimizeNext(){

Grid[] grids=next()

Grid temp

for(int i=0i<grids.length-1i++){

for(int j=grids.length-1j>ij--){

if(priority[grids[j].y][grids[j].x]>priority[grids[j-1].y][grids[j-1].x]){

temp=grids[j]

grids[j]=grids[j-1]

grids[j-1]=temp

}

}

}

return grids

}

public Grid[] next(){

Grid[] grids=new Grid[priority[y][x]]

int index=0,i,newX,newY

for(i=0i<8i++){

newX=x+deltaX[i]

newY=y+deltaY[i]

if(newX>=0&&newX<8&&newY>=0&&newY<8){

grids[index++]=new Grid(newX,newY)

}

}

return grids

}

public int column(){

return x

}

public int row(){

return y

}

}

好慢啊。。。。。。

A1-->B3-->C5-->D3-->E5-->F3-->D4-->E6-->F4-->D5-->E3-->F5-->D6-->E4-->F6-->G4-->

H2-->F1-->G3-->H5-->G7-->E8-->C7-->A8-->B6-->D7-->F8-->H7-->G5-->H3-->G1-->E2-->

C1-->A2-->B4-->A6-->B8-->C6-->D8-->B7-->A5-->C4-->D2-->B1-->A3-->C2-->E1-->G2-->

H4-->G6-->H8-->F7-->H6-->G8-->E7-->C8-->A7-->B5-->C3-->A4-->B2-->D1-->F2-->H1-->

结束

耗时506658毫秒

这是优先选择可能性大的格。

把Knight类的next方法中的for循环方向改为反向就是先走可能性小的格子。运行了3次，每次都在1秒内完成。。。差这老多。。。

猪哥回答：

呵呵，很经典的回溯法练习题，题我会解，不过国际象棋我不会，如果是马走日字的话，我就给你写一个吧。

原理很简单，一个棋盘看成一个什么二维什么来着，忘了，猪哥离开校门很多年。就是X轴、Y轴，棋盘左下角做原点，因为走日字，假定清世骑士起始坐标为(X,Y)，那么他的移动规则是(X-1,Y-2)或(X-1,Y+2)或(X-2,Y-1)或(X-2,Y+1)或(X+1,Y+2)或(X+1,Y-2)或(X+2,Y+1)或(X+2,Y-1)这8种移动规则，也不知道你看懂了没，下面我开始写代码。。。。

我事情比较多，先不急。。代码我慢慢写。

写了个简单的例子，List也是栈实现的一种方式，你先看看吧，不知道对你有没有帮助，当然你最好用3*4、4*5这样的小数字调试，大棋盘程序执行的时间很长，非常长。

import java.util.ArrayList

import java.util.List

/**

* 骑士周游demo,没有做防呆处理

* 棋盘模拟图，A假定为骑士起始位置

* 3

* 2

* 1

* 0 A

* 0 1 2 3

* @author 猪哥甲

*

*/

public class DemoKnight

{

private static int NX = 3//棋盘横向大小

private static int NY = 4//棋盘纵向大小

private static int[] dx= { 2, 1, -1, -2, -2, -1, 1, 2 }

private static int[] dy= { 1, 2, 2, 1, -1, -2, -2, -1 }

private int sx = 0//骑士起始横坐标

private int sy = 0//骑士起始纵坐标

private List points = new ArrayList()//用来有解的路线

private List steps = new ArrayList()//用来记录骑士走过的路线

public static void main(String[] args)

{

DemoKnight dkt = new DemoKnight()

dkt.sx = 0

dkt.sy = 0

List list = new ArrayList()

dkt.steps.add(dkt.getPointStr(dkt.sx, dkt.sy))

dkt.KnightTrav(dkt.sx, dkt.sy)

int size = dkt.points.size()

System.out.println("终于走完了。。。共找到"+size+"种解决方案")

for(int i=0i<sizei++){

List list2 = (List) dkt.points.get(i)

for(int j=0j<list2.size()j++){

System.out.print(list2.get(j)+"-->"晌乱)

}

System.out.println()

}

}

public boolean KnightTrav(int x, int y)

{

String str = null

boolean flag = false

//8种方向，每种方向假定有一个解法，8次答谨肢循环

for(int tx=0,ty=0,count=0count<8count++){

tx = x + dx[count]

ty = y + dy[count]

str = this.getPointStr(tx, ty)

if((tx>=0&&tx<NX)&&(ty>=0&&ty<NY)&&!this.steps.contains(str)){

flag = true

this.steps.add(str)

int size = this.steps.size()

if(!KnightTrav(tx, ty)){

System.out.println("一条路走到尽头,共走了"+size+"步")

}

if(size==NX*NY){

points.add(new ArrayList(this.steps))

}

this.steps.remove(size-1)

}

}

return flag

}

private String getPointStr(int x,int y){

StringBuffer sb = new StringBuffer("{")

sb.append(x)

sb.append(",")

sb.append(y)

sb.append("}")

return sb.toString()

}

}

曾经有网友发表跳马的C程序，但发现在棋盘较大时时间很长，今对其改进，本题使用栈，但你会发现不用退栈，只用N*N步走完，（其实不用栈，用数组）。

骑士周游世界

在一个8×8的方格棋盘中，按照国际象棋槐山游中马的行走规则从棋盘上的某一方格出发，开始在棋盘上周游，如铅销果能不重复地走遍棋盘上的每一个方格，这样的一条周游路线在数学上被称为国际象棋盘上马的哈密尔顿链。请你设计一个程序，从键盘输入一个起始方格的坐标，由计算机自动寻找并打印出国际象棋盘上马的哈密尔顿链。

【问题分析】

(1) 棋盘的表示方法

我们可以用一个8×8的二维数组A(I，J)来表唯镇示国际象棋的棋盘，在马还没有开始周游棋盘时，棋盘上所有的格都置为零。以后，马跳到哪个格，就将马跳跃的步数记录在相应的空格里。

(2) 马的跳跃方向的确定

在国际象棋的棋盘上，一匹马共有八个可能的跳跃方向。

我们设置一组坐标增量来描述这八个条约方向：

① （1，2） ② （2，1）

③ （2，-1） ④ （1，-2）

⑤ （-1，-2）⑥ （-2，-1）

⑦ （-2，1） ⑧ （-1，2）

(3) 马的跳跃方向的表示

设I表示行，J表示列，行增量为DI（R），列增量为DJ（R），则马向某个方向试探性地跳跃一步之后的新坐标应该表示为：NI=I+DI（R），NJ=J+DJ（R）。

(4) 朝某个方向试探性地跳跃一步再看下一步（取下一步最小可走方向（处里边角问题）），

任何一点的坐标加上要试探方向的坐标增量之后，都要判断一下是否已经超出了棋盘的边界。即：当I <0，或I >8，或J <0，或J >8时，都表示已经超出了棋盘的边界，这时，应该放弃该方向，转向试探下一个方向，在不出界的情况下，如果A（NI，NJ）=0，则表示该方向的前方有通路，可以继续向前跳跃。

如果A（NI，NJ）>0，则表示该格已经走过了，不能再走。放弃该方向，并转向下一个方向进行试探。

#include"stdio.h"

#include"conio.h"

#define N 19/*How many the horse最好不要超过19（超出屏幕）*/

int top=0

struct stack

{ int x

int y

int step

}ma[N*N+1]={{0,0,0}}

void push(int a[][N],int i,int j,int m)

{ ma[top].x=i

ma[top].y=j

ma[top].step=m

a[i][j]=++top

}

int pop(int a[][N])

{ int temp

top--

a[ma[top].x][ma[top].y]=0

ma[top].x=0

ma[top].y=0

temp=ma[top].step+1

ma[top].step=0

return temp

}

int jump(int i,int j,int a[][8])

{ int col[]={2,1,-1,-2,-2,-1,1,2}

int row[]={-1,-2,-2,-1,1,2,2,1}

int t,ti=i,tj=j,count=0

for(t=0t<8t++){

ti+=row[t]tj+=col[t]

if(judge(ti,tj,a))

count++ /*How many ways for the horse can jump for second time.*/

ti-=row[t]tj-=col[t]

}

return count

}

int judge(int i,int j,int a[][N]) /*Judge the position can jump */

{ if(i>=0&&j>=0&&i<N&&j<N&&a[i][j]==0)

return 1

return 0

}

sort(int a[8],int b[8])

{ int i,min=a[0],t=0

for(i=1i<8i++){

if(min>a[i]&&a[i]>-1&&a[i]<8){

min=a[i] /*Find the Min-way the horse to jump*/

t=b[i]

}

}

return t

}

[1] [2] 下一页

void disp(int a[][N])

{ int i,j

for(i=0i<Ni++){

for(j=0j<Nj++)

printf("%4d",a[i][j])

printf("\n")

}

}

void horse(int x,int y)

{ int i=x,j=y,min,ti,tj,t,temp=0,flag=0,temp1=0

int count[8],num[8]={0}

int col[]={2,1,-1,-2,-2,-1,1,2}

int row[]={-1,-2,-2,-1,1,2,2,1}

int a[N][N]={{0}}

for(x=0x<8x++)

count[x]=8

push(a,i,j,0)

while(top<N*N)

{ ti=itj=jtemp1=0flag=0

for(x=0x<8x++)

count[x]=8

for(t=tempt<8t++,temp1++){ /*How many ways for the horse can jump for first time*/

ti+=row[t]tj+=col[t]

if(judge(ti,tj,a)){

count[temp1]=jump(ti,tj,a)

num[temp1]=t

flag=1

}

ti-=row[t]tj-=col[t]

}

if(flag){

min=sort(count,num)

ti+=row[min]tj+=col[min]

push(a,ti,tj,min) /*In the stack*/

i=tij=tj

temp=0

}

else{

temp=pop(a) /*Return the stack*/

i=ma[top-1].x

j=ma[top-1].y

}

}

printf("\n\n")

disp(a)

}

main()

{ int x,y

do{

printf("Please enter the X-position :")

scanf("%d",&x)

printf("Please enter the Y-position :")

scanf("%d",&y)

if(x>N||y>N||x<1||y<1)

printf("Error! Try it again,X(1~%d),Y(1~%d)\n",N,N)

}while(x>N||y>N||x<1||y<1)

horse(x-1,y-1)

getch()

return 0

}

---