Starpath Glossary: Path Puzzle Terms and Definitions

The sky

Sky: Starpath’s board: an 8×8 grid of 64 tiles. Other path puzzles call it the grid.
Tile: One square of the sky. The finished trail uses every tile exactly once. Also called a cell or a square.
Star: A tile marked with a number from 1 to 12. The trail starts on star 1 and must reach the others in order.
Waypoint: The general name for a numbered tile that a path must pass in order. Starpath’s stars are waypoints. Also called a checkpoint or a clue.
Barrier: A dark bar on the edge between two tiles. The trail can’t cross it and has to go around. Other puzzles call it a wall.
Neighbor: A tile that shares a side with another. A tile in the open has four neighbors, a tile on the edge of the sky has three, and a corner has two.
Open neighbor: A neighbor the trail could still step to: one that isn’t behind a barrier and hasn’t been used by another part of the trail.
Orthogonal: Up, down, left or right. Every step of the trail is orthogonal, so diagonal moves are not allowed.

Trail: The single line you draw from star 1 across the whole sky. Also called the path or the route. It never crosses or overlaps itself.
Step: One move of the trail from a tile to an orthogonal neighbor. A finished trail on 64 tiles has 63 steps.
Leg: The stretch of trail between two consecutive stars, such as 3 to 4. Twelve stars make eleven legs.
End: The first or last tile of the trail. An end touches the trail on one side only, where every other tile has the trail entering and leaving. Also called an endpoint. The trail starts on star 1, and each day’s sky is built to finish on star 12.
Detour: A leg that takes a longer way than the shortest route between its two stars, to pick up tiles that no other leg can reach.
Trim: To shorten the trail by going back to a tile it has already visited. Everything drawn after that tile is removed.
Undo: Takes back the last step of the trail.
Hint: Extends the trail along the correct route. Hints count toward the daily result.

Forced tile: A tile with only two open neighbors, because it sits in a corner or against barriers. The trail must use both, so you can draw those two links at once.
Corner: One of the four tiles at the corners of the sky. A corner has two neighbors, so unless the trail starts or ends there it is always a forced tile.
Dead end: A tile with only one open neighbor. The trail can enter it and never leave, so it has to be an end of the trail.
Corridor: A passage one tile wide, made by barriers or by the edge of the sky. The trail has to walk straight through it, in one end and out the other.
Pocket: A group of unused tiles that the trail has walled off. A pocket with no way in and out can never be filled.
Stranded tile: An unused tile the trail can no longer reach. One stranded tile means the trail went wrong somewhere earlier, so trim back and try another way.
Checkerboard coloring: Imagining the tiles colored alternately dark and light, like a chessboard. Every step of the trail moves from one color to the other.
Parity: Whether a count is odd or even. With checkerboard coloring, two stars on the same color are an even number of steps apart and two on different colors an odd number, which shows when a short leg has to wander.

Number path puzzle: A puzzle in which the numbers 1, 2, 3 and so on must form one unbroken chain through every cell of a grid. Starpath is one with most of the numbers left out.
Hamiltonian path: A route that visits every point of a network exactly once. A finished Starpath trail is a Hamiltonian path on the tiles of the sky. Named after William Rowan Hamilton.
Hamiltonian cycle: A Hamiltonian path that finishes next to where it started, so it can close into a loop. Also called a Hamiltonian circuit. A Starpath trail does not have to close.
Knight’s tour: A sequence of knight moves that lands on every square of a chessboard exactly once. It is the oldest known puzzle about visiting every square.
Grid graph: The mathematician’s name for a set of squares on a grid, joined where they share a side. It may be a full rectangle or have holes.
NP-complete: A class of problems for which no method is known that stays fast as the problem grows. Deciding whether a grid graph has a Hamiltonian path is NP-complete.