Flipping tiles

Click to flip. Right-click to force.Tap to flip, tap and hold to force.

Move 0 / 2

The game

Here’s a simple puzzle. You are given a 5x5 board of green and yellow tiles. The tiles, however, can be flipped! If a tile appears yellow, then its opposite side (facing away from you) is green and vice versa. Your job is to get all tiles to show the same color, either all-yellow or all-green. To do this, there are two types of moves you can make:

Forcechange the color of a tile.
Flipchange the color of a tile and its neighbours (ignoring edges).

Give it a try! Turn the board green using each move exactly once. To interact with the widget, use the left and right mouse buttons (on PC), or tap and tap-and-hold (on mobile).

The challenge

Well, that wasn’t particularly challenging, but it can get much harder! Let me show you a much more difficult example. The puzzle shown below can be solved in just six steps. Alternatively, it can be solved in seven steps without forcing any tiles. Can you find either solution? Give it a try! Don’t worry if you get stuck: the answer can be found below.

Solve in six moves

Click to flip. Right-click to force.Tap to flip, tap and hold to force.

Move 0 / 6

Solve without forcing

Click to flip. No forcing.Tap to flip. No forcing.

Move 0 / 7
Reveal the answerHide

Click the following tiles, indicated by their position (row, column).

  • Six moves: flip (2, 2), (2, 3), (3, 2) and (4, 1), then force the two remaining tiles.
  • No forces: flip (1, 5), (2, 1), (2, 2), (4, 3), (4, 4), (5, 3) and (5, 4).

Observations about the game

How did it go? Did you solve the puzzle without sneaking a peek at the answer? Whether you think these puzzles are easy or flipping difficult, in this post you can learn how to solve them all through the power of programming. Before jumping into the code, however, let’s start with a few basic observations.

  1. Every imaginable puzzle is solvable. This is true, because there are two trivial solutions: you can always force all yellow tiles green, or force all green tiles yellow. Since there are 25 tiles, at least one of the colors must be <13<13 in number. By forcing alone, we can thus guarantee to solve any puzzle in 12 steps or under.

  2. Order doesn’t matter. The final color of a tile depends only on how many times it has been changed. A move either changes a tile once, or it doesn’t touch it. If two different moves both change the same tile, it changes twice and ends up the way it started. It does not matter in which order the moves are made, the outcome is always the same.

  3. Every move is its own inverse. Changing a tile twice is the same as doing nothing. The same argument applies when a move changes several tiles at once: doing it twice flips the tiles back to the way they were.

One table to solve them all…

Now let’s start thinking about solving this game. Firstly, let’s get a feel for how complex our game is. There are 225≈2^{25} \approx 33 million different puzzles: a number that is enormous to human standards, but very managable for a computer. In other words, we can afford to consider all possible board configurations in a single calculation. Similarly, we can afford to solve all 2252^{25} puzzles ahead of time and store them in a giant lookup table (LUT). Once we have our LUT, solving a puzzle becomes extremely fast, because it doesn’t require any thinking at all: look up the board and make the stored move, next look up the resulting board and again move accordingly, etcetera, until the board is solved. Note that the LUT only needs to store the first move toward the solution; the second move is obtained by looking up the board produced by the first move.

LUT = {
    Board(green green  green  ... green  green  green ): "Solved",

    # One yellow tile
    Board(yellow green  green  ... green  green  green ): "Force Tile(1, 1)",
    Board(green  yellow green  ... green  green  green ): "Force Tile(1, 2)",
    ...
    Board(green  green  green  ... green  yellow green ): "Force Tile(5, 4)",
    Board(green  green  green  ... green  green  yellow): "Force Tile(5, 5)",

    # Two yellow tiles
    Board(yellow yellow green  ... green  green  green ): "Flip  Tile(1, 1)",
    Board(yellow green  yellow ... green  green  green ): "Force Tile(1, 3)",
    ...
    Board(green  green  green  ... yellow green  yellow): "Force Tile(5, 5)",
    Board(green  green  green  ... green  yellow yellow): "Flip  Tile(5, 5)",

    # Three yellow tiles
    Board(yellow yellow yellow ... green  green  green ): "Flip  Tile(1, 2)",
    Board(yellow yellow green  ... green  green  green ): "Flip  Tile(1, 1)",
    ...
    etcetera.
}

