Masyu

Sample puzzle

Solution to above puzzle

Masyu (Japanese: ましゅ IPA [maʃɯ]; translates as "evil influence") is a type of logic puzzle designed and published by Nikoli. The purpose of its creation was to present a puzzle that uses no numbers or letters and yet retains depth and aesthetics.

Rules

Masyu is played on a rectangular grid of squares, some of which contain circles; each circle is either "white" (empty) or "black" (filled). The goal is to draw a single continuous non-intersecting loop that properly passes through all circled cells. The loop must "enter" each cell it passes through from the center of one of its four sides and "exit" from a different side; all turns are therefore 90 degrees.

The two varieties of circle have differing requirements for how the loop must pass through them:

• White circles must be traveled straight through, but the loop must turn in the previous and/or next cell in its path;
• Black circles must be turned upon, but the loop must travel straight through the next and previous cells in its path.

History

The early version of Masyu first appeared in Puzzle Communication Nikoli #84 under the title of Shinju no Kubikazari (真珠の首飾り, meaning "pearl necklace"). That puzzle contains only white circles. Black circles were introduced in Puzzle Communication Nikoli #90, and the puzzle was renamed Shiroshinju Kuroshinju (白真珠黒真珠, meaning "white pearls and black pearls"). This improvement deepened the puzzle and made it gain popularity. Masyu, which is originally a misreading by Nikoli's president of kanji 真珠 (shinju), and apparently became an inside joke at the Nikoli office, was adopted in Puzzle Communication Nikoli #103 to replace the old lengthy name.

Solution methods

Understanding the nuances of the circles and how they interact with each other is the key to solving a Masyu puzzle. Generally speaking, it is easiest to start along the outside border of the grid and work inwards. Here are some basic scenarios where portions of the loop can be determined:

• Any segment travelling from a black circle must travel two cells in that direction without intersecting another part of the loop or the outer border; each black cell must have two such segments at a right angle. The logical combination of those two statements is that if a segment from a black cell cannot be drawn in some orthogonal direction, a segment in the opposite direction must be drawn. For example, if one cannot legally travel up two cells from a black circle, then the loop must travel down from that black circle for two cells. This has two common results:
  • Any black circle along the outer border or one cell from the outer border must have a segment leading away from the border (and those sufficiently near a corner must lead from both walls, defining the loop's path through the circle);
  • Orthogonally adjacent black circles must have segments travelling away from each other.

• White circles along the outer border obviously need the loop to travel through them parallel to the border; if two white circles along a border are adjacent or are one cell apart, then the loop will need to turn away from the border just beyond the circles.

• If three or more white circles are orthogonally contiguous and collinear, then the loop will need to pass through each of those circles perpendicular to the line of circles.

• If two white circles are orthogonally contiguous and a cell on either end has a loop segment entering parallel to the line of the circles, then the loop will need to pass through each of those circles perpendicular to their line. (Otherwise, the line through them would connect to the adjacent segment and one of the white cells would not be next to a turn in the loop.)

As in other loop-construction puzzles, "short circuits" also need to be avoided: as the solution must consist of a single loop, any segment that would close a loop is forbidden unless it immediately yields the solution to the entire puzzle.

Like many other combinatory and logic puzzles, Masyu can be very difficult to solve; solving Masyu on arbitrarily large grids is an NP-complete problem.^[1] However, published instances of puzzles have generally been constructed in such a way that they can be solved in a reasonable amount of time.

See also

• List of Nikoli puzzle types

References

1. ^ Erich Friedman. "Pearl Puzzles are NP-Complete". In preparation. 2002. [1].

External links

• Masyu page at Web Nikoli
• Father of Sudoku puzzles next move BBC