骑士巡游问题程序源码.java

骑士巡游问题源码 控制台程序 可以直接运行 有需要的愿意分享

package MyLesson.HorseProblem;
/*
*注释BY-QIAOHG
*/
import java.util.Random;
import java.util.Vector;

public class HorseProblem3 {
  public static void main(String[] args) {
	/*
	*随机生成随机开始的根节点
	*/
    Random rnd = new Random();
    node root = new node(null, rnd.nextInt(8), rnd.nextInt(8));
	//开始深度优先搜索
    node leaf = depthFirstSearch(root);
	//输出结果
    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j++) {
        System.out.print( (leaf.Grid[i][j] + "    ").substring(0, 4));
      }
      System.out.println();
    }
  }

  public static node depthFirstSearch(node curNode) {
    if (curNode.depth==64) return curNode;//判断是否已经遍历了所有节点
    curNode.setSons();//找出当前节点的可能的所有子节点
    node[] sons = curNode.getSons();//获得所有子节点
    if (sons == null) return null;//子节点为空，本次深度优先搜索失败
    for (int i = 0; i < sons.length; i++) {
      //if (sons[i].depth==64) return sons[i];
      node n = depthFirstSearch(sons[i]);//继续深入搜索
      if (n != null) return n;
    }
    return null;
  }
}

class node {
  int depth = 0;//当前节点深度
  node father = null;//父节点
  node[] sons = null;//子节点
  int x, y;
  int[][] Grid = new int[8][8];//当前节点对应视图

  node(node father, int x, int y) {
    this.father = father;//记录父节点
    this.x = x;    this.y = y;
    if(father!=null){//此节点不是根节点
      this.depth = this.father.depth + 1;//此节点深度
	/*
	*从父节点创建当前节点视图
	*/
      for (int i = 0; i < father.Grid.length; i++)
        for (int j = 0; j < father.Grid[i].length; j++)
          this.Grid[i][j] = father.Grid[i][j];
    }else
      this.depth=1;//父节点深度为1
    this.Grid[this.x][this.y] = this.depth;//在当前节点视图中记录本节点深度
  }

  public void setSons() {
	/*
	*计算存在的子节点
	*/
    Vector v = new Vector();
	//如果没遍历过此节点就加入到V 中
    if (x + 2 < 8 && y + 1 < 8 && Grid[x + 2][y + 1] == 0) v.add(new node(this, x + 2, y + 1));
    if (x + 1 < 8 && y + 2 < 8 && Grid[x + 1][y + 2] == 0) v.add(new node(this, x + 1, y + 2));
    if (x > 0 && y > 1 && Grid[x - 1][y - 2] == 0) v.add(new node(this,  x - 1, y - 2));
    if (x > 1 && y > 0 && Grid[x - 2][y - 1] == 0) v.add(new node(this,  x - 2, y - 1));
    if (x > 0 && y + 2 < 8 && Grid[x - 1][y + 2] == 0) v.add(new node(this,  x - 1, y + 2));
    if (x > 1 && y + 1 < 8 && Grid[x - 2][y + 1] == 0) v.add(new node(this,  x - 2, y + 1));
    if (x + 2 < 8 && y > 0 && Grid[x + 2][y - 1] == 0) v.add(new node(this,  x + 2, y - 1));
    if (x + 1 < 8 && y > 1 && Grid[x + 1][y - 2] == 0) v.add(new node(this,  x + 1, y - 2));
    if (v.size() > 0) {
      this.sons = new node[v.size()];
      this.sons = (node[]) v.toArray(this.sons);
	//遍历子节点，按照其座具有的子节点数量从小向大排序
      for (int i = 0; i < sons.length; i++)
        for (int j = 0; j < sons.length - i - 1; j++)
          if (sons[j].getSonsCount() > sons[j + 1].getSonsCount()) {
            node tempSon = sons[j];
            sons[j] = sons[j + 1];
            sons[j + 1] = tempSon;
          }
    }

  }

  public node[] getSons() {
    return this.sons;
  }

  public int getSonsCount() {
  //计算当前节点的子节点的数量
    int skips = 0;
    if (x + 2 < 8 && y + 1 < 8 && Grid[x + 2][y + 1] == 0) skips++;
    if (x + 1 < 8 && y + 2 < 8 && Grid[x + 1][y + 2] == 0) skips++;
    if (x > 0 && y > 1 && Grid[x - 1][y - 2] == 0) skips++;
    if (x > 1 && y > 0 && Grid[x - 2][y - 1] == 0) skips++;
    if (x > 0 && y + 2 < 8 && Grid[x - 1][y + 2] == 0) skips++;
    if (x > 1 && y + 1 < 8 && Grid[x - 2][y + 1] == 0) skips++;
    if (x + 2 < 8 && y > 0 && Grid[x + 2][y - 1] == 0) skips++;
    if (x + 1 < 8 && y > 1 && Grid[x + 1][y - 2] == 0) skips++;
    return skips;
  }
}