?

Log in

No account? Create an account
 
 
19 August 2011 @ 12:15 am
Friday Puzzle #115 - Loop the Loops  
This is part 9 of a "Better Know the USPC" preview series. The United States Puzzle Championship is scheduled for August 27th, 1PM EDT.

Type: Loop puzzles (specifically Masyu and Slitherlink)


USPC History: Loop puzzles in various forms have appeared basically every year of the test (often two or more per year). Early tests featured fun types like Hexasperation, a hex loop puzzle which is sort of like a minesweeper loop with limited neighboring cell occupancy from given numbers (not be confused with the actual Minesweeper Loop in 2003 that had minesweeper clues independent of the loop step). More recent tests have had simple loop puzzles like Round Trip and Yajilin pretty frequently. This entry focuses on two recurrent types that pack a bit more challenge and intrigue than those: Masyu and Slitherlink.

Slitherlink puzzles have appeared in 1999 (PuzzelSport), 2001 - with large boxes (M. Rios), 2002 - with large boxes (D. Tuller), 2005 - with false number gimmick (M. Rios), 2006 - with large boxes (D. Tuller), 2008 - with sheep (D. Tuller), 2009 - with sheep and wolves (D. Tuller). In 2007 a close-to-fences variation (Fenceposts) was presented from C. Kasper.

Masyu is a more recent puzzle type, but has made a yearly appearance since 2007 with no signs of stopping. 2007 and 2008 were by D. Tuller, 2009 and 2010 by Nikoli. In 2008 a close-to-Masyu variant, Black Pearl, was written by A.R. Wood. 2010 also brought a Hex Masyu from D. Tuller.

Notation tips:
Both of these puzzles mostly involve drawing sure line segments into the grid but a few extra marks are helpful. In Masyu, the only major extra marking that I find useful arises when you know a line segment must turn after passing through a white circle; to block off the straight extension, I tend to darken the edge to make a wall, but an x through the impassable space would work too.

In Slitherlink, the most specific tip from my notation is something that arises from more advanced strategies that consider diagonally connected clues. Each "point" in the grid is used by either 0 or 2 line segments. Sometimes you can identify a spot where a point must be used (such as the corners of a 2 diagonally adjacent to a 0), but it is used exactly once by the edges of that square. The other line segment must be in the diagonally adjacent square. There are three situations here: if this square contains a 3, I'll draw in 2 sure segments in the opposite corner. If it points to a 1, I'll x-out the 2 opposite corner segments that are now dead. If it is a 2 or a blank, I'll draw a diagonal segment through the point to indicate the two single-linked squares with as yet undefined edges, and in the case that it is a 2, I will then go to that square's opposite corner (which must now also be a single-use point) and repeat this process heading out to the next diagonally adjacent square. I'll also occasionally draw a diagonal line through a 2 that is one of two specific wraps around that cell, especially on a puzzle with a lot of these stacked on each other so that I can visualize the loop as it passes through these spaces. (Advanced solver note: Uniqueness can often be applied with care in these situations depending on what surrounding clues look like. Consider a 2 isolated in a corner with no clues in any adjacent cell. If the puzzle has 1 answer, what must that corner look like?)

The last critical rule in both puzzles is to "form a single closed loop." With smaller grids, I have a pretty good ability to grasp all the segments and see if I've achieved this (or am coming close to having two ends intersecting). But when the grid is 20x20 or larger, I'll often quickly shade the inside of the loop as I'm going to keep track of this better by seeing inside and outside. Enclosing any shaded space (or any white space inside of that) is not allowed until the very last link you draw. With some of the Slitherlink variations, particularly the ones that involve animals, the inside/outside shading is pretty essential, and having a second notation like circling the cell when it is outside is useful to keep track of things.

Here is my solved grid from the 2008 slitherlink. Despite the shading, no animals were harmed during the making of this solution.

You'll find my notation is pretty minimal. I've certainly seen other solvers do a lot more though. Wei-Hwa Huang's default Slitherlink style involves building what I'd call an inner/outer mesh with perpendicular segments crossing all unused links, eventually marking out bricks that define the inner and outer spaces at the same time as drawing the loop. I wish I had a picture to show to give it justice, but I can appreciate its utility on some puzzles. It just has a lot more writing than I like to do. As with the other topics, there probably is no "best" approach. I can just tell you what I do as a starting point for your own experimentation to find what works best for you.

