/* --------------------------------------------------------------------

Puzzle class

Copyright (c) 1996 by Christopher R. Waterson. All Rights Reserved.
Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and without
fee is hereby granted provided that this copyright notice
appears in all copies.

File:		Puzzle.java
Synopsis:	Representation for an eight puzzle
Author:		Christopher R. Waterson <waterson@eecs.umich.edu>
Created:	26 Jan 1996
Updated:	Christopher R. Waterson <waterson@eecs.umich.edu>
Last Modified:	22 Oct 1996

-------------------------------------------------------------------- */

package eightpuzzle;

import java.util.*;

/**
 * The representation for the eight puzzle. The solution is assumed to be:
 *
 * <PRE>
 * 1 2 3
 * 8   4
 * 7 6 5
 * </PRE>
 *
 */

public class Puzzle {
	/**
	 * The "blank" or empty space that gets slid around the puzzle
	 */

	public static final int BLANK = 0;

	/**
	 * The goal configuration
	 */

	static int[][] ms_tilesGoal = {
		{ 1, 8, 7 },
		{ 2, 0, 6 },
		{ 3, 4, 5 } };

	/**
	 * A 3x3 array that represents the eight-puzzle
	 */

	int[][] m_tiles;


	/**
	 * Create a new eight puzzle
	 */

	public
	Puzzle() {
		m_tiles = new int[3][3];

		// Set up the initial configuration
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				m_tiles[i][j] = ms_tilesGoal[i][j];
	}


	/**
	 * Creates a new eight puzzle from the specified integer array
	 * @param tiles An integer array of tile positions.
	 */

	public
	Puzzle(int[][] tiles) {
		m_tiles = new int[3][3];

		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				m_tiles[j][i] = tiles[j][i];
	}


	/**
	 * Creates a new eight puzzle from another puzzle
	 * @param p The puzzle from which to create this puzzle.
	 */

	public Puzzle(Puzzle p) {
		m_tiles = new int[3][3];

		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				m_tiles[j][i] = p.m_tiles[j][i];
	}


	/**
	 * Returns true when the puzzle is solved
	 * @return True if the puzzle is solved.
	 */

	public boolean
	isSolved() {
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				if (m_tiles[i][j] != ms_tilesGoal[i][j]) return false;

		return true;
	}


	/**
	 * Returns the location of the specified tile
	 * @param tile The tile for which to identify the location.
	 * @return A TileLocation object.
	 */

	public TileLocation
	getTileLocation(int tile) {
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				if (m_tiles[i][j] == tile) return new TileLocation(i, j);

		// Throw an exception!
		return new TileLocation(-1, -1);
	}



	/**
	 * Returns the location of a tile in the specified tile array
	 */

	public TileLocation
	getTileLocation(int tile, int[][] tiles) {
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				if (tiles[i][j] == tile) return new TileLocation(i, j);

		// Throw an exception!
		return new TileLocation(-1, -1);
	}


	/**
	 * Can the specified tile be moved?
	 */

	public boolean
	canMove(int tile) {
		TileLocation blankLoc = getTileLocation(0);
		TileLocation tileLoc = getTileLocation(tile);

		// Make sure that we really can swap them
		int dx = blankLoc.x - tileLoc.x;
		int dy = blankLoc.y - tileLoc.y;

		if (! (  (dx == 0 && (dy == 1 || dy == -1))
			  || (dy == 0 && (dx == 1 || dx == -1))))
			return false;

		return true;
	}


	/**
	 * Move the specified tile into the location where the blank is
	 */

	public synchronized void
	move(int tile) {
		if (canMove(tile)) {
			TileLocation blankLoc = getTileLocation(0);
			TileLocation tileLoc = getTileLocation(tile);

			/* Swap the two */
			m_tiles[blankLoc.x][blankLoc.y] = tile;
			m_tiles[tileLoc.x][tileLoc.y] = 0;
		}
	}


	/**
	 * Shuffle up the puzzle a bit
	 */

	public void
	shuffle(int howMuch) {
		Random random = new Random(System.currentTimeMillis());

		for (int i = 0; i < howMuch; ++i)
			move(random.nextInt() % 8 + 1);
	}


	/**
	 * Return the tile located at (i, j)
	 */

	public int
	tileAt(int i, int j) {
		return m_tiles[i][j];
	}


	/**
	 * Return the total manhattan distance of all tiles out of place
	 */

	public int
	totalManhattanDistance() {
		int total = 0;

		for (int i = 1; i <= 8; ++i) {
			TileLocation puzzleLoc = getTileLocation(i);
			TileLocation goalLoc = getTileLocation(i, ms_tilesGoal);

			int dx = puzzleLoc.x - goalLoc.x;
			int dy = puzzleLoc.y - goalLoc.y;

			if (dx < 0) dx = -dx;
			if (dy < 0) dy = -dy;

			total += dx + dy;
		}

		return total;
	}



	/**
	 * Print the 8-puzzle on the system console
	 */

	public void
	print() {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (m_tiles[i][j] > 0) {
					System.out.print(m_tiles[i][j] + " ");
				} else {
					System.out.print("  ");
				}
			}
			System.out.println();
		}
	}
}