CNT4714-Programming Assignment 3 Sneaky Knights Solved

You will be given a list of coordinate strings for knights on an arbitrarily large square chess board, and you need to determine whether any of the knights can attack one another in the given configuration.

In the game of chess, knights can move two spaces vertically (up or down) and one space to the side (left or right), or they can move two spaces horizontally (left or right) and one space vertically (up or down). For example, the knight on the following board (denoted with a letter ‘N’, since the letter ‘K’ is traditionally reserved for the king in formal chess notation systems) can move to any position marked with an asterisk (‘*’), and no other positions:

 

Figure 1: The knight at position d3 can move to any square marked with an asterisk.

Thus, on the following board, none of the knights (denoted with the letter ‘N’) can attack one another:

 

Figure 2: A 4x4 board in which none of the knights can attack one another.

In contrast, on the following board, the knights at c6 and d8 can attack one another, as can the knights at c6 and d4:

 

Figure 3: An 8x8 board in which some of the knights can attack one another.

2.     Coordinate System

This program uses the same coordinate system given in the SneakyQueens assignment.

3.     Runtime and Space Requirements
In order to pass all test cases, the average-case / expected runtime of your solution cannot exceed O(nk), and the worst-case space complexity cannot exceed O(nk) (where n is the number of coordinate strings to be processed and k is the maximum length of any of those coordinate strings). So, you can only process the full length of each coordinate string some small, constant number of times.

Continued on the following page...

4.     Method and Class Requirements
Implement the following methods in a class named SneakyKnights. Please note that they are all public and static. You may implement helper methods as you see fit.

 public static boolean  allTheKnightsAreSafe(ArrayList<String coordinateStrings, int boardSize)

Description: Given an ArrayList of coordinate strings representing the locations of the knights on a boardSize × boardSize chess board, return true if none of the knights can attack one another. Otherwise, return false.

Parameter Restrictions: boardSize will be a positive integer less than or equal to Integer.MAX_VALUE. boardSize describes both the length and width of the square board. (So, if boardSize = 8, then we have an 8 × 8 board.) coordinateStrings will be non-null, and any strings within that ArrayList will follow the format described above for valid coordinates on a boardSize × boardSize board. Each coordinate string in the ArrayList is guaranteed to be unique; the same coordinate string will never appear in the list more than once.

Output: This method should not print anything to the screen. Printing stray characters to the screen (including newline characters) is a leading cause of test case failure.

 public static double difficultyRating()

Return a double indicating how difficult you found this assignment on a scale of 1.0 (ridiculously easy) through 5.0 (insanely difficult).

 public static double hoursSpent()

Return a realistic and reasonable estimate (greater than zero) of the number of hours you spent on this assignment.