def solve(board):
    solution = []  # moves to make
    while LUT[board] != 'Solved':
        move = LUT[board]
        solution.append(move)

        board = apply(move, board)
    return solution

Dynamic programming - Populating the lookup table

OK, so we need a lookup table. But how do we compute it? The answer is to use dynamic programming. This term describes the process of solving a general problem by (i) starting with special cases that are trivial to solve (like the first puzzle) and (ii) express harder problems (like the second) in terms of the solutions of easier problems. To mentally prepare yourself for this, you should do the following:

  1. Worry over how complex/difficult the problem appears.
  2. Convert your worries into faith. You have got to believe that the hard cases become trivial after you have dealt with the easy ones.

Did you do it? Do you believe?

Sorting 33 million puzzles from easy to hard

Well, let’s go! Lets go through all 33 million puzzles in order of increasing difficulty. As mentioned, we should start with the trivial cases: they are the two boards that are already solved (all-green and all-yellow). Their solutions have zero steps: the LUT simply says “solved”.

Next come the boards that are one move away from solved. Which boards are those? We don’t have to search for them: we make them. Take a solved board and try each of the possible moves (25 flips and 25 forces). This yields us all 50 puzzles that can be solved in one move. Their solutions are obtained for free: the moves that created these puzzles are also the ones that solve them (because a move is its own inverse).

The boards that are two moves away have now become trivial to solve as well, because and we can repeat the same trick: take every board of the newest epoch and try all 50 moves on it. Every board that comes out that we have never seen before is another puzzle that we have solved, so we add it to the LUT. If a board is already in the LUT, it means we already solvled this puzzles so we simply skip it. Searching outward one layer at a time like this is known as a breadth-first search. The corresponding algorithm takes the following form:

def build_lut():
    """Breadth-first search: solve all board configurations in order of increasing distance from solution."""
    # Trivial cases
    LUT = {ALL_GREEN: SOLVED, ALL_YELLOW: SOLVED}
    layer = [ALL_GREEN, ALL_YELLOW]

    while layer:  # as long as the last epoch found new boards
        next_layer = []

        # Every board that is one move away from the current epoch
        for board in layer:
            for move in MOVES:
                new_board = apply(move, board)

                # Skip the boards we have already solved
                if new_board not in LUT:
                    LUT[new_board] = move         # a new entry in our lookup table
                    next_layer.append(new_board)  # a starting point for the next epoch

        layer = next_layer
    return LUT

The algorithm above explicitly handles all-green and all-yellow solutions as separate cases. However, one may recognize that this is somewhat redundant: a puzzle is effectively identical to its own color-inverse, because both are solved by the same set of moves. Hence, one may remove ALL_YELLOW from the starting layer and add LUT[color_inverse(new_board)] = move. This, you get not one but two solutions out of every iteration.

Fewest moves, or fewest forces?

So far our only goal has been to minimize the number of moves that our solution has. However, we might be interested in a different criterium. For example, let us find the solutions that require the fewest number of forces. In this case, we are not counting the number of moves, but instead measure their combined cost. In our case, the cost of a force greater than the cost of a flip. Fortunately, we only need to make a minor change, converting breadth-first-search into Dijkstra’s algorithm.

def build_lut(flip_cost, force_cost):
    # The trivial cases (epoch 0)
    LUT = {ALL_GREEN: SOLVED, ALL_YELLOW: SOLVED}
    cost = {ALL_GREEN: 0, ALL_YELLOW: 0}
    epochs = {0: [ALL_GREEN, ALL_YELLOW]}  # cost -> boards with that cost

    while epochs:
        c = min(epochs)  # the cheapest epoch first
        for board in epochs.pop(c):
            if cost[board] < c:  # solved cheaper in the meantime
                continue
            for move in MOVES:
                new_cost = c + (force_cost if is_force(move) else flip_cost)
                new_board = apply(move, board)

                # A new entry, or a cheaper solution than we had
                if new_cost < cost.get(new_board, INFINITY):
                    LUT[new_board] = move
                    cost[new_board] = new_cost
                    epochs.setdefault(new_cost, []).append(new_board)
    return LUT

Efficient memory usage

The algorithm is complete, but one question is still open: how do we turn boards and moves into the keys and values of our lookup table? We could take a picture of every board and use those as the keys. But that would be impractical as well as wasteful: matching a picture against 33 million others is slow, and millions of pictures take up a lot of memory.

Boards

