puzzle8.java.bak

用A star

/*
	Author:	James Pate Williams, Jr.

	Solution of 8-puzzle using A* search
*/

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

class Puzzle8Panel extends JPanel {
	char[] s;
	int deltaX, deltaY;
	int x0, x1, y0, y1;

	public Puzzle8Panel(int iWidth, int iHeight, char[] solution) {
		x0 = iWidth / 8;
		x1 = 7 * x0;
		y0 = iHeight / 8;
		y1 = 7 * y0;
		deltaX = (x1 - x0) / 3;
		deltaY = (y1 - y0) / 3;
		s = new char[9];
		s = solution;
	}

	public void sevenSegmentDisplay(Graphics g, char digit,
		int x, int y, int xUnit, int yUnit) {
		int xInc = xUnit / 10;
		int yInc = yUnit / 10;
		int xPoint1 = x + xInc;
		int yPoint1 = y + yInc;
		int xPoint2 = x + xUnit - xInc;
		int yPoint2 = yPoint1;
		int xPoint3 = xPoint1;
		int yPoint3 = y + yUnit / 2;
		int xPoint4 = xPoint2;
		int yPoint4 = yPoint3;
		int xPoint5 = xPoint3;
		int yPoint5 = y + yUnit - yInc;
		int xPoint6 = xPoint4;
		int yPoint6 = yPoint5;

		g.setColor(Color.white);
		switch (digit) {
			case '0':
				g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
				g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
				g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
				g.drawLine(xPoint5, yPoint5, xPoint1, yPoint1);
				break;
			case '1':
				g.drawLine(xPoint1, yPoint1, xPoint5, yPoint5);
				break;
			case '2':
				g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
				g.drawLine(xPoint2, yPoint2, xPoint4, yPoint4);
				g.drawLine(xPoint4, yPoint4, xPoint3, yPoint3);
				g.drawLine(xPoint3, yPoint3, xPoint5, yPoint5);
				g.drawLine(xPoint5, yPoint5, xPoint6, yPoint6);
				break;
			case '3':
				g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
				g.drawLine(xPoint2, yPoint2, xPoint4, yPoint4);
				g.drawLine(xPoint4, yPoint4, xPoint3, yPoint3);
				g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
				g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
				break;
			case '4':
				g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
				g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
				g.drawLine(xPoint4, yPoint4, xPoint2, yPoint2);
				g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
				break;
			case '5':
				g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
				g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
				g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
				g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
				g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
				break;
			case '6':
				g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
				g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
				g.drawLine(xPoint4, yPoint4, xPoint6, yPoint6);
				g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
				g.drawLine(xPoint5, yPoint5, xPoint3, yPoint3);
				break;
			case '7':
				g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
				g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
				break;
			case '8':
				g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
				g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
				g.drawLine(xPoint6, yPoint6, xPoint5, yPoint5);
				g.drawLine(xPoint5, yPoint5, xPoint1, yPoint1);
				g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
				break;
			case '9':
				g.drawLine(xPoint1, yPoint1, xPoint2, yPoint2);
				g.drawLine(xPoint2, yPoint2, xPoint6, yPoint6);
				g.drawLine(xPoint1, yPoint1, xPoint3, yPoint3);
				g.drawLine(xPoint3, yPoint3, xPoint4, yPoint4);
				break;
		}
	}

	public void paintComponent(Graphics g) {
		int i, j, x, y;
  		int xUnit = deltaY / 9;
  		int yUnit = deltaY / 15;

		super.paintComponent(g);
		y = y0;
		for (i = 0; i < 3; i++) {
			x = x0;
			for (j = 0; j < 3; j++) {
				g.setColor(Color.white);
				g.drawRect(x, y, deltaX, deltaY);
				g.setColor(Color.black);
				g.fillRect(x, y, deltaX, deltaY);
				sevenSegmentDisplay(g, s[3 * i + j], x, y, deltaX, deltaY);
				x += deltaX;
			}
			y += deltaY;
		}
	}

	public void setSolution(char[] solution) {
		s = new char[9];
		s = solution;
	}
}

class Puzzle8Frame extends JFrame implements Runnable {
	boolean next;
	int iHeight, iWidth;
	JButton jButton1 = new JButton();
	JPanel jPanel = new JPanel();
	BorderLayout borderLayout = new BorderLayout();
	Puzzle8Panel puzzle8Panel;

