Sue De Coq Revisited Again (ASI#1)

Advanced methods and approaches for solving Sudoku puzzles

Postby David P Bird » Wed Nov 19, 2008 4:50 am

PIsaacson, Yes, I've just assumed than an alternating inference chain that includes ALS inferences can be called an ALS chain! As I build any sort of pattern inference into AICs, I suppose I should find a better name.

Thanks for the extra (1) eliminations, and I've now edited my post to show them.

I prefer to call these patterns as Disjoint Locked Sets because they are indeed both disjoint and locked. In your handle "Distributed" doesn't really describe anything extra, and by droppling the "Locked" part you've actually lost an important qualifier!

The question remains though, are any of the eliminations you've just found incapable of being found using ALSs embedded in AICs?
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby aran » Wed Nov 19, 2008 5:38 am

Slightly on topic.
Since I tend automatically to look at "hidden patterns", I approached Don's 3 puzzles in the original post to see what would emerge, and indeed the same results are readily obtained.
(Puzzle 1 : hidden triple (457) r2c123
Puzzle 2 : hidden pair (37) r78c9
Puzzle 3 : hidden quad (1256) r6c123+r5c2).
Paths not posted (except on request !), because not relevant to what follows.

What was clear from those solutions is that they are driven in the "not hidden" part of the work by a useful incompatibility :
Puzzle 1 : 3 and 8 incompatible in r2c23 because of r2c7 (38)
Puzzle 2 : 1 and 2 incompatible in r7c89 because of r7c2+r7c5 (29)+(19)
Puzzle 3 : 8 and 9 incompatible in r6c13 because of r6c5 (89).

With the same approach to Ronk's puzzle Ruud50k #3284, the hidden triple r789c4 (146) produces the eliminations however without any incompatibility factor.
ie the "not hidden part" being merely r9c4 (7) needs only the resulting pair (25) r9c67 to proceed.
Since there was some debate about whether it wasn't or wasn't an SDC, extrapolating the above ie requirement for an incompatibility (yes not scientific:!: ) might suggest that it wasn't.

But whatever about that, it would be interesting to see if general SDC is representable in "hidden" format. If so, then an equivalent approach might be easier to formulate such as : investigate hidden pairs/etc when the "not hidden" part has an incompatibility factor.
aran
 
Posts: 334
Joined: 02 March 2007

Postby eleven » Wed Nov 19, 2008 8:32 am

Since i never studied a definition of SdC i now had a closer look at the samples in the original post.
Some notes:

First i prefer to start from the line and then go into the box to see, if there is a SdC. You seem to see it differently, cause there were doubts, if ronk's sample would be one at all. But of course, if a bivalue cell is in the box and you need 2 cells (out) in the line, its easier this way round.

So, in the first sample i would start with the 38-cell, find, that it leaves 457 in r2c23 and get the SdC with the box cells r1c3, r2c1 only containing 457 also (seen this way r2c1 would belong to the brown cell). That eliminates 45 in r3c2. The elimination of 5 in r2c4 for me is just a follow-up with locked candidates.

In the third sample i would not make r6c2 part of the SdC. The 15 in r5c2 leaves 289 in r6c13, which is enough with r5c59 being constrained to 289 also. This way you cannot eliminate the 6 in r4c2 by the SdC, but 15 in r6c2, which leaves a 6 there and kills the others anyway.

Of course i know, that sometimes you need the 3rd common cell to be able to make an elimination (I just would not add it here).

Cases, where both in the box and the line more (non common) cells are needed, are rather hard to spot and i never looked for them so far.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby hobiwan » Wed Nov 19, 2008 8:59 am

PIsaacson wrote:SdC: r9c456 - {24567} (r9c7 - {25}, r78c4 - {146}) allows r3c4 <> 6 (I think?) so this can't be correct as indicated below

All three forms (whether you accept them as SDCs or not) lock candidate 6 in [r89c4,r9c5]. They can therefore eliminate 6 in b8 but not in c4.

(Sorry for the late answer, been busy...)
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby DonM » Wed Nov 19, 2008 11:18 am

PIsaacson wrote:David,

I am an avid fan of ALSs, and I still look at most SDCs as ALS chains. But I also look at them as a complete unit ala DDS and use multiplicity computations to find all the reductions.

For instance, in Ronk's example that you cite, you didn't include the r136c4 <> 1 reductions due to the alignment of the 1's in the DDS, or due to looking at it as a simple dual-linked ALS chain: r789c4 {1467} = r9c567 {2567} common restricted {67}

In both the DDS/ALS cases, the reductions are the same. It's the SDC that gives me grief because of the elimination rules.

Your ALS chains look like niceloops with embedded ALS groups? If so, then they are not quite the same as what I refer to as ALS chains.
Ref: http://www.sudoku.org.uk/SudokuThread.asp?fid=4&sid=9448&p1=1&p2=11


PI, thanks for that study on the frequency of SDC. I know that type of thing takes some time, but it's worth it because (I think) this is a very interesting subject. I also appreciate that you are getting the point of the value of SDC.

It may be of interest that there are other threads that have discussed the fact that eliminations possible from the basic forms of SDC can be arrived at using the underlying ALS patterns: http://www.sudocue.net/forum/viewtopic.php?t=472 and http://www.sudocue.net/forum/viewtopic.php?t=625

I look on the presence of a SDC as like a big flashing sign: 'Eliminations! Eliminations!'. Is it easier for the average solver to, using the simplified directions, find a SDC and take advantage of the eliminations or can it be assumed that those same eliminations could be found reliably using other patterns without knowing the SDC was there? There's no question which is easier for me.

(PI- btw: here's an updated link for that original ALS Chains thread, but with the graphics restored: http://www.sudoku.org.uk/SudokuThread.asp?fid=4&sid=10326&p1=1&p2=11. The ALS Chain Tutorial I put on this forum ( http://forum.enjoysudoku.com/viewtopic.php?t=6443 ) is a compressed, rewritten version of sirdave's post done with his close cooperation- we being good buddies and all.:) )

