package edu.compsci;

import cs1.android.*;

// Implementation of the Knight Tour search algorithm
// for nxn board -- with backtracking and recursion.

public class KnightTourApp extends AndroidApp
{
	// coordinates for the center of the upper-left corner of 
	// the board; all drawing is done with respect to this center
	final int BOARD_ULX = 40;
	final int BOARD_ULY = 100;

	// the dimension of the image used for the knight piece
	final int KNIGHT_SIZE = 40;

	// draws a checker board of the given rows and columns
	void drawCheckerBoard( int rows, int cols )
	{
		canvas.setBackground("brown");
		for (int r = 0; r < rows; r = r + 1)
		{
			for (int c = 0; c < cols; c = c + 1)
			{
				drawSquare(r, c);
			}
		}
	}

	// draws a black/white square given its 2D board coordinates *(r, c)*
	// which are converted first to *(x, y)* canvas/drawing coordinates
	void drawSquare(int r, int c)
	{
		// convert 2D board coordinates to canvas/drawing coordinates
		double x = c * KNIGHT_SIZE + BOARD_ULX;
		double y = r * KNIGHT_SIZE + BOARD_ULY;

		// determine cell/square color based on its 2D board coordinates
		String color = pickColor(r, c);

		canvas.drawSquare(x, y, KNIGHT_SIZE, color);
	}


	// returns the color (black or white) for the square at (row, col)
	String pickColor(int row, int col)
	{
		if ((row+col)%2 == 0)
		{
			return "black";
		}   
		else
		{
			return "white";
		}
	}


	// draws a knight piece given its 2D board coordinates *(r, c)*
	// which are converted first to *(x, y)* canvas/drawing coordinates
	void drawKnight(int row, int col)
	{
		double x = col * KNIGHT_SIZE + BOARD_ULX;
		double y = row * KNIGHT_SIZE + BOARD_ULY;
		canvas.drawImage(x, y, "knight.jpg");

		canvas.sleep(1);
	}

	// determines if the given move is valid with respect ot the board
	boolean isValid( int[][] board, int row, int col )
	{
		int numRows = board.length;
		int numCols = board[0].length;

		if ( row >= 0 && row < numRows && col >= 0 && col < numCols)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	// recursive method that determines if a knight tour exists starting at the 
	// given board cell *(curRow, curCol); as before, it tries all possible 8
	// surrounding spots, but does not pick the first available spot and instead
	// calls itself for each new spot, so that its 8 neighbors can be explored
	//
	boolean findNextMove(int[][] board, int curRow, int curCol)
	{
		// the goal is to step on all squares (for 8x8 board, 64 steps)
		int target = board.length*board[0].length;  // rows x cols
		int step = board[curRow][curCol];           // the index of current move

		if (step == target)   // did we make exactly "row x col" moves
		{
			return true;
		}

		// horizontal and vertical displacement based on current location
		int[] colShift = {+1, +2, +2, +1, -1, -2, -2, -1};
		int[] rowShift = {-2, -1, +1, +2, +2, +1, -1, -2};

		// explore all possible 8 moves for the knight
		for (int i = 0; i < 8; i = i + 1)
		{
			int newRow = curRow + rowShift[i];
			int newCol = curCol + colShift[i];

			// check if next possible spot is within the board AND vacant
			if (isValid(board, newRow, newCol) == true && board[newRow][newCol] == 0)
			{
				board[newRow][newCol] = step + 1;   // mark current cell with next move index
				drawKnight(newRow, newCol);         // place the knight in the current cell

				// try the next move step by going to *(newRow, newCol)*
				boolean result = findNextMove(board, newRow, newCol);
				if (result == true)
				{
					return true;   // *(newRow, newCol)* reported success, so we do as well
				}

				// if a dead end reached by starting at *(newRow, newCol)*
				// unmark and prepare to try the next option
				board[newRow][newCol] = 0;    // unmark cell
				drawSquare(newRow, newCol);   // undraw the knight, cover with square
			}
		}

		return false;
	}

	// uses the recursive version of *findNextMove* to find a knight tour on a 2D board
	// starting at the square with coordinates (startRow, startCol)
	//
	void knightTour(int rows, int cols)
	{
		// set up the board and initial screen
		int[][] board = new int[rows][cols];
		drawCheckerBoard(rows, cols);
		canvas.drawText(canvas.getWidth()/2, canvas.getHeight()/8, "Click on a square to start!", 22, "white");

		/*
		 * New code for Android App
		 */
		// wait for user to select a starting point
		int startRow, startCol;
		do {
			Touch touch = canvas.waitForTouch();
			startRow = (touch.getY() - BOARD_ULY + KNIGHT_SIZE/2) / KNIGHT_SIZE;
			startCol = (touch.getX() - BOARD_ULX + KNIGHT_SIZE/2) / KNIGHT_SIZE;
		}
		while(isValid(board, startRow, startCol) == false);
		/*
		 * End New code for Android App
		 */

		canvas.clear();
		drawCheckerBoard(rows, cols);
		canvas.drawText(canvas.getWidth()/2, canvas.getHeight()/8, "The knight is searching...", 22, "white");

		int step = 1;
		board[startRow][startCol] = step;        // mark starting spot
		drawKnight(startRow, startCol);          // draw knight in starting spot

		// call the method *findNextMove* with the starting square *(startRow, startCol)*
		// and wait for the answer; *findNextMove* will search all possible paths
		boolean tourFound = findNextMove(board, startRow, startCol);
		if (tourFound == true) {
			canvas.drawText(canvas.getWidth()/2, 7*canvas.getHeight()/8, "The knight completed the tour!", 22, "white");
		}
		else {
			canvas.drawText(canvas.getWidth()/2, 7*canvas.getHeight()/8, "No tour is possible!", 22, "white");
		}
	}


	// the main method that starts the app
	public void run()
	{
		// 7x7 board
		knightTour(7, 7);
	}
}