Masyu and Mathematics

Masyu as a graph problem

Treat each cell as a vertex and each pair of side-by-side cells as an edge. An n×n grid has n² vertices and 2n(n−1) edges — a 10×10 Masyu has 180 possible line segments. A solution picks a subset of edges forming a single cycle:

• every vertex has degree 0 or 2 (the two-line rule);
• the chosen edges are connected (one loop, not several);
• every pearl vertex has degree 2, plus the local shape conditions for black and white pearls.

Without the pearls, this is close to a classic question: finding a cycle that visits every vertex of a grid graph (a Hamiltonian cycle). Itai, Papadimitriou and Szwarcfiter showed in 1982 that the Hamiltonian path problem on general grid graphs is NP-complete — a hint that loop puzzles on grids are computationally rich.

Why every loop has even length

Colour the grid like a chessboard. Each step moves to the opposite colour, so to return to the start you must take an even number of steps. In graph terms the grid is bipartite, and bipartite graphs contain only even cycles. A Masyu loop therefore always visits equally many light and dark cells. See checkerboard colouring for how solvers use this.

The Jordan curve theorem

The Jordan curve theorem says a simple closed curve in the plane divides it into an inside and an outside. A Masyu loop is such a curve. Two practical consequences:

• Any boundary you draw is crossed an even number of times — the parity rule.
• Every cell not on the loop is unambiguously inside or outside it. Some related puzzles, such as Castle Wall, make this inside/outside status part of the clues.

Masyu is NP-complete

In the paper “Pearl Puzzles are NP-complete”, Erich Friedman proved that deciding whether an arbitrary Masyu puzzle has a solution is NP-complete. Informally: checking a proposed solution is fast, but no known method finds solutions to every huge puzzle efficiently, and a fast general method would solve thousands of other hard problems at once.

That doesn’t make everyday Masyu hard. Published puzzles — including all of ours — are deliberately constructed so that human-style logic reaches the solution without search. NP-completeness is about the worst case over all possible puzzles, not the puzzles people actually enjoy.

The uniqueness question

Well-made puzzles have exactly one solution. Checking that is a separate problem from solving: given one solution, is there another? Researchers including Takayuki Yato and Takahiro Seta have studied the complexity of this “another solution problem” for pencil puzzles, which is one reason puzzle setters rely on careful logic — or computer checking — to guarantee uniqueness.

How computers solve Masyu

Our own Masyu solver combines three classic ideas:

1. Constraint propagation. Every edge is line, no line or unknown. Rules at each cell and pearl are applied repeatedly until nothing changes — the same deductions described in our strategy guide.
2. Lookahead. For each unknown edge, try both values and propagate. If one leads to a contradiction, the other is forced. This is exactly the human what-if method, and it’s how we define our Hard level.
3. Backtracking search. When logic stalls, branch on an edge and search both possibilities, stopping after two solutions — enough to prove a puzzle isn’t unique.

Other approaches encode Masyu for general-purpose SAT or integer-programming solvers, which handle very large grids well.

How puzzles are generated

Our generator grows a random loop, places pearls where the loop’s shape allows them, then adds and removes pearls under the solver’s supervision until exactly one solution remains and the required logic matches the target difficulty. The details are on our about page and in how to make Masyu puzzles.

Further reading

• Erich Friedman, “Pearl Puzzles are NP-complete”.
• A. Itai, C. H. Papadimitriou and J. L. Szwarcfiter, “Hamilton Paths in Grid Graphs”, SIAM Journal on Computing (1982).
• T. Yato and T. Seta, “Complexity and Completeness of Finding Another Solution and Its Application to Puzzles”.
• Masyu — Wikipedia