Masyu
Masyu (ましゅ Mashu, IPA [maɕu͍]; translates as "evil influence")[1]) 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.[1]
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.
Variants
- There are additionally or solely gray circles. The solver has to find out which of these gray circles are white and which are black.
- The diagram is a Toroid; i.e. the left and the right edge of the diagram as well as the top and the bottom edge of the diagram are glued together.
- The diagram is divided into regions; the loop must turn in every region at least once.
- The diagram is played on a hexagonal grid, with grey circles indicating 60-degree turns where the loop turns both before and after the turn, and black circles indicating 180-degree turns where the loop goes straight on the cells before and after the turn.
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.
- Black circles that are orthogonally next to the end of the loop that does not travel towards it must have the loop heading away from the other loop segment.
- 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.)
- A black circle with two white circles diagonally adjacent on the same side must have the loop heading away from that side. If not, and it went between the white circles instead, then the white circles would be parallel to that section of the loop, and make it impossible to complete the black circle.
- Black circles with three white circles diagonally adjacent can be fully completed by this rule.
- If the diagram is cut virtually into two pieces, the loop must cross the cutting line an even number of times. This is due to the Jordan Curve Theorem.
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.[2] 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
References
- 1 2 Knuth, Donald (2011), "Nikoli puzzle favors", Selected Papers on Fun & Games, CSLI Publications, pp. 473–476.
- ↑ Erich Friedman. "Pearl Puzzles are NP-Complete". In preparation. 2002. .