怎样用数据结构的栈和java语言实现骑士游历问题，即让一个国际象棋的马不重复的走完棋盘上的所有格子

猪哥回答：

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

原理很简单，一个棋盘看成一个什么二维什么来着，忘了，猪哥离开校门很多年。就是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也是栈实现的一种方式，你先看看吧，不知道对你有没有帮助，当然你最好用34、45这样的小数字调试，大棋盘程序执行的时间很长，非常长。

import javautilArrayList;

import javautilList;

/

骑士周游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();

dktsx = 0;

dktsy = 0;

List list = new ArrayList();

dktstepsadd(dktgetPointStr(dktsx, dktsy));

dktKnightTrav(dktsx, dktsy);

int size = dktpointssize();

Systemoutprintln("终于走完了。。。共找到"+size+"种解决方案");

for(int i=0;i<size;i++){

List list2 = (List) dktpointsget(i);

for(int j=0;j<list2size();j++){

Systemoutprint(list2get(j)+"-->");

}

Systemoutprintln();

}

}

public boolean KnightTrav(int x, int y)

{

String str = null;

boolean flag = false;

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

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

tx = x + dx[count];

ty = y + dy[count];

str = thisgetPointStr(tx, ty);

if((tx>=0&&tx<NX)&&(ty>=0&&ty<NY)&&!thisstepscontains(str)){

flag = true;

thisstepsadd(str);

int size = thisstepssize();

if(!KnightTrav(tx, ty)){

Systemoutprintln("一条路走到尽头,共走了"+size+"步");

}

if(size==NXNY){

pointsadd(new ArrayList(thissteps));

}

thisstepsremove(size-1);

}

}

return flag;

}

private String getPointStr(int x,int y){

StringBuffer sb = new StringBuffer("{");

sbappend(x);

sbappend(",");

sbappend(y);

sbappend("}");

return sbtoString();

}

}

呵呵，开始我也觉得没有破绽，后来发现了软件也会出昏招。原来原理很简单，只是把基本的开局定式以及常见的对弈拆解局面转换成数据库函数，当出现数据库招数，便调出同类型的宏功能。说到底，只是电脑软件做到了更多的对弈棋局收集，把相关的招数进行了数码汇编。比如：仙人指路开局，软件就会自动把存储在数据库中的符合这一定式类型的所有函数自动调出，选择基本应招（根据用户选手游戏难度不同，软件也会选择相应招数致胜比率和复杂程度）。所以按一般局面和软件玩，就等于和一个熟读兵法的谋士作战，很难赢。你会有看不透，想不到的时候，软件按步就班，数据库就是它的眼睛和脑袋。但是编制软件的并不是一流大师，他们手头上有的都是找得到的棋局，但是棋盘千变万化，有很多招式不可能存在软件中，所以软件也会碰到出昏招的时候。我们可以做一个小实验，两台电脑玩相同的象棋游戏，如果以A电脑进行先手，B电脑进行后手，以B电脑的招式来和A电脑下。百分之九十九的机率是和棋。如果我们用自己的方式 *** 作B电脑和A电脑进行至中局（有一方有多子优势），然后再让两台电脑自己下，肯定有一台电脑是输的。你就会发现输的电脑下的棋局很一般，因为它还是在以应对的形式开展，试问没有优势的情况下，那台数据库一样的电脑软件会出现奇招嘛？也就是说软件也是会输的。我记得国际象棋那个深蓝也输给过卡斯帕罗夫，然后那个更深的蓝赢了卡斯帕罗夫。还是赢在数据采集啊。

呵呵，这个应该难不倒你吧。

好，进入正题，既然你用了一个2D的数组，那么将帅碰面这个情况，转化到JAVA里就是以下的情况

1：将帅当前位置的列数相同

2：在该列上没有其他的旗子

你用了109的数组。假设你现在将的位置是（0,5），帅的位置是（10,5），并且在第5列（准确的说是第6列，因为编号是从0开始）上没有其他的旗子，那么将帅碰面的情况就发生了

你写的代码我不知道，大概的伪代码如下

boolean JSPM(int[][] board){

int col == 将get_col();

if(将get_col() == 帅get_col() && no_block(board, col)) // no_block用来检查该列上是否有其他的旗子

return true;

return false;

}

boolean no_block(int[][] board, int col){

for(int i=0; i<10; i++){

if(board[i][col]有旗子)

return false;

}

return true;

}

看不懂的话可以继续追问