What we need instead is an encoding: a compact way to write down a board. An intuitive example is a text encoding. Reading the tiles row by row, from the top left to the bottom right, the challenge puzzle could be written as

ggygg-yygyg-ggggy-ygggg-ygggg

where g stands for a green tile and y for a yellow one. The dashes only mark the rows to make it easier to read; in practice we would leave them out.

But we can do better still. Under the hood, each character takes up 8 bits: g is stored as 01100111 and y as 01111001. Eight bits per tile is a lot, considering that a single bit is enough: 0 for green, 1 for yellow. The challenge puzzle then becomes

00100-11010-00001-10000-10000

That is no longer text, but a binary number of 25 bits, and the computer stores it exactly like that. We humans would write this number as 5,047,824. The all-green board is the number 00, the all-yellow board is 225−12^{25} - 1 (all 25 bits set), and every other board is a number in between. These numbers are the keys of our LUT. Python can even do the conversion for us:

def encode_board(text):
    """'ggygg-yygyg-...' -> number: one bit per tile, read row by row from the top left."""
    return int(text.replace("-", "").replace("g", "0").replace("y", "1"), 2)

Moves

So how about the moves? A move consists of two pieces of information:

That gives 50 possible moves. The tile index 5r+c5r + c, for the tile in row rr and column cc (counting from 0), is a number from 0 to 24, which fits in five bits. One more bit says whether the move is a force. Together, that is six bits, so every move fits easily in a single byte. The tile indices 25 to 31 are never used, so one of them can serve as the marker for a solved board: SOLVED = 25.

FORCE = 32  # bit 5 of a move: force instead of flip

def encode_move(kind, r, c):
    return (FORCE if kind == "force" else 0) + 5 * r + c

def is_force(move):
    return move & FORCE != 0

Making moves

There is one more advantage of boards as numbers: making a move becomes a single operation. Changing the color of a tile means toggling its bit from 0 to 1 or back, and that is exactly what the XOR operator does (^ in Python). It compares two numbers bit by bit, and sets a bit wherever the two differ:

  00100-11010-00001-10000-10000    the challenge puzzle
^ 01000-11100-01000-00000-00000    the mask of a flip at r = 1, c = 1
= 01100-00110-01001-10000-10000    the board after the flip

So every move is a XOR with a fixed number, its mask: a board on which only the tiles that the move changes are yellow. For a force, that is a single tile; for a flip, a cross that is cut off by the edges of the board.

def tile(r, c):
    """The board with only tile (r, c) yellow."""
    return 1 << (N - 1 - (5 * r + c))

