Knight’s move on infinite chess board with constant time and space
There are a lot of variations of knight movements on a chess board related questions. In this article, I will focus on the one that a knight moves to a desired position with less move. Here is the question:
Question: In an infinite chess board, a knight given in a position say it is (0,0). Return the minimum number of moves needed to move the knight to position (x,y).
First of all it is a good idea to recall the movement rule of a knight. A knight moves two square in one direction and one square in an orthogonal direction. It can also start with one square and continue with two squares in an orthogonal direction. So, a knight has eight possible moves that it can make from a point as shown in the image below.
The knight is at the origin of the infinite board and the movements of the knight in each quadrant are same. Thus, we can assume that the given point is always positive (use the absolute values of the x and y) and the knight is on the bottom left of the board.
This question can be solved by dynamic programming by calculating values for each square. For example, a knight at (0,0) can move to (1,2) by one move. Since the value of the target square is empty (ie, 0), the value can be incremented by one. All the board can be filled by this way using breadth first search (BFS). The value of each square would give the number of moves needed. The following illustration shows how a board is filled by BFS.
As seen above moving the knight to position (7,7) on 8x8 board needs 6 moves. Obviously, on a MxN board, calculating the number of moves needs quadratic O(MN) time and memory. The diagonal square of the knight is calculated as 4 when the knight is on the corner square. This would be 2 if knight is not on a corner square as shown in the image below. Since there is no corner on an infinite board, we should use the value of diagonal square as 2.
A quadratic complexity is acceptable for this problem however it is clear that the numbers on the board are not randomly assigned and if a pattern can be found between them, a mathematical formula can be derived which would run in a constant complexity.
A knight can obviously move to the green squares shown above with the number of moves written in them. The move is made by two horizontal move and one vertical move. The coordinates of those squares can be represented by (2a, a). If the given point (x, y) is one of the green squares, we can simple say that the number of moves needed is x/2=a.
In the first image, the next moves are chosen as next upper squares. It is clear that adding next lower squares will end up with same number of moves. So, still if the given point (x, y) is one of the green squares, we can simple say that the number of moves needed is x/2=a. This, would create a lower (green) area of a board.
The upper (blue) area can be defined similarly where the boundary of the area can be represented by (a, 2a). If the given point (x, y) is one of the blue squares, we can simple say that the number of moves needed is y/2=a.
If the given point (x, y) is one of the coloured squares so far, the answer would be either x/2 or y/2. Since the number of moves needed is always half of the coordinate entries, the answer would be as follows.
The middle area of the coloured squares can obviously filled like the following image. The new area forms diagonals between two areas and the coordinates of the squares can be represented by (a + k, 2a - k) where 0 ≤ k ≤ a.
As the first two areas, the red squares also have a pattern where x+y is always divisible by 3. If the given point (x, y) is one of the red squares, we can simple say that the number of moves needed is (x + y)/3=a. It is clear that moving from blue to red decreases the value of y/2 from a to a/2 and increases value of x/2 from a/2 to a. However, these values can never be more than the value a while (x+y)/3 is always equal to a. So, these three formulas can be merged and for a given (x, y) square, the answer is as follows.
The formula above can be represented as the formula below where all the colored square can be seen clearly.
Another observation is that the partitioned representation of the formula shows the following equation is correct.
As seen in the colored board above, each uncolored squares have a colored square at their horizontal or vertical neighbourhoods. This means that x +/- 1 or y +/- 1 would end up with a colored square and the formula gets an integer value. To find the neighbour square, the formula should be tried for each four neighbour. Mathematically, it can also be achieved by rounding the result.
Only one of the neighbour will be shown as an example since the rest are similar. Assume (x, y) is an uncolored square and (x-1, y) results a=(x-1)/2. Then y should be equal to (x-1)/2 - 2k according to partitioned representation of the formula. Summing up a, x and y shows that the result of the sum is odd.
The square (x, y) can be written as (2y+1, y) by assuming the value of the k=0. Applying one of the knight’s move, lets say it is (1, -2), will result, (2y+2, y-2) which satisfies (x+y)mod3=0. Similarly, the other uncolored squares can be checked and seen that a knight can move to a colored square from an uncolored square by one move.
The rule above is clearly seen for most of the squares but it is not obvious for the bottom neighbour of squares of green or blue area. To see the condition is also true for them, the same green coloring can be applied by starting (2, 0) square which has the value of 2. This is shown in the image below.
By using all the above observations, the number of moves needed is the a value for the colored squares and a+1 for other squares. Thus, the below formula is the final one.
This formula can calculate the number of moves where x > 2 and y > 2 because there is not enough information to calculate the value for smaller boards.
The image below shows the calculation by BFS and the formula for 12x16 board. The while loop in BFS algorithm is called 12x16 = 192 times and the formula is called only once.
To use this formula for any position, the first 3x3 values should be set manually. This formula is not limited to an infinite board. It can also be used on a finite board by changing the starting value of (1,1) to 4.
Thank you for reading.