“衔接”各类一般有三种方法，一种是通过在一个类中创建另一个类的对象调用（包含关系/变量关系）；还有在一种是继承（继承关系）；最后一种是通过参数方式。最终肯定是在主类中调用一个或几个类。

对于第一种包含关系，一个类中有很多地方可以创建对象：

成员变量，直接在类框架下面，如

class X {

      private Y instance = new Y ();

}

局部变量，在方法中，如

class X {

      public void method () {

              Y instance = new Y();

      }

}

--------------------------------------

对于第二种继承关系，则用 extends 来继承一个类，子类可以得到父类的全部 protected 和 public 的成员变量和方法。

class X extends Y {

      // Your code here

}

--------------------------------------

第三种参数方式，一般又有两种情况：

方法参数

public void method (Y arg) {}

public void method (Y[] args) {}

泛型参数

List<Y> list = new ArrayList<Y>();

Map<Y, Z> map = new HashMap<Y, Z>();

诸如此类。

import javautilArrayList;

import javautilCollections;

import javautilComparator;

import javautilList;

import javautilRandom;

import javautilStack;

public class T {

  private static final int[][] MOVES = new int[][] { { -2, 1 }, { -1, 2 },

      { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 } };

  private static final int SIZE = 8;

  private static final int BASE = SIZE + 4;

  private static int[][] board;

  private static NeighborComparator neighborComparator = new NeighborComparator();

  public static void main(String[] args) {

    board = new int[BASE][BASE];

    for (int r = 0; r < BASE; r++) {

      for (int c = 0; c < BASE; c++) {

        if (r < 2 || r > BASE - 3 || c < 2 || c > BASE - 3) {

          board[r][c] = -1;

        }

      }

    }

    int row = 2 + new Random()nextInt(SIZE);

    int col = 2 + new Random()nextInt(SIZE);

    solve(row, col);

  }

  private static void solve(int r, int c) {

    Stack<Cell> stack = new Stack<Cell>();

    int count = 1;

    Cell cell = new Cell(r, c, neighbors(r, c));

    stackpush(cell);

    board[r][c] = count++;

    while (!stackisEmpty()) {

      if (stacksize() == SIZE  SIZE) {

        break;

      }

      cell = stackpeek();

      if (cellnextNeighbor < cellneighborssize()) {

        int[] neighbor = cellneighborsget(cellnextNeighbor);

        r = neighbor[0];

        c = neighbor[1];

        board[r][c] = count++;

        stackpush(new Cell(r, c, neighbors(r, c)));

        cellnextNeighbor++;

      } else {

        stackpop();

        board[cellr][cellc] = 0;

        count--;

      }

    }

    if (stacksize() == SIZE  SIZE) {

      print();

    } else {

      Systemoutprintln("无解");

    }

  }

  private static class NeighborComparator implements Comparator<int[]> {

    public int compare(int[] a, int[] b) {

      return a[2] - b[2];

    }

  }

  private static List<int[]> neighbors(int r, int c) {

    List<int[]> neighbors = new ArrayList<>();

    for (int[] m : MOVES) {

      int x = m[0];

      int y = m[1];

      if (board[r + y][c + x] == 0) {

        neighborsadd(new int[] { r + y, c + x, countNeighbors(r + y, c + x) });

      }

    }

    Collectionssort(neighbors, neighborComparator);

    return neighbors;

  }

  private static int countNeighbors(int r, int c) {

    int num = 0;

    for (int[] m : MOVES) {

      if (board[r + m[1]][c + m[0]] == 0) {

        num++;

      }

    }

    return num;

  }

  private static void print() {

    for (int i = 2; i < boardlength - 2; i++) {

      for (int j = 2; j < board[i]length - 2; j++) {

        Systemoutprintf("%2d ", board[i][j]);

      }

      Systemoutprintln();

    }

    Systemoutprintln();

  }

  private static class Cell {

    int r;

    int c;

    List<int[]> neighbors;

    int nextNeighbor = 0;

    public Cell(int r, int c, List<int[]> neighbors) {

      thisr = r;

      thisc = c;

      thisneighbors = neighbors;

    }

  }

}

以上就是关于怎样用数据结构的栈和java语言实现骑士游历问题，即让一个国际象棋的马不重复的走完棋盘上的所有格子全部的内容，包括:怎样用数据结构的栈和java语言实现骑士游历问题，即让一个国际象棋的马不重复的走完棋盘上的所有格子、象棋对弈软件是如何编制出来的、关于java中国象棋 将帅碰面的问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！