puzzle8.java

用A star

package mypuzzle;

import java.util.*;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.border.*;

/**
 * <p>Title: 8 puzzle </p>
 *
 * <p>Description: a solution of a*</p>
 *
 * <p>Copyright: Copyright (c) 2006</p>
 *
 * <p>Company: hitsz</p>
 *
 * @author yangyi
 * @version 1.0
 */
public class Puzzle8
    extends JFrame {
  public Puzzle8() {
    try {
      jbInit();
    }
    catch (Exception ex) {
      ex.printStackTrace();
    }
  }

  public static void main(String[] args) {
    Puzzle8 puzzle8 = new Puzzle8();
    puzzle8.setBounds(50, 50, 410, 450);
    puzzle8.setVisible(true);
    puzzle8.run();
  }

  private void run() {
    do {
      initialboard();
      moves = solve();
    }
    while (moves == maxMoves);
    jLabel1.setText(Integer.toString(solutions[position][0]));
    jLabel2.setText(Integer.toString(solutions[position][1]));
    jLabel3.setText(Integer.toString(solutions[position][2]));
    jLabel4.setText(Integer.toString(solutions[position][3]));
    jLabel5.setText(Integer.toString(solutions[position][4]));
    jLabel6.setText(Integer.toString(solutions[position][5]));
    jLabel7.setText(Integer.toString(solutions[position][6]));
    jLabel8.setText(Integer.toString(solutions[position][7]));
    jLabel9.setText(Integer.toString(solutions[position][8]));
    //super.paintAll(getGraphics());
  }

  private int solve() {
    int i, j, k, m = 0;
    boolean found = false;
    while (!found && m < maxMoves) {
      for (i = k = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
          solutions[m][k++] = board[i][j];
        }
      }
      System.out.println(board[0][0] + " " + board[0][1] + " " + board[0][2]);
      System.out.println(board[1][0] + " " + board[1][1] + " " + board[1][2]);
      System.out.println(board[2][0] + " " + board[2][1] + " " + board[2][2]);
      System.out.println();

      found = moves();
      g++;
      m++;
    }
    for (i = k = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        solutions[m][k++] = board[i][j];
      }
    }
    return m;
  }

  boolean moves() {
    int b = 0, i, j, k, count = 0, min;
    int[] f = new int[4], index = new int[4];
    int[][][] tempsquare = new int[4][3][3];
    if (board[0][0] == 1 && board[0][1] == 2 && board[0][2] == 3 &&
        board[1][0] == 8 && board[1][1] == 0 && board[1][2] == 4 &&
        board[2][0] == 7 && board[2][1] == 6 && board[2][2] == 5) {
      return true;
    }
    b = expand(board, tempsquare);
    for (i = 0; i < b; i++) {
      f[i] = g + heuristic(tempsquare[i]);
    }
    min = f[0];
    for (i = 1; i < b; i++) {
      if (f[i] < min) {
        min = f[i];
        count = i;
      }
    }
    i = count;
    /*
         for (i = count = 0; i < b; i++) {
      if (f[i] == min) {
        index[count++] = i;
      }
         }
         i = index[new Random().nextInt(count)];
     */
    for (j = 0; j < 3; j++) {
      for (k = 0; k < 3; k++) {
        board[j][k] = tempsquare[i][j][k];
      }
    }
    return false;
  }

  int heuristic(int[][] square) {
    return ManhattenDistance(square);
  }

  int outofSpace(int[][] square) {
    int i, j, oop = 0;
    int[][] goal = new int[3][3];
    goal[0][0] = 1;
    goal[0][1] = 2;
    goal[0][2] = 3;
    goal[1][0] = 8;
    goal[1][1] = 0;
    goal[1][2] = 4;
    goal[2][0] = 7;
    goal[2][1] = 6;
    goal[2][2] = 5;
    for (i = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        if (square[i][j] != goal[i][j]) {
          oop++;
        }
      }
    }
    return oop;
  }
  int DManhattenDistance(int[][] square){
    int md=ManhattenDistance(square);
    return 2*md ;
  }
  int ManhattenDistance(int[][] square) {
    int md = 0;
    if (square[0][0] == 1) {
      md += 0;
    }
    else if (square[0][0] == 2) {
      md += 1;
    }
    else if (square[0][0] == 3) {
      md += 2;
    }
    else if (square[0][0] == 4) {
      md += 3;
    }
    else if (square[0][0] == 5) {
      md += 4;
    }
    else if (square[0][0] == 6) {
      md += 3;
    }
    else if (square[0][0] == 7) {
      md += 2;
    }
    else if (square[0][0] == 8) {
      md += 1;
    }
    if (square[0][1] == 1) {
      md += 1;
    }
    else if (square[0][1] == 2) {
      md += 0;
    }
    else if (square[0][1] == 3) {
      md += 1;
    }
    else if (square[0][1] == 4) {
      md += 2;
    }
    else if (square[0][1] == 5) {
      md += 3;
    }
    else if (square[0][1] == 6) {
      md += 2;
    }
    else if (square[0][1] == 7) {
      md += 3;
    }
    else if (square[0][1] == 8) {
      md += 2;
    }
    if (square[0][2] == 1) {
      md += 2;
    }
    else if (square[0][2] == 2) {
      md += 1;
    }
    else if (square[0][2] == 3) {
      md += 0;
    }
    else if (square[0][2] == 4) {
      md += 1;
    }
    else if (square[0][2] == 5) {
      md += 2;
    }
    else if (square[0][2] == 6) {
      md += 3;
    }
    else if (square[0][2] == 7) {
      md += 4;
    }
    else if (square[0][2] == 8) {
      md += 3;
    }
    if (square[1][0] == 1) {
      md += 1;
    }
    else if (square[1][0] == 2) {
      md += 2;
    }
    else if (square[1][0] == 3) {
      md += 3;
    }
    else if (square[1][0] == 4) {
      md += 2;
    }
    else if (square[1][0] == 5) {
      md += 3;
    }
    else if (square[1][0] == 6) {
      md += 2;
    }
    else if (square[1][0] == 7) {
      md += 1;
    }
    else if (square[1][0] == 8) {
      md += 0;
    }
    if (square[1][1] == 1) {
      md += 2;
    }
    else if (square[1][1] == 2) {
      md += 1;
    }
    else if (square[1][1] == 3) {
      md += 2;
    }
    else if (square[1][1] == 4) {
      md += 1;
    }
    else if (square[1][1] == 5) {
      md += 2;
    }
    else if (square[1][1] == 6) {
      md += 1;
    }
    else if (square[1][1] == 7) {
      md += 2;
    }
    else if (square[1][1] == 8) {
      md += 1;
    }
    if (square[1][2] == 1) {
      md += 3;
    }
    else if (square[1][2] == 2) {
      md += 2;
    }
    else if (square[1][2] == 3) {
      md += 1;
    }
    else if (square[1][2] == 4) {
      md += 0;
    }
    else if (square[1][2] == 5) {
      md += 1;
    }
    else if (square[1][2] == 6) {
      md += 2;
    }
    else if (square[1][2] == 7) {
      md += 3;
    }
    else if (square[1][2] == 8) {
      md += 2;
    }