A puzzle guide may tell you to clear a piece's footprint, resolve a linear conflict, or compare states. This glossary explains those terms with examples from Classic Slide, Orthogonal Slide, and other Puzzuzu games.
Start with board and movement terms, then strategy and distance, or jump to search algorithms. You do not need the algorithm terms to play; they help explain what a computer solver is doing.
Board and movement
Blank or empty space
An unoccupied cell. In a standard sliding-tile puzzle, moving a tile into the blank leaves a new blank where the tile started. Tile movement and blank movement therefore point in opposite directions.
Legal move
An action allowed by the puzzle's rules in the current position. In Classic Slide, a tile next to the blank can slide into it; a diagonally adjacent tile cannot. In Orthogonal Slide, the cells a piece moves into must be clear. A legal move need not bring you closer to the goal.
Orthogonal
At right angles. On these square-grid boards, orthogonal movement follows a row or column, so pieces move up, down, left, or right. Cells that touch only at a corner are diagonally adjacent, not orthogonally adjacent.
Piece footprint
The set of cells occupied by a piece. A 2×2 block occupies four cells. To move it down one row, the two cells just below it must be empty; the upper half of its new footprint overlaps cells it already occupies.
See the Orthogonal Slide guide for the moves that prepare this opening.
Polyomino and tetromino
A polyomino is a shape made from equal squares connected edge to edge. A tetromino has exactly four squares. A 2×2 square and an L made from four squares are tetrominoes; a three-square L and a five-square rectangle are not. Having right-angled edges alone does not make a piece a tetromino. Wolfram MathWorld's polyomino reference describes the family.
Queue puzzle
A puzzle built around one or more ordered lines of pieces. A standard queue follows first in, first out, abbreviated FIFO: the earliest item still in the queue is the next to leave. Each game sets its own rules for moving pieces between queues. Sequence Queue is Puzzuzu's example.
Sliding puzzle
A puzzle solved by moving pieces through available space on a board. Classic Slide requires a complete tile arrangement. Orthogonal Slide uses blocks of different shapes and specified target destinations. Similar-looking boards can therefore have different goals.
Stack puzzle
A puzzle whose pieces occupy stacks. A standard stack follows last in, first out, abbreviated LIFO, so only the top item is removed next. Tower of Hanoi adds a size rule to its stacks, while Ball Stacks uses its own placement rules.
State and state space
A state records everything needed to determine the puzzle's legal next moves and whether it is solved. On a sliding board, that includes the positions of all pieces and empty cells. In another game it may also need an orientation, a turn, or another rule-dependent value.
The state space is the collection of possible states. Imagine connecting two states whenever a legal move takes you from one to the other; a solver can search those connections for a route to the goal. Some arrangements may look valid but cannot be reached from your starting state.
Strategy and distance
Backtracking
Returning to an earlier decision and trying a different option when an approach fails. A player might undo several moves and take a new route. A constraint solver might remove a tentative tile placement and try another tile. If you make the same choice again, you will reach the same dead end.
Heuristic
An estimate used to guide a search. In a sliding puzzle, the number of misplaced tiles is one possible estimate of the work remaining. A heuristic helps compare positions; it does not necessarily describe legal moves or guarantee a solution. Some useful estimates deliberately ignore obstacles.
Manhattan distance
The horizontal distance plus the vertical distance between two grid cells. A tile two columns right and one row below its goal has Manhattan distance 3. Diagonal shortcuts do not count.
For the standard sliding-tile puzzle with one tile moving one cell per move, sum the distances of all numbered tiles and omit the blank. This is a lower bound on the moves remaining, because arranging the blank and moving around other tiles can require extra work. The interpretation changes if a game counts a long slide or several tiles as one move. See Princeton's sliding-puzzle examples.
Linear conflict
Two tiles belong in the same row or column but appear in the reverse of their goal order. They cannot pass each other within that line, so at least one must leave it and return. For one such pair in the standard sliding-tile move model, that detour costs at least two moves beyond the tiles' Manhattan distances. When several pairs overlap, a solver must avoid counting the same required detour repeatedly.
The Classic Slide guide shows the coaching overlay and explains how to use the unfinished area to separate a conflicting pair.
Optimal solution
A solution with the lowest cost under a stated measure, usually the fewest moves. To compare solutions, you need to know what counts as one move. A single-cell slide and an uninterrupted multi-cell slide may be counted differently. Several solutions can tie for the fewest moves.
A method that reliably solves a puzzle need not be optimal. Classic Slide's layer-by-layer method is intended to be manageable for a person, without promising the smallest possible move count.
Parity and inversions
Parity means whether a count is even or odd. An inversion is a pair of numbered tiles appearing in reverse goal order when the board is read row by row, omitting the blank. In 2, 1, 3, the pair 2 and 1 contributes one inversion.
Sliding-puzzle solvability depends on an invariant involving inversion parity and, for even-width boards, the blank's row. The Classic Slide solvability section gives the rules for an ascending goal with the blank at bottom right. Do not apply a rule for that goal unchanged to a different target arrangement.
Search algorithms
A* search
A search algorithm that chooses which state to explore next using f(n) = g(n) + h(n). Here, g is the cost of reaching that state and h estimates the cost remaining. A* chooses a state with the lowest combined value. Whether it finds a least-cost solution depends on the estimate and how the search handles previously seen states. UC Berkeley's informed-search notes explain the conditions.
Admissible heuristic
An estimate that never exceeds the true minimum cost to reach the goal. This property helps A* find an optimal solution. If the search keeps a record of states it has already explored, it must also handle a cheaper route to a recorded state correctly. One way is to use a consistent heuristic; another is to revisit that state when a cheaper route appears.
Branch and bound
An optimization method that keeps the best complete solution found so far and discards branches whose bounds show they cannot improve it. If a solution costs 20 moves and a branch needs at least 22, that branch cannot give a shorter answer. The bounds must be valid for the pruning to be safe.
Branching factor
The number of successors available from a state, sometimes averaged across a search. In the standard sliding-tile puzzle, a blank in an interior cell has four neighboring tiles that can move; a corner blank has two. A search may exclude an immediate reversal, leaving fewer successors to explore.
Breadth-first search (BFS)
Search that visits states at one move depth before the next. With equal-cost moves, it finds a solution using the fewest moves, if one is reachable in a finite state space. It can require substantial memory to keep the frontier and visited states. With unequal move costs, the shallowest solution need not be cheapest. UC Berkeley's uninformed-search notes compare these cases.
Constraint satisfaction problem (CSP)
A problem expressed as variables, their possible values, and constraints restricting which combinations are allowed. In Tetravex, a board position can be a variable, candidate tiles are its possible values, and neighboring edges must agree. A solver can remove incompatible possibilities before trying assignments. See UC Berkeley's introduction to CSPs.
NP-hard
A formal complexity classification. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. It does not mean that every instance is difficult, that solutions are impossible, or that no fast algorithm could ever exist. Claims about puzzle complexity need to specify the generalized problem and what is being asked, such as finding a solution or finding a shortest one. A fixed small board is not a useful measure of that distinction. NIST's definition of NP-hard gives the formal terminology.
Try reading one move in Classic Slide in these terms. Identify the current state, name a legal move, and describe how the blank and the moving tile change position. Then compare that move with the whole-footprint check in Orthogonal Slide.