Strategies:
While there are many topological requirements that arise in these puzzles, the strategies I'll share with you will have much less of a math focus and more of a practical puzzle-solving focus. For either Masyu or Slitherlink I can group these into the following categories:
(1) near edges/corners
(2) between touching clues
(3) between diagonally adjacent clues
(4) meta - mostly "do not close the loop".

(1) and (2) are the most obvious starting points on either puzzle type. In a masyu, white circles on the border or black circles on or one off the border have some forced segments just from considering the edge of the grid. Equivalently, certain small adjacent patterns anywhere will have forced segments. Two adjacent black circles have two long segments radiating outwards from them. Three (or more) adjacent white circles must be crossed by three (or more) parallel lines, not one single line. Other common patterns exist and you should note them when you see them as they might turn up again.

In a slitherlink, the simplest place to start building your pattern database is in the very corner where there are obvious segments or unused paths to draw if a 0, 1, 2, or 3 are there. The 1 and 3 actually draw segments in that cell and imply a connection into the diagonally adjacent cell. The 2 doesn't draw any segments in the corner cell itself yet but it does draw two extending segments on the border in the adjacent cells. Note that this corner situation is duplicated anywhere inside the grid that a 0 is diagonally adjacent to one of these numbers. Other simple patterns include a 0 next to a 3 (or a 0 next to a 2 on an edge), adjacent 3's with two possibilities, and such should be gimmes for you. While memorizing common patterns will get you quicker on some puzzles (particular Nikoli's), and you can find some pages online (even Wikipedia) with many drawn to add to your arsenal, I am not going to list them all here as memorizing two dozen things is not going to get you through all the hurdles you will hit.

What is more useful in my opinion is to start to appreciate where and why loops get constrained. Take a 313 on an edge. This is a memorizable pattern. But it should also be quickly derivable if you don't know it. 3's have only 1 missing edge, so this is either the edge on the 1 or it is not. If it shares an edge with the 1, the other 3 cannot. But that is really problematic. So neither 3 shares an edge with the 1. Get your head around how 3's have a lot of path and 1's very little path and you'll see why places they touch each other might be valuable to look at.

Even more valuable as you advance, in both puzzle types, is strategy area (3) - diagonally adjacent clues, which is where most solvers are weaker than they should be. In Slitherlink particularly, diagonally adjacent clues store a lot of information because of the parity of their corners. As stated above, each point is connected to 0 or 2 links. But when connected to 2 links, sometimes only 1 link can go into a particular square forcing one link into the diagonally adjacent square. When you know this single link is going to that square, you can mark 1's and 3's pretty easily. But you MUST see that 2's pass along the same single-link message through to the adjacent corner. If the lower-left corner of a 2 has exactly one link entering it, then the upper-right corner of that same 2 has exactly one link exiting it. This must be so, whichever of the four out of six total ways that 2 can end up being filled. So marking your diagonal links is essential, and recognizing usable/unusable links in those touching squares. Get good at this, and you'll be a lot better at Slitherlink than just a pattern memorizer will be. Although pattern memorization certainly helps.

Diagonally adjacent clues are underappreciated in Masyu as well. Diagonal clues, specifically those that contain at least one black circle, have a push/pull relationship with the clues around them. If a black circle extends towards a diagonally adjacent black circle, it pushes a new extension from that black circle in a perpendicular direction. More significantly, if a black circle extends towards a diagonally adjacent white circle, it pushes a parallel line in the white circle that pushes back and gives another line from the black circle. So I look at dense spots with such a white/black diagonal relationship when I can. If I see two whites near a black like this, even better. There are two such situations. If the whites are on the same side of the black circle, then the black does not extend between them. (This is probably the first "obvious" situation that is just uncommon enough that people don't recognize it quickly enough. The other is a black two cells removed from a double white.) On the other hand, if the two whites are on a shared diagonal with the black circle, then there are only 2 total ways the lines from the black circle can go (instead of the usual four) and either way forces a lot of line segments in the involved area. The 2007 USPC Masyu which was rated as "hard" by solvers after the test who were most familiar with more straight-forward Nikoli puzzles, forced solvers to (A) guess or (B) spot a contradiction at a white-black-white diagonal in the upper-left that had a rather dense set of circles around it. If you were prepared to look for those diagonals as problem spots, you would have been much more efficient at solving the puzzle.

As much as local clue thinking matters, btoh puzzles really solve a lot of the time based on strategy area (4) - don't close the loop. Until your last line segment, you should not have a closed loop anywhere in the grid. Masyu and Slitherlink puzzles often get into what I call the "chase" state, where two ends that cannot prematurely close are very close throughout the grid. Whatever you have to do to be aware of this state (observing the grid better, shading the inside of loops, labeling ends of shared segments with letters), get aware of this state. In addition to not closing the loop are "meta" steps that would lead to a problem of getting a single loop at the end. If drawing a segment that isolates a whole section of grid, be sure there is an even number of segments in this section as an odd number could never close. Even if you are stranding an even number of segments, be sure there are two connections back out that won't leave a second loop. The isolated section will almost always solve by starting from those two connection points and thinking about how to gather every remaining clue up before closing.

Finally, don't be afraid to get in the habit of lightly sketching an idea on the page and taking it one or two steps farther to learn why something isn't possible. Eventually you may learn to do this in your head, or to learn some of the patterns you don't know, but "seeing" a loop that will work, or will not work, will only start if you get used to seeing the loop on the page as it grows. I (re)learn patterns in puzzles all the time by drawing the contradictions. I think you can too.

Comments: These are my two favorite loop puzzles, with Masyu being a good "gateway" puzzle into Slitherlink. Masyu is usually pretty simple in comparison, but still has moments of surprising complexity for using only two kinds of clue. While a lot of the basic patterns can be picked up quickly, and almost all of the small puzzles will feel repetitive after enough time, Masyu masters like juno will come up with large challenges with new, repeated patterns that challenge your powers of deduction and recognition.

Slitherlink involves more clue variety and is typically more complex even with its reasonably simple rules. I've really enjoyed the different USPC variations I've seen with time, mostly the irregular grids and less with the ones where wolves started encroaching on the sheep (which inspired my own response puzzle here the following year). I must say that the many Even/Odd Slitherlink in the most recent WPC in Poland with absolutely no number clues made me appreciate the corner parity of these puzzles so much more (I already had most of the general rules in mind, but the Poles treatment took this to eleven and beyond).

My favorite practice sources for these two puzzles are the Nikoli Pencil Puzzle Book series, where I race to be at 50% the value of the expert Masyu time and 75% the expert Slitherlink time. Computer-generated puzzles will feel a lot different from these and some practice with them is recommended too. I've yet to find a square slitherlink generator that I enjoy, but the variable shapes on Croco-puzzle including hex are pretty good when they come up. And their computer-generated Masyu are certainly acceptable as well.

About this puzzle: I went back and forth a lot on whether to make a Masyu or a Slitherlink for the last week of this series. I eventually decided to merge the two. The result is a very tall puzzle with bits that are exclusively Masyu and Slitherlink and a middle section with elements of both. Solving a Masyu on dots instead of in cells may feel a bit different, but I hope you can adjust to the isomorphic presentation. This puzzle will probably be pretty challenging if you haven't solved a lot of the component puzzles, but hopefully it shows off some of the strategies I think you should know, some of the similarity of logic between the two types, and gives you an opportunity or two to visualize a new rule you've never seen before.



Loop the Loops
Rules:
Draw a single closed loop by connecting neighboring dots horizontally or vertically (but not diagonally).

Some numbers appear in the grid as clues; as in a Slitherlink/Fences puzzle, a numbered square indicates exactly how many of its four edges are used by the loop.

Some circles (either white or black) also appear in the grid as clues; as in a Masyu puzzle, the loop must pass through all of these circles. When passing through a black circle, the path must make a 90 degree turn and extend at least two dots in both directions. When passing through a white circle, the path must go straight and must turn at at least one of the adjacent dots.







Answer Entry: Enter the number of interior cells in all connected groups in each of the marked rows, reading from left to right and starting with the top-most marked row. For the example, the answer is 12,4.
 
 
 
Teesside Snog Monster: puzzlejiggery_pokery on August 19th, 2011 07:16 am (UTC)
I've thoroughly enjoyed this whole series; thank you for your generosity with your time in creating it and sharing it with us.
(Anonymous) on August 19th, 2011 09:15 am (UTC)
Yeah, agree. I particularly liked the penta piece (which I usually avoid as much as I can), but this puzzle was really nice too. I might be overinterpreting a bit here, but it seems that you worked hard to put as many techniques discussed in the post as possible into this puzzle, and I have to say it worked really well. We've got everything here: chases, less usual masyu patterns, diagonal reasoning, uniqueness (only if you want it :)), very well done.

Marcin
motrismotris on August 19th, 2011 02:36 pm (UTC)
I think with the Corral and with this puzzle I did the best at including the full mix of strategies as a "training" puzzle should probably have. Unfortunately in this case it made the puzzle extra large as it needed isolated and shared bits, but I suppose it could be a 25 or 30 pointer on the USPC as is.
robRobert Vollmert on August 19th, 2011 08:25 pm (UTC)
I agree, apart from the fun puzzles, it's really interesting to see how you go about these. Some useful hints on Slither Link notation (though mine is quite similar, lacking a bit with the 2s). The maze probably improved my technique most…
(Anonymous) on August 19th, 2011 08:20 pm (UTC)
Such a natural variant ...
... amazed we have not seen it before (other than a slight overlap of sorts seen in a MellowMelon 8 board megapuzzle once). Great fun, thanks.

As for loop puzzles, especially Slitherlink/Fences, I would love to see an overview of shortcuts. What I mean by that, if unclear, is what "givens" there are when certain numbers are juxtapositioned, such as 3 next to 0, 3 next to 3, 3 diagonal from 3, or things like 2 or 3 in a corner, etc. I assume that we all use such shortcuts to run through the earliest stages of any Slitherlink (to the point where MellowMelon did his famous 33 in the middle of a sea of 0's for a great groaner stumper), but no one ever shares them. While I have been around doing this for a while, I always think there must be a few I am missing to help move the puzzles along quicker. That would be a great extra piece for someone to do, and for others to add to.

p.s. Thanks for this great series. Great overviews, good refreshers and fun puzzles.

TheSubro
motrismotris on August 19th, 2011 09:40 pm (UTC)
Re: Such a natural variant ...
I can't claim originality for this meld (I first saw it on OAPC 8 two years ago from Serkan Yurekli, who had seen it from Nils Miehe in the German puzzle portal which I've never had time to dig into). But I do think I took the combination farther than others have done to make a neat puzzle that really uses both kinds of clues in different ways. This one has several combo-only work-ins in the middle that are only touching the surface of what this hybrid could contain. I'll certainly make more puzzles of this style in the future.
Adam R. Woodzotmeister on January 25th, 2012 02:58 pm (UTC)
Re: Such a natural variant ...
I'd like to add my claim for originality, dating back to March 15, 2005 for a superset of this variant. - ZM
Deb MohantyDeb Mohanty on August 20th, 2011 06:15 pm (UTC)
Great series
Thanks so much for the great series. Wonderful write ups and great set of puzzles (as usual).

Good Luck for USPC.
insane_bassist on August 25th, 2011 04:38 am (UTC)
This was a super fun puzzle. I'm practicing for my first USPC. I'm pretty much screwed this year around, but it'll be good practice for later years. All I know is I'm having a ton of fun doing puzzles like this; they are much more interesting than the puzzles I have done in the past, like plain Slitherlink without these twists. So thanks for the fun and practice :D
motrismotris on August 25th, 2011 02:51 pm (UTC)
Glad you like them, and best of luck/skill for your first USPC on Saturday.
Hao YeHao Ye on August 27th, 2011 01:53 am (UTC)
Agreed. These have been really useful to me as well and some of the puzzles are quite clever. ;)

I'm not sure if this counts as part of strategy 4 you mentioned, but I found shading to be helpful for Slitherlink. Since each segment must separate inside from outside, you can occasionally find interior squares that need to "escape" to the edge. Additionally, it will sometimes be the case that a 1 is surrounded on two sides by interior (or exterior squares), which forces it to be interior (or exterior), and informs which edges can (or cannot) exist.
wmwhoteyqie: pic#122123860wmwhoteyqie on January 6th, 2014 10:25 am (UTC)
На каком-то сайте я уже видел близкую информацию хотя пофиг