# KnightL on a chessboard challenge

**Problem statement**

is a chess piece that moves in an shape. We define the possible moves of as any movement from some position to some satisfying either of the following:

and , or

and

Note that and allow for the same exact set of movements. For example, the diagram below depicts the possible locations that or can move to from its current location at the center of a chessboard:

Observe that for each possible movement, the Knight moves units in one direction (i.e., horizontal or vertical) and unit in the perpendicular direction.

Given the value of for an chessboard, answer the following question for each pair where :

- What is the minimum number of moves it takes for to get from position to position ? If it’s not possible for the Knight to reach that destination, the answer is instead.

Then print the answer for each according to the Output Format specified below.

**Input Format**

A single integer denoting .

**Constraints**

**Output Format**

Print exactly lines of output in which each line (where ) contains space-separated integers describing the minimum number of moves must make for each respective (where ). If some cannot reach position , print -1 instead.

For example, if , we organize the answers for all the pairs in our output like this:

(1,1) (1,2) (2,1) (2,2)

**Sample Input 0**

5

**Sample Output 0**

4 4 2 8 4 2 4 4 2 4 -1 -1 8 4 -1 1

**Explanation 0**

The diagram below depicts possible minimal paths for , , and :

One minimal path for is:

We then print `4 4 2 8`

as our first line of output because took moves, took moves, took moves, and took moves.

In some of the later rows of output, it’s impossible for to reach position . For example, can only move back and forth between and so it will never reach .

**Solution**

We are going to solve this problem by searching for a solution recursively for every . From each current position we know which new position we can reach. The possible values of given a current position and a pair can be easily computed as follows:

int[] rows = {r + i, r + i, r - i, r - i, r + j, r + j, r - j, r - j}; int[] cols = {c + j, c - j, c + j, c - j, c + i, c - i, c + i, c - i};

We then have 8 (not necessarily valid) new positions we can reach from . Example: for a given `newRow = rows[1]`

the corresponding `newCol`

will be `cols[1]`

. That is, an entry at index `idx`

in `rows`

corresponds to an entry at `cols[idx]`

.

We then call our search function recursively for every pair we can reach from a given current position .

For our recursive algorithm to work we need to have a terminating condition:

if (r == n - 1 && c == n - 1) { return count; }

where `count`

is the current number of steps it took us to reach this far for a given function call.

Obviously thats not all. In order to avoid jumping between two positions indefinitely we need to store some sort of state so our algorithm will stop in case we can never reach . That is, we are only going to *jump* to a new state if we haven’t visited that state already or if we may have found a shorter path to that state in case the state has been visited before.

Our state is a combination of *row*, *column* and *number of steps* it took us to get there. We are going to jump to only when:

– we haven’t visited before, or,

– we have visited before but the number of steps it took us to get there is larger than `count + 1`

Finally we need to keep track of our minimum number of steps for every .

**Full code**

public class KnighL { private static int brute(int n, int i, int j, int r, int c, boolean[][] visited, int[][] steps, int count) { visited[r][c] = true; if (r == n - 1 && c == n - 1) { return count; } else { int[] rows = {r + i, r + i, r - i, r - i, r + j, r + j, r - j, r - j}; int[] cols = {c + j, c - j, c + j, c - j, c + i, c - i, c + i, c - i}; int min = Integer.MAX_VALUE; for (int rc = 0; rc < 8; rc++) { int newRow = rows[rc]; int newCol = cols[rc]; if (newRow >= 0 && newCol >= 0 && newRow < n && newCol < n) { if (!visited[newRow][newCol] || (visited[newRow][newCol] && steps[newRow][newCol] > count + 1)) { steps[newRow][newCol] = count + 1; int ans = brute(n, i, j, newRow, newCol, visited, steps, count + 1); if (ans != Integer.MAX_VALUE) { if (ans < min) { min = ans; } } } } } return min; } } private static int solve(int n, int i, int j) { int[][] steps = new int[n][n]; int ans = brute(n, i, j, 0, 0, new boolean[n][n], steps, 0); return ans != Integer.MAX_VALUE ? ans : -1; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { int ans = solve(n, i, j); System.out.print(ans + " "); } System.out.println(); } } }