	// step 3 - percentage size the window
	void setDesktopSize(JFrame frame, int wPerc, int hPerc) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		iWidth = screen.width * wPerc / 100;
		iHeight = screen.height * hPerc / 100;
		frame.setSize(iWidth, iHeight);
	}

	// step 4 - center the window
	void centerOnScreen(JFrame frame) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		Dimension window = frame.getSize();
		int iCenterX = screen.width / 2;
		int iCenterY = screen.height / 2;
		frame.setLocation(iCenterX - window.width / 2, iCenterY - window.height / 2);
	}

	public Puzzle8Frame(char[] solution) {
		String title = "Puzzle8 by James Pate Williams, Jr. (c) 2001";
		next = false;
		jButton1.setToolTipText("Perform one iteration of algorithm");
		jButton1.setText("Next");
		jButton1.setVerticalAlignment(SwingConstants.BOTTOM);
		jButton1.addActionListener(new java.awt.event.ActionListener() {
			public void actionPerformed(ActionEvent e) {
				jButton1_actionPerformed(e);
			}
    		});
    		this.getContentPane().setLayout(borderLayout);
		setTitle(title);
		addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent event) {
				System.exit(0);
			}
		});
		setDesktopSize(this, 100, 100);
		centerOnScreen(this);
		Container contentPane = getContentPane();
		contentPane.add(jPanel, BorderLayout.SOUTH);
		jPanel.add(jButton1, BorderLayout.CENTER);
		puzzle8Panel = new Puzzle8Panel(iWidth, iHeight, solution);
		contentPane.add(puzzle8Panel, BorderLayout.CENTER);
		this.show();
		(new Thread(this)).run();
	}

	public boolean getNext() {
		return next;
	}

	public void setNext(boolean n) {
		next = n;
	}

	void jButton1_actionPerformed(ActionEvent e) {
		next = true;
	}

	public void run() {
		Thread.yield();
	}

	public void draw(char[] solution) {
		puzzle8Panel.setSolution(solution);
		puzzle8Panel.paintComponent(getGraphics());
	}
}

class Puzzle {
	int g, nodesExpanded;
	int[][] board;
	Date date;
	Random random;
	public static final int MaxMoves = 100;

	public Puzzle() {
		boolean found;
		int digit, i, j, k;
		int[] placed = new int[9];

		date = new Date();
		random = new Random(date.getTime());
		for (i = 0; i < 9; i++)
			placed[i] = 0;
		board = new int[3][3];
		g = nodesExpanded = 0;
		for (i = 0; i < 3; i++)
			for (j = 0; j < 3; j++)
				board[i][j] = 0;
		for (i = 0; i < 9; i++) {
			found = false;
			do {
				digit = random.nextInt(9);
				found = placed[digit] == 0;
				if (found)
					placed[digit] = 1;
			} while (!found);
			do {
				j = random.nextInt(3);
				k = random.nextInt(3);
				found = board[j][k] == 0;
				if (found)
					board[j][k] = digit;
			} while (!found);
		}
	}

	int getNodesExpanded() {
		return nodesExpanded;
	}

	int expand(int[][] square, int[][][] tempSquare) {
		int b = - 1, col = - 1, i, j, k, 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;
	}

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

	boolean move() {
		int b, count, i, j, k, 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]);
			for (j = 0; j < 3; j++)
				for (k = 0; k < 3; k++)
					board[j][k] = tempSquare[i][j][k];
		}
		// find the node of minimum f
		min = f[0];
		for (i = 1; i < b; i++)
			if (f[i] < min)
				min = f[i];
		for (count = i = 0; i < b; i++)
			if (f[i] == min)
				index[count++] = i;
		i = index[random.nextInt(count)];
		// increment the cost of the path thus far
		g++;
		nodesExpanded += b;
		for (j = 0; j < 3; j++)
			for (k = 0; k < 3; k++)
				board[j][k] = tempSquare[i][j][k];
		return false;
	}

	int outOfPlace(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) {
		// city block or Manhatten distance heuristic
		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 solve(char[][] solution) {
		boolean found;
		int i, j, k, m = 0;

		do {
			for (i = k = 0; i < 3; i++)
				for (j = 0; j < 3; j++)
					solution[m][k++] = (char) (board[i][j] + '0');
			found = move();
			m++;
		} while (!found && m < MaxMoves);
		for (i = k = 0; i < 3; i++)
			for (j = 0; j < 3; j++)
				solution[m][k++] = (char) (board[i][j] + '0');
		return m;
	}
}

public class Puzzle8 implements Runnable {
	char[][] solution = null;
	int moves;

	public Puzzle8 () {
		solution = new char[Puzzle.MaxMoves + 1][9];
		do {
			Puzzle puzzle = new Puzzle();
			moves = puzzle.solve(solution);
		} while (moves == Puzzle.MaxMoves);
	}

	public void run() {
		Puzzle8Frame puzzle8Frame = new Puzzle8Frame(solution[0]);

		System.out.println("moves = " + moves);
		for (int i = 0; i < moves; i++) {
			while (!puzzle8Frame.getNext())
				Thread.yield();
			puzzle8Frame.setNext(false);
			puzzle8Frame.draw(solution[i]);
		}
		puzzle8Frame.draw(solution[moves]);
	}

	public static void main(String[] arg) {
		(new Puzzle8()).run();
	}
}