/** Puzzle.java -- Does most of the work to find a solution to the Knight's
 *  tour problem.  Start a knight at one point (say the upper left corner)
 *  and see how to move the knight so that it visits all 64 squares exactly
 *  once.
 *  The numbers inside the board indicate the sequence of visits 1-64.
 *  We keep track of current as well as proposed position of the knight
 *  while finding solutions.
 */
public class Puzzle
{
  private int size;
  private int [][] board;
  private int visit;
  private int row;
  private int col;
  private int newRow;
  private int newCol;
  private boolean done;

  // By default, we'll start the knight at the top left (0,0) corner.
  public Puzzle(int n)
  {
    size = n;
    board = new int [size][size];
    clearBoard();
    board[0][0] = 1;
    visit = 1;
    row = 0;
    col = 0;
  }

  // This constructor is for the situation where we want to start
  // at some other arbitrary position.
  public Puzzle(int n, int i, int j)
  {
    size = n;
    board = new int [size][size];
    clearBoard();
    board[i][j] = 1;
    visit = 1;
    row = i;
    col = j;
  }

  public void clearBoard()
  {
    for (int i = 0; i < size; ++i)
      for (int j = 0; j < size; ++j)
        board[i][j] = 0;
  }

  public void solve()
  {
    System.out.println("solve() starting with visit = " + visit);
    int direction;

    if (visit == size*size)
      done = true;
    else
    {
      done = false;
      direction = 0;

      // From the current board position, find the next place
      // where the knight can go.  Note that no matter how big
      // the board is, there are always 8 directions to go.
      while (direction < 8 && ! done)
      {
        if (beenThere(direction))
          ++direction;
        else
        {
          board[newRow][newCol] = ++visit;

	  System.out.println(this);

          row = newRow;
	  col = newCol;
          solve();

	  // If we didn't find solution, backtrack:  take off the
	  // most recent knight placement and try it again.
	  // Also need to remember where we were!
          if (! done)
          {
	    clearVisit(visit);
	    --visit;
	    setPosition(visit);
	    //board[newRow][newCol] = 0;
	    //System.out.println("clearing [" + newRow + "][" + newCol + "]");
	    ++direction;
	  }
	}
      }
    }
  }

  /* return true if that new position is off the board, or
   * its board value is NOT zero.
   */
  public boolean beenThere(int direction)
  {
    findNewPosition(direction);
    boolean returnVal = newRow < 0 || newRow > (size - 1) || 
	                newCol < 0 || newCol > (size - 1) ||
	                board[newRow][newCol] != 0;
    System.out.println("visit = " + visit + " @ [" + row + "][" + col + 
		       "], dir = " + direction +
		       ", been there returns " + returnVal);
    return returnVal;
  }


  /** The 8 possible new positions for the knight are like going
   *  around the clock.
   */
  public void findNewPosition(int direction)
  {
    switch(direction)
    {
      case 0 : newRow = row - 2; newCol = col + 1; break;
      case 1 : newRow = row - 1; newCol = col + 2; break;
      case 2 : newRow = row + 1; newCol = col + 2; break;
      case 3 : newRow = row + 2; newCol = col + 1; break;
      case 4 : newRow = row + 2; newCol = col - 1; break;
      case 5 : newRow = row + 1; newCol = col - 2; break;
      case 6 : newRow = row - 1; newCol = col - 2; break;
      case 7 : newRow = row - 2; newCol = col - 1; break;
    }
  }

  // setPositon - Given a visit number, set row and col to that place.
  public void setPosition(int v)
  {
    for (int i = 0; i < size; ++i)
      for (int j = 0; j < size; ++j)
        if (board[i][j] == v)
	{
          row = i;
	  col = j;
        }
  }

  // clearVisit -- When we backtrack, we need to erase the most recently
  // placed knight.
  public void clearVisit(int v)
  {
    for (int i = 0; i < size; ++i)
      for (int j = 0; j < size; ++j)
        if (board[i][j] == v)
	{
	  System.out.println("clearing [" + row + "][" + col + "]");
	  board[i][j] = 0;
        }
  }

  /** Create a string rep'n of the board, including
   * leading spaces if a number is less than 10.
   */
  public String toString()
  {
    String build = "";
    for (int i = 0; i < size; ++i)
    {
      for (int j = 0; j < size; ++j)
      {
	if (board[i][j] < 10)
          build += " ";
     	build += board[i][j] + " ";
      }
      build += "\n";
    }
    return build;
  }
}