Unflip Solver

An exact, provably move-optimal solver for the Unflip puzzle, with a step-by-step walkthrough printer.

Unflip is played on an N×N board of black and white tiles. A move selects any k×k square (2 ≤ k ≤ N) and flips every tile inside it — white becomes black, black becomes white. The board is solved when every tile is white, and the goal is to get there in the fewest possible moves.

This solver finds that minimum — not a heuristic answer, a proven one — and prints each move as an annotated board card. Boards up to 13×13 (650 candidate moves) solve in well under a second for almost every level.

Step 1 of 3 — flip the 2×2 square covering rows 2–3, cols 3–4:
     1 2 3 4 5 6 7
  1  · · · · · · ·
        ┌───┐
  2  · ·│■ ■│· · ·
  3  · ·│· ·│■ · ·
        └───┘
  4  · · ■ ■ ■ · ·
  ...

· is a white (solved) tile, ■ is black. The flip square is outlined and highlighted in color on ANSI terminals.

Contents

File	Purpose
unflip.py	Front end: loads levels, runs the solver, renders step cards, verifies solutions
unflip_solver.cpp	C++17 search core — exact optimal, multithreaded
daily_levels_book.json	159 daily levels (4×4 – 10×10, with par)
main_levels_book.json	120 main levels (4×4 – 9×9, par on all but one)
weekly_challenges_book.json	25 weekly challenges (9×9 – 13×13, no par given)

Usage

python unflip.py daily 5             # solve daily level 5, print step cards
python unflip.py weekly 20           # solve weekly challenge 20 (13×13)
python unflip.py main 1              # solve main level 1
python unflip.py daily --list        # list the levels in a book
python unflip.py weekly --all        # solve every level, print a summary table
python unflip.py board.txt           # solve a raw text board (0/1 or 1/2 digits)

Options: --compact (move list only, no boards), --ascii (no Unicode glyphs), --no-color (no ANSI colors).

After printing a solution, unflip.py re-applies every move to the original board and checks that all tiles are white before declaring success — the output is verified, not just trusted.

Running the solver directly

The C++ core is a standalone program that reads a board from stdin or a file:

Get-Content board.txt | .\unflip_solver.exe
.\unflip_solver.exe board.txt --threads 8
.\unflip_solver.exe board.txt --target either

Flag	Meaning
--target 0	finish with every tile color 0 — the game's goal (default)
--target 1	finish with every tile color 1
--target either	race both targets bound-by-bound; optimal over both
--threads T	worker threads (default: all logical cores)

Input is N lines of N digits, either 0/1 or 1/2 (the latter is mapped to 0/1). Output is a small line protocol that unflip.py parses (this is the real output for the included board.txt, a 5×5 board with two stray black tiles that nonetheless needs 8 moves):

TARGET 0          # which input color the board ends as
MOVES 8           # optimal move count
1 1 2             # one move per line: row col size (0-based, top-left corner)
1 1 3
0 3 2
0 0 3
0 0 5
2 2 2
2 2 3
3 0 2
NODES 65          # search nodes expanded
TIME 0.002        # seconds

Progress lines (bound 7 exhausted, nodes=52) go to stderr as each depth is ruled out.

Building

g++ -O3 -march=native -std=c++17 -o unflip_solver.exe unflip_solver.cpp

No dependencies beyond a C++17 compiler. If the executable is missing, unflip.py builds it automatically with g++ on first use.

How it works

The size of the raw move space is what makes this puzzle hard: a 13×13 board has 650 distinct flip squares, any subset of which could be a solution, and each move touches up to 169 tiles. The solver's core idea is a change of representation that makes every move local — touching exactly 4 points instead of up to k² tiles — and then an IDA* search with strong pruning over that compact domain.

The XOR-difference transform

Let t[i][j] be 1 for each tile that still needs to be flipped (the black tiles). Define the 2D XOR-difference grid on the (N+1)×(N+1) lattice of tile corners:

D[i][j] = t[i][j] ^ t[i-1][j] ^ t[i][j-1] ^ t[i-1][j-1]

(out-of-range cells count as 0). This is a discrete second difference over GF(2), and it has two properties that drive everything else:

1. Moves become 4-point toggles. Flipping a k×k square at (r, c) toggles a solid k² block of t, but in the difference domain the interior cancellations are exact: only the four corner points D[r][c], D[r][c+k], D[r+k][c], D[r+k][c+k] change.
2. Solved ⇔ all zero. The transform is invertible (t is the 2D prefix-XOR of D), so D is all-zero exactly when no tile needs flipping.

A "flip 25 tiles" operation is now "toggle 4 points", and the goal is "clear the grid". The whole (N+1)² ≤ 196-point grid fits in a 256-bit bitboard (four 64-bit words), so applying a move is 4 XORs and the solved test is an OR of four words.

IDA* with forced corner branching

The search is iterative-deepening A*: try to solve within 0 moves, then 1, then 2, … The first depth that yields a solution is optimal by construction, because every shallower depth was exhausted first.

