node.java

八数码拼图程序源码,可以实现初始8个数码顺序到目标8个数码顺序的自动拼图

package com.will.eightnums;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author Will Wang
 * @version 1.0
 */

class Node {
  byte nodeson[][] = new byte[3][3]; //记录1~8及空格,为方便从已开始
  Node pre; //前一个节点
  byte x, y; //空格位所在位置,不再从数组中判断空格位置，加快搜索速度
  byte flag; //0未移动，1向左，2向上、3向右、4向下
  int f;//A*算法中用于代价评估
  Node() {

  }

  Node(byte n[][]) {
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        this.nodeson[i][j] = n[i][j];
        if (n[i][j] == 0) {
          this.x = (byte) i;
          this.y = (byte) j;
        }
      }
    }
    flag = 0;
  }

  public boolean equals(Node n) {
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (this.nodeson[i][j] != n.nodeson[i][j]) {
          return false;
        }
      }
    }
    return true;
  }

  public String toString() {
    char c[] = new char[9];
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        c[j + i * 3] = (char) (this.nodeson[i][j] + '0');
      }
    }
    return new String(c);
  }

  public void leftCopy(Node source) {
    for (int i = 0; i < 3; i++) {
    System.arraycopy(source.nodeson[i],0,nodeson[i],0,3);
    }
    this.nodeson[source.x][source.y] = nodeson[source.x][source.y - 1];
    this.nodeson[source.x][source.y - 1] = 0;
    this.x = source.x;
    this.y = (byte) (source.y - 1);
    this.flag = 1;
    this.pre = source;
  }

  public void rightCopy(Node source) {
    for (int i = 0; i < 3; i++) {
      System.arraycopy(source.nodeson[i],0,nodeson[i],0,3);
    }
    this.nodeson[source.x][source.y] = nodeson[source.x][source.y + 1];
    this.nodeson[source.x][source.y + 1] = 0;
    this.x = source.x;
    this.y = (byte) (source.y + 1);
    this.flag = 3;
    this.pre = source;
  }

  public void upCopy(Node source) {
    for (int i = 0; i < 3; i++) {
      System.arraycopy(source.nodeson[i],0,nodeson[i],0,3);
    }
    this.nodeson[source.x][source.y] = nodeson[source.x - 1][source.y];
    this.nodeson[source.x - 1][source.y] = 0;
    this.x = (byte) (source.x - 1);
    this.y = source.y;
    this.flag = 2;
    this.pre = source;
  }

  public void downCopy(Node source) {
    for (int i = 0; i < 3; i++) {
      System.arraycopy(source.nodeson[i],0,nodeson[i],0,3);
    }
    this.nodeson[source.x][source.y] = nodeson[source.x + 1][source.y];
    this.nodeson[source.x + 1][source.y] = 0;
    this.x = (byte) (source.x + 1);
    this.y = source.y;
    this.flag = 4;

    this.pre = source;
  }

  public int h1(Node n) { ///比较2个节点同一位置不同数码的个数
    int num = 0;
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (this.nodeson[i][j] != n.nodeson[i][j]) {
          num++;
        }
      }
    }
    return num;
  }
  public void setf(Node n) { ///设置当前节点到某个节点的f估计值
    if(pre==null)
      f=10*h1(n)+1;
    else
      f=pre.getf()- 10*pre.h1(n)+10*h1(n)+1;
  }

  public int getf(){
    return f;
  }
  public int getParity(){//判断节点的奇偶性,返回值0偶数，1奇数
    int num=0,temp=0;
    for(int i=0;i<3;i++){
      for(int j=0;j<3;j++){
        if(nodeson[i][j]!=0){
   tp:       for(int m=0;m<=i;m++){
            for (int n = 0; n < 3; n++) {
              if(i==m&&j==n) break tp;
              if (nodeson[m][n]!=0&&nodeson[i][j]>nodeson[m][n]) {
                num++;
              }
            }
          }
        }
      }
    }

    return num%2;
  }

}