puzzle8i.java

用A star

/*
	Author:	James Pate Williams, Jr.

	Solution of 8-puzzle using IDA* search
*/

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

class Puzzle8IPanel extends JPanel {
	char[] s;
	int deltaX, deltaY;
	int x0, x1, y0, y1;
	
	public Puzzle8IPanel(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 Puzzle8IFrame extends JFrame implements Runnable {
	boolean next;
	int iHeight, iWidth;
	JButton jButton1 = new JButton();
	JPanel jPanel = new JPanel();
	BorderLayout borderLayout = new BorderLayout();
	Puzzle8IPanel puzzle8IPanel;
	
	// 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 Puzzle8IFrame(char[] solution) {
		String title = "Puzzle8I 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);
		puzzle8IPanel = new Puzzle8IPanel(iWidth, iHeight, solution);
		contentPane.add(puzzle8IPanel, 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) {
		puzzle8IPanel.setSolution(solution);
		puzzle8IPanel.paintComponent(getGraphics());
	}
}

class PuzzleI {
	int flag, g, moves, nodesExpanded;
	int[][] board;
	Date date;
	Random random;
	public static final int Infinity = 2000000000;
	public static final int MaxMoves = 100;

	public PuzzleI() {
		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 = moves = 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;