At each node the solver does not branch over all 650 moves. It takes the first remaining 1-point of D in row-major order. Any solution must clear that point, and a move can only touch it if the point is one of the move's four corners — so the branch set is just the moves having that corner, a small fraction of the total. Candidates are ordered by how many current 1-points their four corners clear (4 down to 1), so the most productive moves are tried first. Since moves are involutions and order is irrelevant over GF(2), each move is also used at most once along any search path.

Admissible lower bound (the main pruner)

Each move contributes exactly one column pair {c, c+s} (with s ≥ 2) to each of 2 rows of D, and one row pair to each of 2 columns. Geometry constrains which pairs a line can receive: row i can only host pair distances up to max(i, N−i), because the square must fit on the board.

At startup, a BFS over line bitmasks precomputes, for every possible line state and distance limit, the minimum number of pairs whose XOR clears that line. From these per-line costs come three lower bounds on the moves still required:

• ceil(Σ row costs / 2) — every move feeds exactly 2 rows,
• ceil(Σ column costs / 2) — likewise for columns,
• the largest single-line cost — a move adds at most one pair to any line.

Their maximum is admissible, and it is maintained incrementally: applying or undoing a move re-evaluates only the 2 rows and 2 columns it touches (the transposed grid is kept in a second bitboard so column lookups are as cheap as row lookups). Any branch whose bound exceeds the remaining move budget is cut immediately.

Lock-free transposition table

A transposition table shared by all threads records, for each difference state seen, the largest remaining-move budget that already failed from it. Reaching the same state with an equal or smaller budget is pruned without re-searching — this is what removes the massive duplication IDA* otherwise suffers when different move orders reach the same position.

Each entry is a single 64-bit word — a 59-bit hash fingerprint plus the failed budget in the low 5 bits — so plain atomic loads and stores stay consistent across threads with no locks. Buckets hold two slots (depth-preferred and always-replace), and the state hash is a splitmix64 mix of the four bitboard words. The table is 256 MB (2²⁴ buckets) on boards of 9×9 and up, 16 MB below that. Results are only stored when the search genuinely exhausted the subtree — a search aborted because another thread found a solution proves nothing and is not recorded.

Parallel root splitting

Within each depth iteration, the root's candidate moves are distributed across a thread pool via an atomic work-stealing counter. Each worker keeps its own search state; the transposition table is the only shared structure. The first thread to find a solution sets a shared flag and the rest wind down. With --target either, both uniform-color goals are raced bound-by-bound, so the answer is optimal across both finishes.

The Python front end

unflip.py is the human-facing layer. It loads a level from one of the JSON books (or a raw text file), converts the tiles to the solver's 0/1 input (in the books, value 1 is the goal color and 2 needs flipping), invokes unflip_solver.exe --target 0 as a subprocess, and parses the move list. It then renders each step as a labeled board card with the flip square outlined, re-applies all moves to verify the final board is uniform, and — with --all — checks every solved level's move count against the book's par.

Results

All solutions are independently verified by replaying the moves on the original board.

• 159/159 daily levels solved optimally, every move count equal to par, in ~2 s total (slowest single level ~10 ms).
• 120/120 main levels solved optimally.
• 25/25 weekly challenges (9×9 – 13×13, optima up to 25 moves, not known beforehand) solved optimally; all but two levels in under ~1 s. The two hardest (24-move optima) take ~7 s and ~38 s on a 20-thread machine. For comparison, the first of those did not finish in over 4 minutes with a single-threaded prototype using a weaker bound and no transposition table.

Weekly Challenges — solving all 25 levels

 lvl   board  par  moves      time  title
   1   10x10    -     12    0.001s  Weekly #1
   2   10x10    -     18    0.021s  Weekly #2
   3   11x11    -     18    0.032s  Weekly #3
   4   11x11    -     19    0.040s  Weekly #4
   5   11x11    -     17    0.264s  Weekly #5
   6   11x11    -     24    6.727s  Weekly #6A
   7   11x11    -     16    0.002s  Weekly #6B
   8   10x10    -     17    0.005s  Weekly #7
   9   10x10    -     19    0.042s  Weekly #8
  10   10x10    -     13    0.003s  Weekly #9
  11   10x10    -     18    0.005s  Weekly #10
  12   10x10    -     12    0.001s  Weekly #11
  13     9x9    -     13    0.006s  Weekly #12
  14     9x9    -     17    0.072s  Weekly #13
  15   12x12    -     14    0.006s  Weekly #14
  16   12x12    -     24   37.840s  Weekly #15
  17   11x11    -     25    0.001s  Weekly #16
  18   12x12    -     14    0.006s  Weekly #17
  19   12x12    -     11    0.002s  Weekly #18
  20   11x11    -     19    0.273s  Weekly #19
  21   13x13    -     14    0.036s  Weekly #20
  22   11x11    -     18    0.009s  Weekly #21
  23   11x11    -     13    0.011s  Weekly #22
  24   11x11    -     18    0.003s  Weekly #23
  25   12x12    -     17    0.003s  Weekly #24

total solver time: 45.41s

Timings measured on a 20-thread desktop CPU; node counts and times are printed per run.

Notes

• The game's only winning state is all-white. White is tile value 1 in the JSON books, which maps to 0 after the front end's conversion, hence --target 0.
• With multiple threads, the specific optimal solution returned can vary between runs (whichever thread wins the race reports its line), but the move count is always the proven minimum.