// Ex 7.22 Knight's Tour
// To see if a knight can move to each space
// on a chess board hitting each space only once

import java.util.Arrays;

public class KnightsTour2 {

	//Initialize an 8x8 array to represent the chessboard
		public static int[][] chessBoard = new int[8][8];


		public static void main(String[] args) {


			int[][] accessibility = { {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} };

			int[] moveValues = {10,10,10,10,10,10,10,10};


			int currentRow = 0; //Represents the row our knight is on
			int currentCol = 0; //                column

			int[] horizontal = { 2,1,-1,-2,-2,-1,1,2 }; //Moves list that operates on the columns
			int[] vertical = { -1,-2,-2,-1,1,2,2,1 };   //                                rows

			chessBoard[currentRow][currentCol] = 1; // Set starting position to 1


			//Iterates as far as 64 to cover every possible square
			for( int counter = 2; counter <= 64; counter++) {


				//Iterates through the 8 possible moves a knight can make
				for ( int i = 0; i < 8; i++ ) {

					currentCol += horizontal[i];
					currentRow += vertical[i];



					//Checks if move is valid
					//If it is valid it finds the value of the target location and stores it in
					//moveValues array

					try{

						if ( chessBoard[currentRow][currentCol] == 0) {


							moveValues[i] = accessibility[currentRow][currentCol];



						}else {
							moveValues[i] = 10;

							//lower the number of possible jumps from the current location
							accessibility[currentRow][currentCol] -= 1;
						}

					}
					catch ( ArrayIndexOutOfBoundsException e ) {

						moveValues[i] = 10;
					}


					currentCol -= horizontal[i];
					currentRow -= vertical[i];


				}//end of i controlled for statement


				//Uses the lowest valued move as our movenumber,then applies that move to the knight
				int moveNumber = getIndexOfLowest( moveValues );

				//System.out.printf("%d", moveNumber);
				try {
					currentCol += horizontal[ moveNumber ];
					currentRow += vertical[ moveNumber ];

					chessBoard[currentRow][currentCol] = counter;
				}
				catch ( ArrayIndexOutOfBoundsException e) {
					System.out.println("No moves remaining!");
				}




				//fill the moveValues array with 10's before next iteration
				Arrays.fill( moveValues, 10);


                                //puts the value of counter on the knight's current position
                                chessBoard[currentRow][currentCol] = counter;



			}//end of counter controlled for statement


			System.out.printf("Covered %d squares using this tour!\n",getNumberOfMoves());


			//Displays chessboard with move taken on each square
			for ( int[] rows : chessBoard ) {
				for ( int column : rows) {
					System.out.printf("%2d ",column);
				}
				System.out.println();
			}
		}



		//Method returns the number of spaces that have been filled by the knight
		//by finding the highest value in the array
		public static int getNumberOfMoves() {

			int moves = chessBoard[0][0];

			for ( int[] rows : chessBoard ) {
				for( int testsquare : rows ) {

					if ( testsquare > moves ) {
						moves = testsquare;
					}
				}
			}

			return moves;
		}


		public static int getIndexOfLowest ( int[] arrayValues ) {

			int[] arrayValuesCopy = new int[ arrayValues.length ];

			System.arraycopy( arrayValues, 0, arrayValuesCopy, 0, arrayValues.length);



			Arrays.sort( arrayValuesCopy );

			int lowest = arrayValuesCopy[0];

			System.out.printf("the value of lowest is %d\n", lowest);


			int location = Arrays.binarySearch( arrayValues, lowest );

			System.out.printf("the value of location is %d\n", location);

			return location;

		}







	}