puzzle.java~16~

用A star

package mypuzzle;

import javax.swing.*;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import javax.swing.border.TitledBorder;
import java.util.Date;
import java.util.Random;

/**
 * <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 abstract class Puzzle
    extends JFrame {
  public Puzzle() {
    try {
      jbInit();
    }
    catch (Exception ex) {
      ex.printStackTrace();
    }

  }

  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));
  }

  long gettime() {
    return time;
  }

  public void run() {
    long a = System.currentTimeMillis();
    do {
      initialboard();

      moves = solve();
    }
    while (moves == maxMoves);
    long b = System.currentTimeMillis();
    time = b - a;
    System.out.print("it cost:");
    System.out.print(time+"ms");
    finish=true;
    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());
  }

  public 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;
  }

  public abstract int solve();

  public 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);
    }
  }

  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 position = 0;
  int moves = 0;
  long time = 0;
  boolean finish=false;
  int[][] solutions = new int[maxMoves + 1][9];
  int[][] board = new int[3][3];

}