The Parity Check: How Even-and-Odd Patterns Reveal Impossible Puzzle Moves
Why Parity Can Stop an Impossible Solve Before It Starts
Parity is the simple distinction between even and odd, but in puzzles it can become a powerful impossibility detector. If every legal move preserves an even-or-odd pattern, any target with the opposite pattern is unreachable. Recognizing that fact can save you from testing hundreds—or millions—of moves that could never succeed.
This technique belongs to a wider mathematical idea called an invariant: a property that remains unchanged while everything else moves around. Purdue University’s introduction to parity and the 15-puzzle explains how comparing invariants can prove that two puzzle positions cannot be connected by legal moves.
Parity appears in sliding puzzles, tiling challenges, coin-flipping games, path puzzles and many other brainteasers. You do not need advanced mathematics to use it. You only need to ask the right question:
What stays even or odd after every permitted move?
What Even and Odd Really Tell You
An even number is divisible by two, while an odd number leaves a remainder of one. That sounds elementary, but the following rules make parity remarkably useful:
- Even + even = even
- Odd + odd = even
- Even + odd = odd
- Adding or subtracting two preserves parity
- Switching between even and odd requires a change by an odd amount
Imagine a row of coins. A legal move requires you to flip exactly two coins. Depending on their current faces, the number of heads may rise by two, fall by two or remain unchanged. It can never change by one.
Therefore, the parity of the number of heads never changes. If you begin with an even number of heads, every reachable position must also contain an even number of heads. A goal showing an odd number of heads is impossible under those rules.
This is the heart of a parity argument: ignore unnecessary detail and track only the feature that cannot cross the even-odd boundary.
The Three-Part Parity Check
When you suspect that a puzzle may contain an impossible position, use this short process.
1. Choose Something Countable
Look for a feature that can be represented by a number or one of two states. Possibilities include:
- The number of pieces on dark squares
- The number of upside-down tokens
- The number of out-of-order pairs
- The color occupied by a moving piece
- Whether a blank space is on an odd or even row
- Whether a permutation requires an odd or even number of swaps
The most useful quantity is not always obvious. A puzzle may require you to combine two measurements, as the 15-puzzle does.
2. Study Every Legal Move
Do not ask what usually happens. Determine what every legal move does.
Does each move preserve parity? Does it always switch parity? Do two separate properties switch together? If different move types behave differently, record each type separately.
This kind of rule inspection fits naturally into the first 60 seconds of sizing up a puzzle. Understanding the mechanics before acting often reveals more than a long sequence of trial-and-error moves.
3. Compare the Start and Goal
If the start and goal have different invariant values, the puzzle is impossible under the stated rules.
If their values match, the puzzle may be solvable—but parity alone does not always prove that it is. Think of parity as a locked-door detector: it can show that entry is impossible, but an unlocked door does not guarantee that the route beyond it is clear.
The Checkerboard Puzzle: A Visual Parity Proof
Consider a standard 8-by-8 checkerboard. It has 32 dark squares and 32 light squares. Now remove two diagonally opposite corners and try to cover the remaining 62 squares with 31 dominoes, each covering two adjacent squares.
At first, success seems plausible:
- There are 62 uncovered squares.
- Each domino covers two squares.
- Thirty-one dominoes cover exactly 62 squares.
The total area works—but the color count does not.
Adjacent checkerboard squares always have opposite colors, so every domino must cover one dark square and one light square. However, diagonally opposite corners have the same color. Removing both leaves 30 squares of one color and 32 of the other.
Thirty-one dominoes would cover 31 dark and 31 light squares, so the board cannot be tiled. Stanford computer scientist John McCarthy used this classic mutilated-checkerboard argument as an example of a simple counting proof that can be unexpectedly difficult to reproduce through general automated proof procedures.
The lesson is important: matching the total area is not enough. A hidden two-color balance can make a tiling impossible.
This method becomes easier with strong spatial awareness. Practicing visualization in tiling and block-based games can help you notice how pieces interact with colored regions before you begin placing them.
How Parity Controls the 15-Puzzle
The classic 15-puzzle contains fifteen numbered tiles and one blank space in a 4-by-4 frame. A legal move slides a neighboring tile into the blank.
It appears that enough sliding should eventually produce any arrangement. In reality, only half of all possible arrangements belong to the same reachable class as the solved board.
To test a position, read the numbered tiles from left to right and top to bottom, ignoring the blank. Then count inversions. An inversion is a pair of tiles that appears in the wrong numerical order.
For example, consider this nearly solved final row:
13, 15, 14, blank
The pair 15, 14 creates one inversion because 15 appears before the smaller number 14.
For a standard 4-by-4 puzzle:
- Count the inversions.
- Count the blank’s row from the bottom, starting with 1.
- Add the two numbers.
- The position is solvable when the sum is odd and unsolvable when it is even.
In the example, there is one inversion and the blank is in row one from the bottom. The sum is two, which is even, so the position cannot be solved through legal slides.
Why does this work? A horizontal slide preserves both the inversion parity and the blank’s row. A vertical slide changes the inversion parity while also moving the blank between an odd and an even row. The two changes occur together, so the parity of their sum remains fixed.
The rule differs slightly on sliding puzzles with an odd number of columns. In that case, a position is reachable from the standard goal only when the inversion count is even. The important strategy is to use the solvability rule designed for the board’s dimensions rather than applying the 4-by-4 formula everywhere.
Alternating Colors Can Reveal Impossible Paths
Parity is also useful in path-drawing and movement puzzles. Color a grid like a checkerboard and notice what happens whenever a piece moves one square horizontally or vertically: it always switches color.
That creates an alternating sequence:
dark → light → dark → light
After an even number of moves, the piece finishes on the same color where it began. After an odd number, it finishes on the opposite color.
Suppose a puzzle demands a path of exactly ten single-square moves between two squares of opposite colors. Ten is even, so the path must end on the starting color. The requested path is therefore impossible, regardless of how many routes appear available.
A related test works for paths that must visit every square exactly once. On a board with equal numbers of dark and light squares, a path that alternates colors must use those colors in a tightly controlled order. Removing squares, fixing the endpoints or changing the board’s shape may create an imbalance that no route can overcome.
Common Parity Mistakes to Avoid
Parity is powerful, but it must be applied carefully.
Counting the Wrong Feature
The number of misplaced tiles may change unpredictably even when a different property—such as permutation parity—remains fixed. If your count can change between even and odd after a legal move, it is not an invariant.
Ignoring a Move Type
A rule is useful only if it accounts for every permitted move. If rotations, jumps or flips are allowed, test each one separately.
Treating a Necessary Condition as a Complete Solution
A matching parity means “not ruled out,” not automatically “solvable.” Other obstacles may still exist, including disconnected regions, piece-shape restrictions or additional invariants.
Forgetting the Exact Rules
Allowing one extra operation can completely change the answer. A sliding puzzle may be impossible when tiles can only slide, but immediately fixable if you are allowed to lift and swap two tiles.
Turn “I Can’t Solve It” Into a Proof
When a puzzle refuses to cooperate, the problem is not always your technique. The goal itself may be unreachable.
Pause and make a parity checklist:
- What can I count or color?
- What does each legal move change?
- Is that change always even, always odd or paired with another change?
- Do the starting and target positions have compatible parity?
- Am I proving impossibility, or only failing to find a route?
If you think you have discovered a universal rule, apply the counterexample test before trusting it. One legal move that breaks your proposed pattern means you need a better invariant.
Parity replaces frustration with certainty. Instead of saying, “I tried everything,” you can explain exactly why no legal sequence could ever work. That shift—from searching blindly to identifying what cannot change—is one of the most satisfying upgrades a puzzle solver can make.