(Edited to save bandwidth, among other reasons:) )
Last edited by DonM on Wed Nov 19, 2008 3:09 pm, edited 1 time in total.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby eleven » Wed Nov 19, 2008 12:08 pm

So much words. What did he say now? Does it help solving puzles ? Ah sorry, im so primitive, i always want to do it ... manually.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby denis_berthier » Wed Nov 19, 2008 9:39 pm

eleven wrote:
denis_berthier wrote:OK, but most SdC are subsumed by much simpler NLs.
If with simpler NL you mean e.g. a w-wing, i agree. If you mean a 5-cell bilocation chain, i dont. Any fixed technique hierarchy is problematic and statistics based on that will always give a biased result.

PIsaacson wrote:Anyway, the point was to count SDCs, so I deliberately omitted any methods other than those associated with SSTS and SDC/DDS. I even had to "dumb down" the X-cycles/X-coloring to agree with the coloring technique used in Simple Sudoku.


This illustrates that different goals lead to different evaluations.
My goal wrt SdC, if I have any, is to determine if there is anything fundamentally new in it. And it seems I'm not the only one to wonder.
Said otherwise:
1) is it only easier for players than other patterns (which, admittedly, would be enough reason to have it in our arsenal)
2) and/or does it also lead to new eliminations?

On the first point, I have no opinion. In the above posts, I've seen contradictory opinions from different players.

On the second point, we face the problem of deciding wrt what we try to see if it is new. This is were a bias can appear. (We also face the problem of giving a precise definition.)
It seems to me that if an elimination can be done using only a sub-pattern of the SdC (i.e. another pattern that is a part of the SdC, such as an ALS-chain or an xy-chain), then this elimination shouldn't be considered as new.
Paul, do you have any means of taking this into account in your statistics?
Can anyone provide examples of eliminations that can't be done by a well known sub-pattern?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby eleven » Thu Nov 20, 2008 12:24 am

It seems, that my understanding of a SdC rather is an easy to spot special case of what PIsaacson called a dual (or triple..) linked ALS chain, than what DonM defined. SdC's are not a new thing, so they cant make new eliminations. And its also clear, that they can be generalised (and obviously this has been done in 2 directions), but for manual solvers this is of marginal interest.

Also it seems, that most manual solvers think, that SdC's are as hard to find as ALS chains (personally i only find these accidently, how could i do it systematically with hundreds of potentially useable ALS's in a grid ?). So i think, they have been presented poorly in respect to manual solving.

One more point about statistics. The frequeny of patterns in grids often is strongly related to the pattern of the sudoku.
In diagonal grids you will find much more x-wings, swordfish etc. than in random grids and in the pattern of tareks puzzles above you will find much more jellyfish and Sue de Coq's than on average.
The reason is obvious. The pattern gives more chances for them.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby David P Bird » Thu Nov 20, 2008 2:17 am

Eleven, As I've tried to say, it's a matter of preference - how quick can we get at spotting useful tell-tale patterns for arriving at our deductions. Once we're aware of the power of a particular pattern, if we want, we can train our eyes to recognise them.

I use colouring schemes on a spreadsheet to help my otherwise rather poor pattern recognition skills. One of them highlights bivalue cells which allows me to spot the simple SDCs fairly easily. As I've shown, one of these will replace several individual AICs, so a quick check if successful, will produce a big advance.

The more complex ones take me much longer to find, although I'm sure if I practised I'd speed up. It then becomes a question of pattern frequency as to which manual solving strategy will be most successful. Until quite recently I left checking for SdCs quite late in my running order and consequently didn't find any because I'd already made the eliminations using chains. Now I run quick checks for the simplest ones fairly early because the potential benefits are so good. However I then leave them alone as I feel the chances of finding one created by a new elimination are reduced. Whether that feeling is right or wrong is an open question though.

