import java.util.ArrayList;
import java.util.Random;

/**
 * Pedram Namiranian Jan 31, 2016 Period 4 ~1 hours 0 minutes This lab was
 * pretty enjoyable except for the fact that for the longest time my code was
 * not able to have the night move two to the left and one down, it would
 * usually get stuck at 16 steps in the top right corner. I spent about 30
 * minutes trying to debug it, I ran through my code multiple times with a sheet
 * of paper and a pencil and nothing seemed to work. Eventually I was tired so I
 * deleted my "moves" array and I retyped it, and my code works now and I have
 * no idea what was going on.
 */

public class P4_Namiranian_Pedram_KnightsTour2 {
	static int row = 0;
	static int colum = 0;
	static int[][] access = { { 2, 3, 4, 4, 4, 4, 3, 2 }, { 3, 4, 6, 6, 6, 6, 4, 3 }, { 4, 6, 8, 8, 8, 8, 6, 4 },
			{ 4, 6, 8, 8, 8, 8, 6, 4 }, { 4, 6, 8, 8, 8, 8, 6, 4 }, { 4, 6, 8, 8, 8, 8, 6, 4 },
			{ 3, 4, 6, 6, 6, 6, 4, 3 }, { 2, 3, 4, 4, 4, 4, 3, 2 } };
	static int[][] board = new int[8][8];
	static int[][] moves = { { 2, 1 }, { -2, 1 }, { 2, -1 }, { -2, -1 }, { 1, 2 }, { -1, 2 }, { 1, -2 }, { -1, -2 } };
	static ArrayList<Integer> possible = new ArrayList<Integer>();

	public static void main(String[] args) {
		int numSteps = 0;
		numSteps++;
		board[0][0] = numSteps;
		while (canMove()) {
			move();
			numSteps++;
			board[row][colum] = numSteps;
		}
		System.out.println("    1   2   3   4   5   6   7   8");
		for (int i = 0; i < 8; i++) {
			System.out.printf("%-4s", i);
			for (int j = 0; j < 8; j++) {
				System.out.printf("%-4s", board[i][j]);
			}
			System.out.println();
		}
		System.out.println();
		System.out.println(numSteps + " squares were visited");
	}

	private static void move() {
		int minIndex = 0;
		Random rand = new Random();
		int currentPos = 0;
		for (int i = 1; i < possible.size(); i++) {
			currentPos = possible.get(i);
			if (access[row + moves[currentPos][0]][colum
					+ moves[currentPos][1]] < access[row + moves[possible.get(minIndex)][0]][colum
							+ moves[possible.get(minIndex)][1]]) {
				minIndex = i;
			} else if (access[row + moves[currentPos][0]][colum
					+ moves[currentPos][1]] == access[row + moves[possible.get(minIndex)][0]][colum
							+ moves[possible.get(minIndex)][1]]
					&& !rand.nextBoolean()) {
				minIndex = i;
			} else {
				;
			}
		}
		int temp = 0;
		for (int j = 0; j < possible.size(); j++) {
			temp = access[row + moves[possible.get(j)][0]][colum + moves[possible.get(j)][1]];
			access[row + moves[possible.get(j)][0]][colum + moves[possible.get(j)][1]] = temp - 1;
		}
		row += moves[possible.get(minIndex)][0];
		colum += moves[possible.get(minIndex)][1];
	}

	private static boolean canMove() {
		possible.clear();
		for (int i = 0; i < 8; i++) {
			if (moves[i][0] + row < 8 && moves[i][0] + row >= 0) {
				if (moves[i][1] + colum < 8 && moves[i][1] + colum >= 0) {
					if (board[moves[i][0] + row][moves[i][1] + colum] == 0) {
						possible.add(i);
					}
				}
			}
		}
		if (possible.size() > 0) {
			return true;
		}
		return false;
	}
}