Maximum Number Unique Move Knight Chess Board

Maximum Number Unique Move Knight Chess Board

This programming question is also very famous in financial companies to screening candidate in first round of interview. This question has been asked middle to senior level developer position where interviewer want to check candidate ability to write algorithm quickly and for below question they gave two hours time:

Question:

Please implement a program to determin the maximum number of unique moves a knight can make on a chess board. The chess board can be of any size rectangle and the knight move can of any size. For example, a chess piece that moves 2X5 on a board 8X6. Please utilize a thread pool to decrease the real time it take to solve the problem.

Program should take as arguments, the configuration of the board and knight, as well as the number of thread to launch.

Solution: There are many different logic and algorithm can be use to write this algorithm, although to keep thing simple I have got the desired output using two for loop. Next I will implement same program by using thread as asked by interviewer but for now this what I have:

• KnightUniqueMoves.java: Method findKnightMove takes two parameters which you could pass in main method and based on that program will create two dimensional array and find knight moves:

package com.knightmove;

import java.text.DecimalFormat;

public class KnightUniqueMoves {
	
	static int[][] chessBoard;
	static int moveCount = 0;

	private static void findKnightMove(int rowCount, int columnCount){
		
		chessBoard = new int[rowCount][columnCount];
		
		for (int i = 0; i < rowCount; i++) {
			
			for (int j = 0; j < columnCount; j++) {
				
				System.out.println("\nStart count: "+String.valueOf(moveCount+1));				
				int postionCount = 0;				
				
				// go down and right
				if (canMove(i + 2, j + 1, rowCount, columnCount)) {
					chessBoard[i + 2][j + 1] = ++moveCount;
					++postionCount;
				}
				// go right and down
				if (canMove(i + 1, j + 2, rowCount, columnCount)) {
					chessBoard[i + 1][j + 2] = ++moveCount;
					++postionCount;
				}
				// go right and up
				if (canMove(i - 1, j + 2, rowCount, columnCount)) {
					chessBoard[i -1][j + 2] = ++moveCount;
					++postionCount;
				}
				// go up and right
				if (canMove(i - 2, j + 1, rowCount, columnCount)) {
					chessBoard[i -2][j + 1] = ++moveCount;
					++postionCount;
				}
				// go up and left
				if (canMove(i - 2, j - 1, rowCount, columnCount)) {
					chessBoard[i - 2][j - 1] = ++moveCount;
					++postionCount;
				}
				// go left and up
				if (canMove(i - 1, j - 2, rowCount, columnCount)) {
					chessBoard[i - 1][j - 2] = ++moveCount;
					++postionCount;
				}
				// go left and down
				if (canMove(i + 1, j - 2, rowCount, columnCount)) {
					chessBoard[i + 1][j - 2] = ++moveCount;
					++postionCount;
				}
				// go down and left
				if (canMove(i + 2, j - 1, rowCount, columnCount)) {
					chessBoard[i + 2][j - 1] = ++moveCount;
					++postionCount;
				}
				
				System.out.println("Knight postion on chess board: ["+i+"]["+j+"]");
				System.out.println("Total move knight can do: "+String.valueOf(postionCount));				
				print();
				
			}
		}
	}
	
	private static boolean canMove(int row, int column, int rowCount, int columnCount) {		
		
		if (row >= 0 && column >= 0 && row < rowCount && column < columnCount) {
			return true;
		}
		return false;
	}
	
	private static void print() {
		
		DecimalFormat DecimalFormat = new DecimalFormat("00");
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard[0].length; j++) {
				System.out.print("	" + DecimalFormat.format(chessBoard[i][j]));
			}
			System.out.println();
		}		
		
	}
	
	public static void main(String[] args) {
		
		int row = 8;
		int column = 8;		
		findKnightMove(row, column);		
		System.out.println("\nTotal number of unique move by Knight on "+row+"X"+column+" chess board:--> "+moveCount);
		
	}
	
}

• Output: Total number of unique move knight can do on 8X8 chess board is: 336. I am not pasting full output because its so big, you can try in your workspace to see full output.

Reference:

• Creating and Populating Multi-Dimensional Arrays