Jeffrey Bosboom's Blog

[blog] [projects] [about]

Review and analysis: LYNE

LYNE is a route and cover game played on king’s graphs (the graphs on an integer lattice where each vertex is connected to every vertex a king’s move away), possibly containing holes. Each vertex is a triangle, square, diamond or hexagon. Triangles, squares and diamonds (“colored” nodes) each have two designated terminal nodes which must be connected by a path through all other nodes of that color and possibly some of the hexagon nodes. Hexagons do not restrict color, but must be included in paths a number of times equal to the number of pips on that hexagon (two, three or four). Each edge may only be part of one path and crossing (diagonal) edges cannot both be in paths.

LYNE includes quite a few puzzles: 26 sets of 25 puzzles each, plus between one and three sets of daily puzzles which increase in difficulty throughout the week in the crossword tradition. Typically two or three sets are available for play at any one time, but unlocking a new set requires fully completing a previous set – so you can still get stuck at 24 of 25 in your three current sets.

LYNE saves your progress after every puzzle, which is good because 25 puzzles turns out to be a tedious number to solve in a single sitting. While some inferences can be made using rules described below, puzzles are not solvable through inference alone. In practice, interface limitations prevent making effective use of inference. The interface requires tracing from one terminal to another, with no option to mark out middle parts of the path early. There’s also no provision for marking edges as unused or tracking which colors are possible on an edge. Due to these interface limitations, I solved most of my puzzles by trial and error, and once that process started taking too long, I moved on to automation.

Single-color LYNE is NP-complete

Even with a single color, LYNE is NP-complete. LYNE is played on a king’s graph, but the graph may contain holes. If the graph has holes in a checkerboard pattern (no two vertices horizontally or vertically adjacent), it’s a grid graph rotated 45 degrees, and if there are any more holes, the grid graph also has holes. Hamiltonian path with designated start and end vertices on grid graphs with holes is NP-complete. LYNE contains this problem as the special case in which all nodes are of a single color, where the terminal nodes are the designated start and end vertices (interchangeable in an undirected graph), so LYNE is also NP-complete.

Admittedly, this reduction does not seem to capture the challenge of actual LYNE puzzles intended for play by humans. In my experience with the game, the challenge derives mostly from the hexagons, suggesting a planar 3SAT reduction with two colors representing true and false, one of which must connect through hexagons in each clause gadget, where the whole gadget can be covered only if the true color makes it to the hexagons. My attempts at such a reduction have been stymied by the connectedness of king’s graphs, so the resulting graph will probably still be very sparse relative to actual LYNE puzzles.

lynebot

lynebot is a bot that automatically solves LYNE puzzles. lynebot tracks the possible colors on each edge (triangle, square, diamond or none), applying local inference rules to eliminate or force colors. When the local rules cannot make progress, the bot begins a backtracking search, choosing one of the edges with the fewest possible remaining colors and setting it to each possibility in turn. When all edges have been assigned colors, the bot enumerates the possible paths to check if they cover all nodes and connect the terminals.

This is a backtracking search and so has exponential time in the worst case, but it solves nearly all puzzles in LYNE’s level sets in under a second, such that the two-second animation of solved puzzles sliding off to the left to be replaced by a new puzzle on the right is the rate-determining step when solving a level set.

All of lynebot’s inference rules are local to a node or edge. In some puzzles, it’s possible to eliminate some edges by reasoning about paths in the graph. For example, considering the subgraph of all nodes of one color and hexagons, if a colored node is an articulation point in the graph and both terminals are in the same biconnected component, none of the edges in the other component can be in the path, as the path could not return to the second terminal. I have not bothered with these additions because lynebot is already working well, but they may provide insight relevant to a more natural hardness proof.