## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# KnightL on a chessboard challenge

Sharing is caring!

Problem statement
$KnightL$ is a chess piece that moves in an $L$ shape. We define the possible moves of $KnightL(a,b)$ as any movement from some position $(x_1, y_1)$ to some $(x_2, y_2)$ satisfying either of the following:

$x_2 = x_1 \pm a$ and $y_2 = y_1 \pm b$, or
$x_2 = x_1 \pm b$ and $y_2 = y_1 \pm a$

Note that $(a, b)$ and $(b, a)$ allow for the same exact set of movements. For example, the diagram below depicts the possible locations that $KnightL(1,2)$ or $KnightL(2,1)$ can move to from its current location at the center of a $5 \times 5$ chessboard:

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

Given the value of $n$ for an $n \times n$ chessboard, answer the following question for each pair where $1 \le a,b \textless n$:

• What is the minimum number of moves it takes for $KnightL(a,b)$ to get from position $(0,0)$ to position $(n - 1, n - 1)$? If it’s not possible for the Knight to reach that destination, the answer is $-1$ instead.

Then print the answer for each $KnightL(a,b)$ according to the Output Format specified below.

Input Format
A single integer denoting $n$.

Constraints
$5 \le n \le 25$

Output Format
Print exactly $n - 1$ lines of output in which each line $i$ (where $1 \le i \textless n$) contains $n - 1$ space-separated integers describing the minimum number of moves $KnightL(i,j)$ must make for each respective $j$ (where $1 \le j \textless n$). If some $KnightL(i,j)$ cannot reach position $(n - 1, n - 1)$, print -1 instead.

For example, if $n = 3$, we organize the answers for all the $(i, j)$ 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 $KnightL(1,1)$, $KnightL(1,2)$, and $KnightL(1,3)$:

One minimal path for $KnightL(1,4)$ is:

$(0,0) \rightarrow (1,4) \rightarrow (2,0) \rightarrow (3,4) \rightarrow (4,0) \rightarrow (0,1) \rightarrow (4,2) \rightarrow (0,3) \rightarrow (4,4)$

We then print 4 4 2 8 as our first line of output because $KnightL(1,1)$ took $4$ moves, $KnightL(1,2)$ took $4$ moves, $KnightL(1,3)$ took $2$ moves, and $KnightL(1,4)$ took $8$ moves.

In some of the later rows of output, it’s impossible for $KnightL(i,j)$ to reach position $(4,4)$. For example, $KnightL(3,3)$ can only move back and forth between $(0,0)$ and $(3,3)$ so it will never reach $(4,4)$.

Solution
We are going to solve this problem by searching for a solution recursively for every $(i,j)$. From each current position $(r,c)$ we know which new position $(newRow, newCol)$ we can reach. The possible values of $(newRow, newCol)$ given a current position $(r,c)$ and a pair $(i,j)$ 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 $(r,c)$. 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 $(newRow, newCol)$ we can reach from a given current position $(r,c)$.

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 $(n - 1, n - 1)$. 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 $(newRow, newCol)$ only when:
– we haven’t visited $(newRow, newCol)$ before, or,
– we have visited $(newRow, newCol)$ 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 $(i,j)$.

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();
}
}
}