puzzle8.java~85~

用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];
        }
      }
      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 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;
    }
    if (square[2][0] == 1) {
      md += 2;
    }
    else if (square[2][0] == 2) {
      md += 3;
    }
    else if (square[2][0] == 3) {
      md += 4;
    }
    else if (square[2][0] == 4) {
      md += 3;
    }
    else if (square[2][0] == 5) {
      md += 2;
    }
    else if (square[2][0] == 6) {
      md += 1;
    }
    else if (square[2][0] == 7) {
      md += 0;
    }
    else if (square[2][0] == 8) {
      md += 1;
    }
    if (square[2][1] == 1) {
      md += 3;
    }
    else if (square[2][1] == 2) {
      md += 2;
    }
    else if (square[2][1] == 3) {
      md += 3;
    }
    else if (square[2][1] == 4) {
      md += 2;
    }
    else if (square[2][1] == 5) {
      md += 1;
    }
    else if (square[2][1] == 6) {
      md += 0;
    }
    else if (square[2][1] == 7) {
      md += 1;
    }
    else if (square[2][1] == 8) {
      md += 2;
    }
    if (square[2][2] == 1) {
      md += 4;
    }
    else if (square[2][2] == 2) {
      md += 3;
    }
    else if (square[2][2] == 3) {
      md += 2;
    }
    else if (square[2][2] == 4) {
      md += 1;
    }
    else if (square[2][2] == 5) {
      md += 0;
    }
    else if (square[2][2] == 6) {
      md += 1;
    }
    else if (square[2][2] == 7) {
      md += 2;
    }
    else if (square[2][2] == 8) {
      md += 3;
    }

    return md;
  }

  int expand(int[][] square, int[][][] tempsquare) {
    int b = 0;
    int i, j, k, col = -1, row = -1;
    for (i = 0; i < 4; i++) {
      for (j = 0; j < 3; j++) {
        for (k = 0; k < 3; k++) {
          tempsquare[i][j][k] = square[j][k];
        }
      }
    }
    for (i = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        if (square[i][j] == 0) {
          row = i;
          col = j;
          break;
        }
      }
    }
    if (row == 0 && col == 0) {
      tempsquare[0][0][0] = tempsquare[0][0][1];
      tempsquare[0][0][1] = 0;
      tempsquare[1][0][0] = tempsquare[1][1][0];
      tempsquare[1][1][0] = 0;
      b = 2;
    }
    else if (row == 0 && col == 1) {
      tempsquare[0][0][1] = tempsquare[0][0][0];
      tempsquare[0][0][0] = 0;
      tempsquare[1][0][1] = tempsquare[1][1][1];
      tempsquare[1][1][1] = 0;
      tempsquare[2][0][1] = tempsquare[2][0][2];
      tempsquare[2][0][2] = 0;
      b = 3;
    }
    else if (row == 0 && col == 2) {
      tempsquare[0][0][2] = tempsquare[0][0][1];
      tempsquare[0][0][1] = 0;
      tempsquare[1][0][2] = tempsquare[1][1][2];
      tempsquare[1][1][2] = 0;
      b = 2;
    }
    else if (row == 1 && col == 0) {
      tempsquare[0][1][0] = tempsquare[0][0][0];
      tempsquare[0][0][0] = 0;
      tempsquare[1][1][0] = tempsquare[1][1][1];
      tempsquare[1][1][1] = 0;
      tempsquare[2][1][0] = tempsquare[2][2][0];
      tempsquare[2][2][0] = 0;
      b = 3;
    }
    else if (row == 1 && col == 1) {
      tempsquare[0][1][1] = tempsquare[0][1][0];
      tempsquare[0][1][0] = 0;
      tempsquare[1][1][1] = tempsquare[1][0][1];
      tempsquare[1][0][1] = 0;
      tempsquare[2][1][1] = tempsquare[2][1][2];
      tempsquare[2][1][2] = 0;
      tempsquare[3][1][1] = tempsquare[3][2][1];
      tempsquare[3][2][1] = 0;
      b = 4;
    }
    else if (row == 1 && col == 2) {
      tempsquare[0][1][2] = tempsquare[0][0][2];
      tempsquare[0][0][2] = 0;
      tempsquare[1][1][2] = tempsquare[1][1][1];
      tempsquare[1][1][1] = 0;
      tempsquare[2][1][2] = tempsquare[2][2][2];
      tempsquare[2][2][2] = 0;
      b = 3;
    }
    else if (row == 2 && col == 0) {
      tempsquare[0][2][0] = tempsquare[0][1][0];
      tempsquare[0][1][0] = 0;
      tempsquare[1][2][0] = tempsquare[1][2][1];
      tempsquare[1][2][1] = 0;
      b = 2;
    }
    else if (row == 2 && col == 1) {
      tempsquare[0][2][1] = tempsquare[0][2][0];
      tempsquare[0][2][0] = 0;
      tempsquare[1][2][1] = tempsquare[1][1][1];
      tempsquare[1][1][1] = 0;
      tempsquare[2][2][1] = tempsquare[2][2][2];
      tempsquare[2][2][2] = 0;
      b = 3;
    }
    else if (row == 2 && col == 2) {
      tempsquare[0][2][2] = tempsquare[0][2][1];
      tempsquare[0][2][1] = 0;
      tempsquare[1][2][2] = tempsquare[1][1][2];
      tempsquare[1][1][2] = 0;
      b = 2;
    }

    return b;
  }

  private void jbInit() throws Exception {
    this.getContentPane().setLayout(null);
    this.setTitle("puzzle game");
    addWindowListener(new WindowAdapter() {
      public void windowClosing(WindowEvent event) {
        System.exit(0);
      }
    });
    jLabel1.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel1.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel1.setBounds(new Rectangle(6, 3, 127, 104));
    jLabel6.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel6.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel9.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel9.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel8.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel8.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel7.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel7.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel4.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel4.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel5.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel5.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel2.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel2.setHorizontalAlignment(SwingConstants.CENTER);
    jLabel3.setBorder(BorderFactory.createRaisedBevelBorder());
    jLabel3.setHorizontalAlignment(SwingConstants.CENTER);
    begin.setBounds(new Rectangle(138, 338, 120, 53));
    begin.setText("next");
    begin.addActionListener(new java.awt.event.ActionListener() {
      public void actionPerformed(ActionEvent e) {
        position++;
        if (position < moves) {
          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]));
        }
      }
    });
    jLabel9.setBounds(new Rectangle(263, 204, 129, 96));
    jLabel8.setBounds(new Rectangle(133, 204, 129, 96));
    jLabel7.setBounds(new Rectangle(7, 204, 126, 96));
    jLabel6.setBounds(new Rectangle(263, 107, 129, 96));
    jLabel5.setBounds(new Rectangle(134, 107, 128, 97));
    jLabel4.setBounds(new Rectangle(6, 109, 128, 94));
    jLabel3.setBounds(new Rectangle(264, 0, 128, 106));
    this.getContentPane().add(jLabel2);
    this.getContentPane().add(jLabel3);
    this.getContentPane().add(jLabel4);
    this.getContentPane().add(jLabel1);
    this.getContentPane().add(jLabel5);
    this.getContentPane().add(jLabel8);
    this.getContentPane().add(jLabel6);
    this.getContentPane().add(jLabel7);
    this.getContentPane().add(jLabel9);
    this.getContentPane().add(begin);
    jLabel2.setBounds(new Rectangle(134, 1, 130, 106));
  }

  private void initialboard() {
    int[] placed = new int[9];
    int i = 0, j = 0, k;
    for (i = 0; i < 9; i++) {
      placed[i] = 0;
    }
    for (i = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        board[i][j] = 0;
      }
    }
    Random random = new Random(new Date().getTime());
    for (k = 0; k < 9; k++) {
      boolean found = false;
      int digit;
      do {
        digit = random.nextInt(9);
        found = placed[digit] == 0;
        if (found) {
          placed[digit] = 1;
        }
      }
      while (!found);
      do {
        i = random.nextInt(3);
        j = random.nextInt(3);
        found = board[i][j] == 0;
        if (found) {
          board[i][j] = digit;
        }
      }
      while (!found);
    }
  }
  long gettime(){
    return time;
  }
  JLabel jLabel1 = new JLabel();
  JLabel jLabel2 = new JLabel();
  JLabel jLabel3 = new JLabel();
  JLabel jLabel4 = new JLabel();
  JLabel jLabel5 = new JLabel();
  JLabel jLabel6 = new JLabel();
  JLabel jLabel7 = new JLabel();
  JLabel jLabel8 = new JLabel();
  JLabel jLabel9 = new JLabel();
  JButton begin = new JButton();
  TitledBorder titledBorder1 = new TitledBorder("puzzle game");
  int maxMoves = 100;
  int g = 0, position = 0;
  int moves = 0;
  long  time = 0;
  int[][] solutions = new int[maxMoves + 1][9];
  int[][] board = new int[3][3];
}