Ask Dr. Sudoku #5 – On the Parity of Loops

0 Flares 0 Flares ×

Fifth in a series with puzzle solving tips. This time, with some advice on global constraints that arise in loop puzzles.

Some of you have asked why I don’t put “general tips” up before I post any puzzles. I find that learning how to solve puzzles is more interesting than reading how to do every single step. I won’t post a list of the top 20 Slitherlink patterns you should memorize, for example, on the rules and info page. Most of you would probably get more enjoyment figuring those out for yourself. But, after you’ve solved a challenge, I do like highlighting some of the things as constructor I tried to include, perhaps as a lesson for the future. This is what I will do this week with parity constraints for the Friday Masyu.

Basic Masyu steps, particularly regarding black circles and edges, will get you to this state. There is one more extra line drawn, from the black circle highlighted in yellow. Notice that if this connection went up instead of down it would immediately close a loop. This is the most basic loop closure step to observe in this kind of puzzle and should become close to automatic with practice.

Now we get to see loop parity at work. The general idea is that until you’ve made all the connections, in any isolated region there must always be an even number of loose ends. When it looks like you will strand an odd number of ends, you have a problem. And when you have to choose between ends to enter into a region, you must always choose the end that will still let you form a single loop and not two or more loops.

Consider the lower-right region highlighted in yellow in the next figure. There is one end, A, already in there. There are three other ends, B, C, and D, that can reach into the region. To have a single loop, either 2 or 4 of these ends must connect into the yellow space. This is the basic parity constraint.

Notice that both C and D cannot get to yellow, as if D goes to the right it blocks C, and if C goes down it blocks D. So there are only 2 and not 4 ends that reach into yellow. Now you have to choose against the end that will give you more than one loop. Since C is connected to A, it cannot be the extra end in the yellow region. Draw a vertical connection from C up (as shown in red). This deduction will lead to a lot more progress.

Basic Masyu steps get you to this next stall point. Again, parity is important but in a slightly different way. Here you need to create a new strand to restore parity. Notice how in the yellow region there are just 3 ends. There must be another end that gets into this box. Not knowing how it connects yet, you can still deduce there is a line in red going up to the top-left corner. Continuing that connection to the top-middle of the grid will lead to the final connections needed to complete the puzzle.

While there are far harder observations about parity that come up in loop puzzles, even these simple ones can slow a majority of solvers who aren’t very familiar with them. Sure, bifurcation/guessing could have gotten you through this 10×10 puzzle, but on a larger puzzle you won’t want to go so far down a guessing path when “simple” deductions about parity can give you significant progress.

  • skynet says:

    I got to understand parity after seeing this walkthrough though i was using it in a different way ..I was finding whether seperate loops would be formed say if this end connects to this end ..Then i would eliminate that connection.
    This parity thing is a more polished way of looking at connecting ends.
    Good walkthrough!!

  • Jack Bross says:

    On the question of general tips, I do think it can be hard to find the right balance. I definitely agree that you have to work through the basic logic of a puzzle before any “standard tricks” really make sense and sink in. But I also think there is a difference between a broadly experienced solver running into a new puzzle type, and somebody who has only ever solved a few sudoku running into a new puzzle type. For complete novices, I think it’s always helpful to try to give general principles of how the logic tends to work, what to look for, and so on. That can include simple things like “in a consecutive sudoku, the places where there aren’t any marked borders are as important as the places where there are” or “mark both confirmed white space as well as shaded space” (in nurikabe, cave etc.). A more experienced solver is going to have a rough idea how the logic ought to work in a new type without any hints.

    • Para says:

      Part of the fun of puzzling is also discovering things for yourself. We all at one point started by opening a puzzle booklet, reading the rules and trying to figure out what to do to solve a puzzle. It would be easier for someone just explain every detail. But in my mind it’s much more useful to discover the basics by yourself. Sometimes there’s some harder steps that are hard to pick up on, which are good to be explained if you don’t see them.

      • pafcio says:

        I agree with you completely. Unfortunately, not many people are delighted that every problem is solved by them. Thomas is doing a very good job in promoting the puzzle – for those who do not necessarily want to own very deeply penetrate

  • Trayton says:

    If a solver wants to read the basic steps, I recommend they check out Wikipedia. Both the Masyu and Slitherlink are excellent examples that enumerate the simple axioms of the puzzles (especially the latter). I enjoy the “Ask Dr. Sudoku” posts that dig into the next steps. Puzzles 102, if you will, for this introduction period.

    P.S. I hope the links are formatted properly.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.