Masyu is a type of logic puzzle

Logic puzzle

A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...

 designed and published by Nikoli

Nikoli

Nikoli Co., Ltd. is a Japanese publisher that specializes in games and, especially, logic puzzles. Nikoli is also the nickname of a quarterly magazine issued by the company...

. 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

Degree (angle)

A degree , usually denoted by ° , is a measurement of plane angle, representing 1⁄360 of a full rotation; one degree is equivalent to π/180 radians...

.

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

Kanji

Kanji are the adopted logographic Chinese characters hanzi that are used in the modern Japanese writing system along with hiragana , katakana , Indo Arabic numerals, and the occasional use of the Latin alphabet...

 真珠 (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

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 problem. However, published instances of puzzles have generally been constructed in such a way that they can be solved in a reasonable amount of time.

External links

• Masyu page at Web Nikoli
• Father of Sudoku puzzles next move BBC
  BBC
  The British Broadcasting Corporation is a British public service broadcaster. Its headquarters is at Broadcasting House in the City of Westminster, London. It is the largest broadcaster in the world, with about 23,000 staff...