# Solving the King's Reach problem in Python

By John Lekberg on May 30, 2020.

NOTE: Andrew Norton pointed out that the solution to this problem appears in the Online Encyclopedia of Integer Sequences as Sequence A273743. Thanks, Andrew!

This week's post is about the "King's Reach" problem. You will learn:

• How to create a brute force solution and analyze its time complexity.
• How to create a faster solution by looking at the problem from a different perspective.

# Problem Statement

You have an infinitely large chess board extending in all directions. You place a king ♔ on the board.

You are given a number n and you are told to find mark any square that the king ♔ can move to in exactly n moves. (The king ♔ can move one square in any direction.)

How many squares do you end up marking?

# How I represent the data

I represent the king's ♔ position on the chess board with cartesian coordinates. E.g.

``````(3, 8)
``````

In this coordinate system, the origin, `(0, 0)`, is where the king ♔ is originally placed.

# Creating a brute force solution

A simple brute force solution will generate all possible n-move sequences for the king ♔, and record the final positions. Here's a Python function that does that:

``````import itertools

def kings_reach_bf(n):
"""Solve the King's Reach problem for n moves by
generating all possible n-step movements.
"""
king_moveset = list(
itertools.product([-1, 0, 1], repeat=2)
)
king_moveset.remove((0, 0))

visited = set()

all_n_move_sequences = itertools.product(
king_moveset, repeat=n
)
for sequence in all_n_move_sequences:
x, y = 0, 0
for dx, dy in sequence:
x += dx
y += dy

return len(visited)

kings_reach_bf(7)
``````
``````225
``````

What's the time complexity of this solution? For n moves,

• There are 8 directions that the king ♔ can move in.
• Each move in an n-move sequence has 8 possibilities (from the 8 directions).
• Therefore, there are 8n of the n-move sequences.

As a result, the time complexity of this algorithm is

O(8n)

# Creating a more efficient solution

There's got to be a way to create a faster solution.

How does the brute force solution work?

• Create all possible n-move sequences.
• Then, record where the king ♔ ends up.

• Create all potential places where the king ♔ ends up (overcounting).
• Then, go back and actually check if the king ♔ could reach those places in n moves.

I think this would produce a faster solution because generating all possible n-move sequences has a lot of redundancy (multiple n-move sequences end up at the same position). If

• The number of potential places is smaller than the number of possible n-move sequences (8n), and
• Checking if the king ♔ could actually reach a potential place is fast,

then the time complexity of this could be much better than the brute force solution.

What are the potential places that the king ♔ could move in n-moves?

• The furthest the king ♔ can move on the x-axis is between -n and n.
• The furthest the king ♔ can move on the y-axis is between -n and n.

As a result, the places that the king ♔ could move is a subset of

{ -n, -n+1, ..., -1, 0, 1, ..., n-1, n }2 = { (0, 0), (1, n), (-n, -n), ... }

The size of this set is (2n + 1)2 places.

How can I check if the king ♔ could actually reach a potential place?

• I know (from above) that if |x| > n or |y| > n, then (x, y) is unreachable.
• If (x, y) is (0, 0), then
• (0, 0) can be reached in n = 0 steps by not moving.
• (0, 0) cannot be reached in n = 1 step.
• (0, 0) can be reached in n > 1 steps, by
• Move to (0, 1).
• Move back and forth between (0, 1) and (1, 1) until the king ♔ has one move is left.
• Move back to (0, 0).
• For any other (x, y), such that |x| ≤ n and |y| ≤ n,
• The king ♔ can move from (x, y) to (0, 0) in mn steps.
• These steps can be modified to move from (x, y) to (0, 0) in n steps:
• When the king ♔ is one step away from (0, 0), it has moved m-1 steps.
• Move the king ♔ back and forth between two places that are both one step away from (0, 0) until the king has moved a total of n-1 steps.
• Move the king ♔ to (0, 0).
• Reverse these steps for the n-move sequence that moves the king ♔ from (0, 0) to (x, y).

As a result, for n moves,

• (x, y) is reachable if |x| ≤ n and |y| ≤ n.
• Except (0, 0) is reachable only if n ≠ 1.

Here's Python code that implements this:

``````import itertools

def reach(x, y, n):
"""Check if the position (x, y) is reachable by a
King in n steps from (0, 0).

In general if

- |x| <= n, and
- |y| <= n,

then (x, y) is reachable from (0, 0) in n steps.

The exception is when (x, y) is (0, 0):

- (0, 0) can be reached in n = 0 steps by not moving.
- (0, 0) CANNOT be reached in n = 1 step.
- (0, 0) can be reached in n > 1 steps, by
- Move (0, 1).
- Move back and forth between (0, 1) and (1, 1)
until the king has one move is left.
- Move back to (0, 0).
"""
if (x, y) == (0, 0):
return n == 0 or n > 1
else:
return max(abs(x), abs(y)) <= n

def kings_reach_quick(n):
"""Solve the King's Reach problem for n moves by
generating an overcount of visited positions (gridXY),
then fixing the overcount.
"""
assert n >= 0

gridXY = itertools.product(range(-n, n + 1), repeat=2)

n_visited = 0
for x, y in gridXY:
if reach(x, y, n):
n_visited += 1

return n_visited

kings_reach_quick(7)
``````
``````225
``````

What's the time complexity of this solution? For n moves:

• There are (2n+1)2 places to check.
• Checking each place requires O(1) operations.

As a result, the overall time complexity of the solution is

O(n2)

# Comparing the brute force solution and the quick solution

I want to confirm that `kings_reach_bf` and `kings_reach_quick` are generating the same results, so I assert that the first couple results are the same:

``````for i in range(9):
bf = kings_reach_bf(i)
quick = kings_reach_quick(i)♔
print(
f"n={i}",
f"bf={bf:3d}",
f"quick={quick:3d}",
f"(EQUAL? {bf==quick})",
sep=", ",
)
``````
``````n=0, bf=  1, quick=  1, (EQUAL? True)
n=1, bf=  8, quick=  8, (EQUAL? True)
n=2, bf= 25, quick= 25, (EQUAL? True)
n=3, bf= 49, quick= 49, (EQUAL? True)
n=4, bf= 81, quick= 81, (EQUAL? True)
n=5, bf=121, quick=121, (EQUAL? True)
n=6, bf=169, quick=169, (EQUAL? True)
n=7, bf=225, quick=225, (EQUAL? True)
n=8, bf=289, quick=289, (EQUAL? True)
``````

From my algorithmic analysis, I know that `kings_reach_quick` ( O(n2) ) has a better time complexity than `kings_reach_bf` ( O(8n) ).

I want to also measure the difference using cProfile:

``````import cProfile

cProfile.run('kings_reach_bf(8)')
``````
``````16777222 function calls in 13.469 seconds
[...]
``````
``````cProfile.run('kings_reach_quick(8)')
``````
``````1157 function calls in 0.000 seconds
[...]
``````

# In conclusion...

In this week's post, you learned how to solve the "King's Reach" problem. You constructed a brute force solution by generating all possible move-sequences. Then you looked at the problem from a different perspective and created a more efficient solution.

My challenge to you:

If the king ♔ could only move up, down, left, and right (instead of the 8 directions) how many places could it reach in n moves?

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!

(If you spot any errors or typos on this post, contact me via my contact page.)