Regarding ways to find ALS see here: http://forum.enjoysudoku.com/viewtopic.php?t=6351
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby aran » Thu Nov 20, 2008 3:47 am

David P Bird
one of these will replace several individual AICs

I think that what Eleven is saying, and what I am saying, is that our alternative approaches (broadly hidden subset) will produce these same eliminations in the one movement (and not as series of AICs) in a way that to us (heavily underlined) seems simpler both to spot and express. Denis Berthier raises a similar point.
aran
 
Posts: 334
Joined: 02 March 2007

Postby eleven » Thu Nov 20, 2008 4:23 am

David,

so we agree in the most points you mentioned. All SdC's with a single bivalue cell in the line or the box are easy ones for me.

Concerning the ALS search (thanks for the lnks) i am with Myth Jellies: When elaborating AIC's or any chains i naturally find some. So there is no need for looking for them explicitely.

The basic question always remains. Where should i start to look for chains (ALSs or whatever) ? I have some favorites like AURs or pincers of wings which had been useless so far, maybe i will try almost SdC's now, but i think, this always will be a question of personal flavour.
eleven
 
Posts: 1535
Joined: 10 February 2008

Postby ronk » Thu Nov 20, 2008 4:46 am

PIsaacson wrote:
Code: Select all
Statistics for royle17 (max 6 candidates)

36628 puzzles took 438.40 sec total  average 11.97 msec/puzzle

Sue deCoq    992 out of  36628 2.71%
2 sec DDS   5005 out of  36628 13.66%
Solved     35918 out of  36628 98.06%

With about the same set of basic techniques, I get 35082 solved ... but only 167 SDCs. These are SDCs with a maximum of 7 candidates in the "core set" and a maximum of 9 cells-- 3 in the box-row (or box-column) intersection, 3 more in the box, and 3 more in the row.

Something is severely out of whack here. Are you counting only SDCs that result in an elimination? Are you counting essentially the same SDC more than once? For example, I'm counting the three possible interpretations here as one SDC.

[edit: added the following]

Perhaps my code has a super-serious bug. If you PM me your email, I can send the 167 puzzles in which I find one or more SDCs. Then you could post a few SDCs from some of the other 992-167 puzzles.

[edit2: Before disabling xyz-wings, w-wings and advanced coloring, solved count was 35911 and SDC count was 119.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Wed Jan 21, 2009 12:13 pm

denis_berthier wrote:It seems to me that if an elimination can be done using only a sub-pattern of the SdC (i.e. another pattern that is a part of the SdC, such as an ALS-chain or an xy-chain), then this elimination shouldn't be considered as new.
Paul, do you have any means of taking this into account in your statistics?


Denis,

Sorry for the delay in responding, but I had to rewrite my method scheduler to accept new command syntax to allow restarting a puzzle or a board position with different ordering rules and to track/report statistics for each different set.

I don't have exact results yet (still debugging the new syntax processor), but based on preliminary testing, all the SDCs that my solver detects can be replaced by ALS dual-linked chains and subset counting. I don't have your hxyzt-chains, but nrczt-chains/whips/braids produce eliminations equivalent to any SDC that I currently detect.

However, my SDC method uses a variant of my subset counting method limited to 2 sector distributed disjoint subsets, so I'm not sure that I'm finding all possible SDCs. Ruud's SudoCue is the only other solver I have access to that locates SDCs, but it doesn't accept batch processing of puzzles, so I can only spot check. So far, I'm finding (at least) everything that SudoCue v 3.20 finds.

This may be a case of comparing apples to oranges from a candidate elimination POV. SDCs allow for (some) eliminations that ALS chains and subset counting do not seem to consider. Likewise, ALS dual-linked chains and subset counting allow for eliminations that SDCs skip. That's what has me pretty confused about SDCs -- the formal candidate elimination rules are tricky/complex and I may not have implemented them 100% correctly. Checking against manual posted solutions has been frustrating because my solver doesn't always find the same SDCs as in the examples.

As for the question of whether or not SDCs find newer/better eliminations, I can only say that I'm starting to find SDCs manually and I feel pretty good about it. I guess what I'm trying to say is that manual solving is a very individualistic process and everyone has favorite techniques based on their current abilities/knowledge.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby hobiwan » Wed Jan 21, 2009 4:33 pm

PIsaacson wrote:Ruud's SudoCue is the only other solver I have access to that locates SDCs, but it doesn't accept batch processing of puzzles, so I can only spot check.

HoDoKu finds SdC as well (although not all extended variants) and you can list all SdCs at a given state of the puzzle. Batch processing currently only looks for puzzles that cant be solved without guessing, but if you tell me want you need I could probably add it.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Previous

Return to Advanced solving techniques