almost-locked ranges?

Advanced methods and approaches for solving Sudoku puzzles

almost-locked ranges?

Postby Bob Hanson » Sat Jan 03, 2009 7:38 pm

Happy New Year, all,

I'm interested in comments relating to the discussion of what I am calling "almost-locked ranges" at

http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#almostrange

These relate to recent discussions here as well as some of the more complicated fish analyses.

Have these been popularized? (I suspect so.) Pointers to where they are discussed within our outside this forum would be appreciated. I may want to add a few of those links to that explanation page.

I realized that I use them extensively myself when solving puzzles by hand, and since they were recently discussed here in a slightly different context, I incorporated them into the Sudoku Assistant today. The results for the impossible520 set (given at that link above) are really quite impressive. Obviously almost-locked sets are everywhere and whether by that name or not are very powerful devices.

A preliminary set of examples, some of which are quite simple, and some of which are more challenging to figure out by hand can be found at:

http://www.stolaf.edu/people/hansonr/sudoku/ex_A2.htm?n=20&search=ALS-B

Thanks in advance,

Bob Hanson
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby PIsaacson » Tue Jan 13, 2009 7:22 am

Bob,

Could you please verify the link for your impossible 520 puzzles: http://www.stolaf.edu/people/hansonr/sudoku/data/i520.js

[edit] The link is still incorrect, but I got the correct location from your other topic "Sudoku Assistant -- 10000 method exampes" so if it's the same ordering, then I'm okay to cross-check with your results.

When I click to download it or link to it, the server take me to www.stolaf.edu home with an error saying it cannot locate the requested page.

I'd like to check my implementation of your 3d-medusa plus "almost-locked ranges" against your results on this same puzzle set.

[edit] I just ran my solver against the impossible520 list and I only drop into what I think is my equivalent of hypothesis on puzzle 183 and 477. I'm only using the following methods: naked/hidden singles, row/col/box interactions, naked/hidden subsets size 2-4, 3d-medusa + almost locked ranges. I'm assuming that when I load one of the impossible520 puzzles into your Sudoku Assistant and check off the additional ALS checking, that's the correct requirements for adding almost locked ranges? Also, I'm assuming that when a Step is labeled P+ and contains a "hypothesis and disproof" comment the corresponding diagram shows the starting board position.

I'm having trouble matching my solver's steps and output logs to your solver's. All of my methods have a front end scheduler that examines the current puzzle state and uses various (simple) heuristics to select the next best Candidate Elimination Cell to research/attack. If this step results in any reductions, a post processing step decides whether to continue with the current selected method, or to select another. Basically, this means my solver usually doesn't process cells in a nice row/col order for very long, nor does it continue with any method when it decides that some other method will be more productive.

Thanks,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby Myth Jellies » Tue Jan 13, 2009 6:59 pm

Nice to see you again, Bob.

In your color hinge diagrams, you might want to note that...
    A candidate in the yellow cells will inhibit the weak link, but still allow the structure to be used for strong links
    A candidate in the gray cells will inhibit the strong link, but still allow the structure to be used for weak links.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby David P Bird » Tue Jan 13, 2009 10:17 pm

Bob, The first 9 of your almost locked ranges are all 'hinges' or 'empty rectangles' which connect chains orthogonally between rows and columns. The last 6 do the same for parallel rows or columns (Bill Richter wanted to call these hinges too but got no support).

The way I see them is in much the same light as you I believe, namely they provide a way to navigate an inference chain around the grid, and I also share your lack of interest in giving names to every pattern variant. What has interested me of late has been identifying the useful almost locked sets that exist in the mass which is generally available. I came to the conclusion that the most useful ALSs are those which have at least two candidates with nodes that either make up one on half of your red/blue connecting sets or are their complements.

This boils down to considering how the internal nodes in an ALS or its complementary AHT (almost hidden tuple) are confined to the box-line intersections. When they are fragmented, the only way the inference can be propagated onwards is via another pre-analysed pattern with the same fragmented node. For example second pattern could be another ALS/AHT, nearly fish, or nearly unique rectangle, but these connections are much less frequent.

To clarify a "nearly fish": say we have a set of 3 columns with candidates confined to 4 rows. In any of those rows, if that digit is considered true in some other column, one of the four potential fish patterns will become true in the three remaining rows. The possible locations for the fish creating candidate or 'fish egg' can be therefore fragmented across several box-row intersections.

Remembering my schooldays when I had to write in ink, I think of confined nodes as 'blobs' and fragmented ones as 'splatters' in my own workings, but whatever the terminology, I consider this line of reasoning gives me a wider perspective. Each of your almost locked ranges is a box holding two of my 'blobs', and your yellow cells are where they overlap which ideally we'd like to be empty to give maximum versatility as Myth has touched on.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England


Return to Advanced solving techniques

cron