Return to Blog

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:

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
        visited.add((x, y))

    return len(visited)

kings_reach_bf(7)

225

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

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?

What if, instead, I

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

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?

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?

As a result, for n moves,

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:

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.)