/*
	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;
			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);
	}
	
	int DFSContour(char[][] solution, int fLimit, int m, int[][] board) {
		boolean equal, skip;
		char[] tempSolution = new char[9];	
		int b, count, fCost, i, j, k, l, n, newF, nextF = Infinity;
		int[][][] tempSquare = new int[4][3][3];

		fCost = g + heuristic(board);
		for (i = k = 0; i < 3; i++)
			for (j = 0; j < 3; j++)
				solution[m][k++] = (char) (board[i][j] + '0');
		m++;
		if (m == MaxMoves)
			return Infinity;
		if (fCost > fLimit) {
			flag = 0;
			return fCost;
		}
		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) {
			flag = 1;
			moves = m;
			return fCost;
		}
		b = expand(board, tempSquare);
		nodesExpanded += b;
		for (i = 0; i < b; i++) {
			skip = false;
			for (j = m - 1; !skip && j < m; j++) {
				for (k = l = 0; k < 3; k++)
					for (n = 0; n < 3; n++)
						tempSolution[l++] = (char) (tempSquare[i][k][n] + '0');
				equal = tempSolution[0] == solution[j][0];
				for (k = 1; equal && k < 9; k++)
					equal = tempSolution[k] == solution[j][k];
				if (equal)
					skip = true;
			}
			if (!skip) {
				newF = DFSContour(solution, fCost, m, tempSquare[i]);
				if (flag == 1)
					return newF;
				nextF = newF < nextF ? newF : nextF;
			}
		}
		g++;
		return nextF;
	}

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

	boolean solve(char[][] solution) {
		boolean found;
		int fCost, i, j, k, m = 0;
		
		fCost = DFSContour(solution, Infinity, 0, board);
		if (flag == 1)
			return true;
		else if (fCost == Infinity)
			return false;
		return false;
	}

	int getMoves() {
		return moves;
	}
}

class Puzzle8I implements Runnable {
	char[][] solution = null;
	int moves;
	PuzzleI puzzleI = null;

	public Puzzle8I () {
		solution = new char[PuzzleI.MaxMoves][9];
		do
			puzzleI = new PuzzleI();
		while (!puzzleI.solve(solution));
	}

	public void run() {
		Puzzle8IFrame puzzle8IFrame = new Puzzle8IFrame(solution[0]);
		
		moves = puzzleI.getMoves() - 1;
		System.out.println("moves = " + moves);
		for (int i = 1; i < moves + 1; i++) {
			while (!puzzle8IFrame.getNext())
				Thread.yield();
			puzzle8IFrame.setNext(false);
			puzzle8IFrame.draw(solution[i]);
		}
	}

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