import java.util.*;

/**
 * Knight's Tour for CIS288
 * Scott Hurring - sh5 at njit dot edu
 */
public class Knight 
{
	// Board dimensions
	private int rows = 0;
	private int cols = 0;
	private int size = 0;
	
	// The chessboard
	private int [][] board;
	
	// Current move number and list of moves taken
	private int move = 0;
	private Stack moves = new Stack();

	// Possible modifications to current knight's position.
	private int[][] mods = { {-2,-1},{-2,1}, {1,-2},{1,2}, {2,1},{2,-1}, {1,-2},{-1,-2} }; 
	
	/**
	 * Constructor.
	 */
	public Knight(int rows, int cols)
	throws Exception
	{
		System.out.println("Knight's Tour rows="+rows+", cols="+cols);
		this.rows = rows;
		this.cols = cols;
		this.size = rows * cols;
	}
	
	/**
	 * Build a chessboard of dimension rows x cols.
	 */
	private void build_board(int rows, int cols)
	{
		this.board = new int[rows][cols];
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				this.board[row][col] = 0;
			}
		}
	}
	
	/**
	 * Solve the Knight's Tour from the (row,col) square.
	 */
	public boolean solve(int row, int col)
	{
		this.build_board(rows, cols);
		return this.next(row, col);
	}
	
	/**
	 * Recursively find the next move for the knight from (row,col).
	 */
	private boolean next(int row, int col)
	{
		this.move_to(row, col);

		// End the recursion if the board is filled.
		if (this.move >= this.size) {
			return true;
		}
		
		// Look at all possible moves from this (row,col)
		Stack legalmoves = this.legal_moves(row, col);
		//System.out.println("["+ this.move +"] next("+row+","+col+"): legal moves out of here = "+ legalmoves.size());
		while (!legalmoves.empty()) {
			int[] pair = this._unpack_pair((ArrayList)(legalmoves.pop()));
			//System.out.println("\t["+ this.move +"] try ("+ pair[0] +","+ pair[1] +")");
			if (this.next(pair[0], pair[1])) {
				return true;
			}
		}
		
		// No valid moves out of this square, backtrack	
		//System.out.println("\t["+ this.move +"] No valid move out of ("+ row +","+ col +")");
		this.backtrack();
		return false;
	}
	
	/**
	 * Return an array of legal (row,col) moves.
	 */
	private Stack legal_moves(int row, int col)
	{
		Stack legalmoves = new Stack();
		int newrow = 0;
		int newcol = 0;
		
		for (int i = 0; i < this.mods.length; i++) {
			newrow = row + this.mods[i][0];
			newcol = col + this.mods[i][1];

			// Is this potential move on the board?
			if ((newrow < 0) || (newrow >= this.rows) || 
			(newcol < 0) || (newcol >= this.cols) ) 
			{
				continue;
			}
			
			// Is this square available?
			if (this.board[newrow][newcol] == 0) {
				legalmoves.push(this._pack_pair(newrow, newcol));
			}
		}

		return legalmoves;
	}
	
	/**
	 * Move the knight to (row,col)
	 */
	private void move_to(int row, int col)
	{
		this.move++;
		//System.out.println("Move to ("+ row +","+ col +") on "+ this.move);
		this.board[row][col] = this.move;
		ArrayList pair = this._pack_pair(row,col);
		this.moves.push(pair);
	}
	
	/**
	 * Backtrack the knight to the previous square.
	 */
	private void backtrack()
	{
		this.move--;
		int[] pair = this._unpack_pair((ArrayList)(this.moves.pop()));
		//System.out.println("Bactrack to ("+ pair[0] +","+ pair[1] +")="+ this.board[pair[0]][pair[1]] +" on "+ this.move);
		this.board[pair[0]][pair[1]] = 0;
	}

	/**
	 * Pack int (row,col) primitives into an ArrayList of Integer objects.
	 */
	private ArrayList _pack_pair(int row, int col)
	{
		ArrayList packed_pair = new ArrayList();
		
		packed_pair.add(0, new Integer(row));
		packed_pair.add(1, new Integer(col));
		
		return packed_pair;
	}
	
	/**
	 * Un-pack a (row,col) pair into an array of int primitves.
	 */
	private int[] _unpack_pair(ArrayList packed_pair)
	{
		int[] pair = new int[2];
		
		pair[0] = ((Integer)(packed_pair.get(0))).intValue();
		pair[1] = ((Integer)(packed_pair.get(1))).intValue();
		
		return pair;
	}
	
	/**
	 * Print the state of the chessboard.
	 */
	public void print_board()
	{
		System.out.println("==> Board");
		for (int row = 0; row < this.rows; row++) {
			for (int col = 0; col < this.cols; col++) {
				System.out.print(this.board[row][col] +", ");
			}
			System.out.println("");
		}
	}
}