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).
Click to flip. Right-click to force.Tap to flip, tap and hold to force.
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:
| Force | change the color of a tile. |
| Flip | change 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).
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.
Solve without forcing
Click to flip. No forcing.Tap to flip. No forcing.
Click the following tiles, indicated by their position (row, column).
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.
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 in number. By forcing alone, we can thus guarantee to solve any puzzle in 12 steps or under.
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.
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.
Now let’s start thinking about solving this game. Firstly, let’s get a feel for how complex our game is. There are 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 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
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:
Did you do it? Do you believe?
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.
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
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.
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 , the all-yellow board is (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)
So how about the moves? A move consists of two pieces of information:
That gives 50 possible moves. The tile index , for the tile in row and column (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
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 set, and decode_move turns a move back into its kind, row and column.
Now realize the following. Our LUT contains key-value pairs, and the keys are simply all the numbers from to . 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 is board . 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.
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.
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.
"""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))