puzzlemh.java~30~

用A star

package mypuzzle;

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 class PuzzleMh
    extends Puzzle {
  public PuzzleMh() {
  }

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

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

  public 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;
      }
    }
    for(i=0;i<4;i++) f[i]=0;
    i=0;
    while(i < count) {
      b = index[new Random().nextInt(count)];
      if(f[b]==0){
        for (j = 0; j < 3; j++) {
          for (k = 0; k < 3; k++) {
            board[j][k] = tempsquare[i][j][k];
          }
        }
        i++ ;
        f[b]=i;
        if (!hasExpanded(board)) {
          break;
        }
      }
     /* else {
        System.out.print("find a expanded node");
      }
      */
    }
    /*
     for (j = 0; j < 3; j++) {
      for (k = 0; k < 3; k++) {
        board[j][k] = tempsquare[i][j][k];
      }
     }
     */
    return false;
  }

  boolean hasExpanded(int[][] board) {
    boolean expanded = false;
    try {
      Node node;
      int i = 0;
      node = (Node)nodeExpanded.get(i);
      while (node != null) {
        int k = 0;
        while (k < 9 && node.getElements(k / 3, k % 3) == board[k / 3][k % 3]) {
          k++;
        }
        if (k == 9) {
          return true;
        }
        i++;
        node=(Node)nodeExpanded.get(i);
      }
    }
    catch (ArrayIndexOutOfBoundsException e) {}
    return expanded ;
  }

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

  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 g = 0;
}