/*
 * Created on Mar 30, 2004
 *  
 */
package eightPuzzle;

import java.util.Iterator;

/**
 * @author kgajos
 * 
 * The guts of the 8-puzzle solver
 */
public class EightPuzzle {

  protected static final int NULL_HEURISTIC = 0;
  protected static final int MISPLACED_TILES_HEURISTIC = 1;
  protected static final int DISTANCES_HEURISTIC = 2;
  protected static final int CUSTOM_HEURISTIC = 3;

  // keeps track of what heuristic to use
  protected int currentHeuristic = NULL_HEURISTIC;

  // a board representing the goal state -- you may find it
  // convenient when computing heuristics or when you need
  // to check if you have reached the goal
  public static final Board goalState =
    new Board(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 });

  // it should take only two moves to solve this initial configuration
  // -- you may find it (and other states like it) convenient in early
  // stages of your work
  public static final Board easyStartState =
    new Board(new int[] { 1, 4, 2, 3, 0, 5, 6, 7, 8 });

  // counter for the number of nodes expanded during search
  protected int searchCount = 0;

  /**
   * Creates a new instance of the Eight Puzzle solver
   */
  public EightPuzzle() {
  }

  /**
   * The A* search method
   * 
   * @param state
   *                    the initial state of the board
   * @return the final board
   */
  public Board search(Board startState) {
    // TODO fill in the search code

    // keep in mind that the Board class has getCostEstimate()
    // and setCostEstimate() methods -- you should use them
    // to update the value of the f() function for any 
    // board configuration; the OpenList class uses the value
    // returned by getCostEstimate() to order the nodes

    // also note that each board knows its pedigree, i.e.  you can ask
    // it for the sequence of actions that resulted in it beging
    // created starting with the start state





    // return null if no solution was found
    return null;
  }

  /**
   * Calculates the cost estimate for a particular board configuration by
   * adding the current cost of this board configuration and the expected
   * distance from the goal
   * 
   * @param board
   *                    the board to be evaluated
   * @return the total cost estimate
   */
  protected int getCostEstimate(Board board) {
    int hValue = 0;
    switch (currentHeuristic) {
    case NULL_HEURISTIC :
      hValue = nullHeuristic(board);
      break;
    case MISPLACED_TILES_HEURISTIC :
      hValue = misplacedTilesHeuristic(board);
      break;
    case DISTANCES_HEURISTIC :
      hValue = distancesHeuristic(board);
      break;
    case CUSTOM_HEURISTIC :
      hValue = customHeuristic(board);
      break;
    default :
      System.err.println("You specified an unrecognized heuristic!");
    }

    return board.getPathLength() + hValue;
  }

  /**
   * null heiristic -- generously filled in for you;)
   * 
   * @param board
   *                    the board to be evaluated
   * @return an estimate of the distance from the goal state
   */
  protected int nullHeuristic(Board board) {
    return 0;
  }

  /**
   * the number of misplaced tiles
   * 
   * @param board
   *                    the board to be evaluated
   * @return an estimate of the distance from the goal state
   */
  protected int misplacedTilesHeuristic(Board board) {
    // TODO your code here
    return 0;
  }

  /**
   * the sum of the distances of the tiles from their goal position
   * 
   * @param board
   *                    the board to be evaluated
   * @return an estimate of the distance from the goal state
   */
  protected int distancesHeuristic(Board board) {
    // TODO your code here
    return 0;
  }

  /**
   * Go wild -- you estimate of the distance from the goal
   * 
   * @param board
   *                    the board to be evaluated
   * @return an estimate of the distance from the goal state
   */
  protected int customHeuristic(Board board) {
    // TODO your code here
    return 0;
  }

  /**
   * @return Returns the currentHeuristic.
   */
  protected int getCurrentHeuristic() {
    return currentHeuristic;
  }

  /**
   * Specify the current heuristic
   * 
   * @param currentHeuristic
   *                    The currentHeuristic to set.
   */
  protected void setCurrentHeuristic(int currentHeuristic) {
    this.currentHeuristic = currentHeuristic;
  }

	
	
  public static void main(String[] args) {
    // you will need to modify this method to conduct the experiments with a 100 different boards
    // but this should be helpful to get started
		
    EightPuzzle puzzle = new EightPuzzle();
    // specify heuristic to use
    puzzle.setCurrentHeuristic(NULL_HEURISTIC);
    // specify initial state and start the search
    Board res = puzzle.search(easyStartState);
    // report the result
    System.out.println("best soln: " + res.getPathFromStartNode());
  }

}