def mask(move):
    """The tiles a move changes: a single tile, or a cross (cut off by the edges)."""
    kind, r, c = decode_move(move)
    if kind == "force":
        return tile(r, c)
    cross = [(r, c), (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
    return sum(tile(i, j) for i, j in cross if 0 <= i < 5 and 0 <= j < 5)

def apply(move, board):
    return board ^ mask(move)

Here 1 << k is the number with only bit kk set, and decode_move turns a move back into its kind, row and column.

The board is the index

Now realize the following. Our LUT contains 2252^{25} key-value pairs, and the keys are simply all the numbers from 00 to 225−12^{25} - 1. Do you see what this means? Consider what the dictionary looks like when we sort it by key:

0: SOLVED
1: move for board 1
2: move for board 2
3: move for board 3
...

The keys don’t add any information! We might as well leave them out, and write

[SOLVED, move for board 1, move for board 2, move for board 3, ...]

The position in this array is the board, and the value at that position is the move to make. The boards themselves never need to be stored. With one byte per move, the whole LUT takes up 32 MB, where a Python dictionary with 33 million entries would take several gigabytes.

In numpy, such an array is created with np.zeros(2**25, dtype=np.int8), and the cost of every board goes into a second array of the same length. Numpy also lets us handle a whole epoch at once. If boards is an array of boards, then apply(move, boards) makes the move on all of them in a single operation, cost[boards] looks up all their costs at once, and boards[cost[boards] == c] keeps only the boards whose cost is c. That makes the inner loop over the boards disappear, and turns hours of computing into less than a minute.

One last trick is used by the widget on this page. A board and its color inverse always share their move, and the inverse of board ss is board 225−1−s2^{25} - 1 - s. So the second half of the array is the first half backwards, and only the first half needs to be downloaded. Packed with gzip, that is about 5 MB per table.

The code

Here is the puzzle once more, this time with the solver. Choose MinSteps or MinForces to see the solution from either table: a blue plus means “flip this tile”, a red dot means “force this tile”. Solve Step makes the moves one at a time, with the forces first.

Click to flip. Right-click to force.Tap to flip, tap and hold to force.

Move 0 / 25

And here is the complete solver. It is the code from this post, with the dictionaries replaced by numpy arrays. Running it takes about 40 seconds, and writes both tables to disk.

Show main.pyHide main.py
"""Flip tiles: a lookup table with the first move of an optimal solution for every 5x5 board."""
import numpy as np

N = 25                                # tiles on the board
ALL_GREEN, ALL_YELLOW = 0, 2**N - 1   # the two solved boards
SOLVED = 25                           # LUT value for a solved board (not a move)
FORCE = 32                            # bit 5 of a move: force instead of flip


# --- Boards ------------------------------------------------------------------------------
def encode_board(text):
    """'ggygg-yygyg-...' -> number: one bit per tile, read row by row from the top left."""
    return int(text.replace("-", "").replace("g", "0").replace("y", "1"), 2)


def tile(r, c):
    """The board with only tile (r, c) yellow."""
    return 1 << (N - 1 - (5 * r + c))


# --- Moves -------------------------------------------------------------------------------
def encode_move(kind, r, c):
    """One byte: bit 5 is the kind of move, bits 0-4 the tile index 5r + c."""
    return (FORCE if kind == "force" else 0) + 5 * r + c


def is_force(move):
    return move & FORCE != 0


def decode_move(move):
    r, c = divmod(move & ~FORCE, 5)
    return ("force" if is_force(move) else "flip"), r, c


def mask(move):
    """The tiles a move changes: a single tile, or a cross (cut off by the edges)."""
    kind, r, c = decode_move(move)
    if kind == "force":
        return tile(r, c)
    cross = [(r, c), (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
    return sum(tile(i, j) for i, j in cross if 0 <= i < 5 and 0 <= j < 5)


def apply(move, board):
    """Change the color of the masked tiles (works on one board or a whole array at once)."""
    return board ^ mask(move)


MOVES = [encode_move(kind, r, c) for kind in ("flip", "force") for r in range(5) for c in range(5)]


# --- The lookup table --------------------------------------------------------------------
def build_lut(flip_cost, force_cost):
    """
    Dynamic programming, from cheap to expensive: every board gets the first move of its
    cheapest solution. The board is the index in the LUT; the value is the move to make.
    """
    LUT = np.zeros(2**N, dtype=np.int8)
    cost = np.full(2**N, np.iinfo(np.int16).max, dtype=np.int16)  # cheapest found so far

    solved = np.array([ALL_GREEN, ALL_YELLOW], dtype=np.int32)
    LUT[solved], cost[solved] = SOLVED, 0
    epochs = {0: [solved]}                                  # cost -> boards with that cost

    while epochs:
        c = min(epochs)                                     # the cheapest epoch first
        boards = np.concatenate(epochs.pop(c))
        boards = boards[cost[boards] == c]                  # skip boards since solved cheaper
        for move in MOVES:
            new_cost = c + (force_cost if is_force(move) else flip_cost)
            new_boards = apply(move, boards)                # the whole epoch at once
            new_boards = new_boards[cost[new_boards] > new_cost]   # only improvements
            if new_boards.size:
                LUT[new_boards], cost[new_boards] = move, new_cost
                epochs.setdefault(new_cost, []).append(new_boards)
    return LUT


def solve(board, LUT):
    """Look up the move, make it, repeat until solved."""
    moves = []
    while LUT[board] != SOLVED:
        move = int(LUT[board])
        moves.append(decode_move(move))
        board = apply(move, board)
    return moves


if __name__ == "__main__":
    fewest_moves = build_lut(flip_cost=100, force_cost=101)   # a force costs a bit extra
    fewest_forces = build_lut(flip_cost=1, force_cost=100)    # a force costs 100 flips
    np.save("fewest_moves.npy", fewest_moves)
    np.save("fewest_forces.npy", fewest_forces)

    # Rows and columns count from 0 here
    challenge = encode_board("ggygg-yygyg-ggggy-ygggg-ygggg")
    print("fewest moves: ", solve(challenge, fewest_moves))
    print("fewest forces:", solve(challenge, fewest_forces))