Sliding Puzzle Solvable?

Puzzle Representation

Rather than representing the puzzle as a matrix it will make sense to us to “unwrap” the puzzle into a vector. So, for example, the final configuration of the puzzle would be

[1, 2, 3, 4, 5, 6, 7, 8, 0]

where 0 has been used to denote the empty square.

Inversions and Polarity

To make sense of the algorithm for determining whether a puzzle configuration is solvable we need to define two terms:

• inversion — an inversion is any pair of tiles that are not in the correct order; and
• polarity — is the total number of inversions even (solvable) or odd (not solvable)?

Consider the following puzzle configuration which has six inversions:

[1, 3, 4, 7, 0, 2, 5, 8, 6]

Let’s look at the inversions (since the 0 is just a place holder it’s not considered when finding inversions):

• 3 > 2
• 4 > 2
• 7 > 2
• 7 > 5
• 7 > 6 and
• 8 > 6.

Since there are six inversions (even polarity) this configuration is solvable.

Here’s a configuration which is not solvable:

[2, 1, 3, 4, 5, 6, 7, 8, 0]

There’s just a single inversion (2 > 1), so the polarity is odd.

Some notes on the link between inversions, polarity and solvability can be found here.

Python Implementation

The game concept is being implemented using Unreal Engine, a paradigm with which I am completely unfamiliar. So it made more sense for me to implement the solvability algorithm in Python and just pass this on to the Unreal developer.

So here’s the simple function:

def solvable(tiles):
    """
    Check whether a 3x3 sliding puzzle is solvable.

    Checks the number of "inversions". If this is odd then the puzzle configuration is not solvable.

    An inversion is when two tiles are in the wrong order.

    For example, the sequence 1, 3, 4, 7, 0, 2, 5, 8, 6 has six inversions:

    3 > 2
    4 > 2
    7 > 2
    7 > 5
    7 > 6
    8 > 6

    The empty tile is ignored.
    """
    count = 0

    for i in range(8):
        for j in range(i+1, 9):
            if tiles[j] and tiles[i] and tiles[i] > tiles[j]:
                count += 1

    return count % 2 == 0

Let’s give it a test run.

{{< comment >}}
print(solvable([1, 2, 3, 4, 5, 6, 7, 8, 0])) # 0 -> solvable
print(solvable([3, 7, 2, 4, 5, 8, 0, 1, 6])) # 12 -> solvable
print(solvable([1, 3, 4, 7, 0, 2, 5, 8, 6])) # 6 -> solvable
print(solvable([1, 8, 2, 0, 4, 3, 7, 6, 5])) # 10 -> solvable
print(solvable([2, 1, 3, 4, 5, 6, 7, 8, 0])) # 1 -> not solvable
print(solvable([8, 1, 2, 0, 4, 3, 7, 6, 5])) # 11 -> not solvable
{{< /comment >}}

>>> solvable([1, 2, 3, 4, 5, 6, 7, 8, 0])
True
>>> solvable([2, 1, 3, 4, 5, 6, 7, 8, 0])
False

Looks good. No more broken puzzles!