Is this a new technique?

Advanced methods and approaches for solving Sudoku puzzles

Postby Luke » Tue Feb 17, 2009 9:47 am

DonM wrote:Ah, another life lesson: There is ignorance in knowing too much!:D

Funny, with me, the more I learn the more I realize how much I don't know!

And RobO, perhaps the moniker "xy2z" is what's holding things back. Go eponymous. You've got a built-in winner:

RoboWing:!:
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby RobO » Tue Feb 17, 2009 5:22 pm

Luke451 wrote:RoboWing:!:


:D

I'm going away for a few days. Will reconsider if I can think of a better way of 'selling' it.
RobO
 
Posts: 16
Joined: 16 February 2009

Postby PIsaacson » Tue Feb 17, 2009 6:14 pm

RobO,

Don't give up on ALSs or think that they are out of the reaches of the "huddled masses". I thought I would never understand Sue de Coq or be able to find them without a computer. Then DonM posted an outstandingly simple technique for locating them manually. I took the time to practice and while I still don't really understand SDCs, I can find them fairly quickly now. ALSs are all over the place, so learning how to use them effectively is a powerful weapon to have in your arsenal of techniques.

Just remember that due-diligence is a requirement before a patent is granted. Claiming a new pattern/solving technique is a similar process. You should gather statistics on how often this pattern occurs in some of the exemplar large puzzle collections such as royle17, top50000 etc. That helps support the proposition that it's worthy of studying. If you know c/c++, you could download my ALS engine and try modifying it to scan for your xy2z patterns.

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

Postby Draco » Thu Feb 19, 2009 9:01 am

Paul,

I wouldn't mind checking out your ALS engine... where would I find it?

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby StrmCkr » Thu Feb 19, 2009 11:28 am

http://forum.enjoysudoku.com/viewtopic.php?t=6580
thats pauls. thread..
theres is a link to it on there. second post
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 625
Joined: 05 September 2006

Postby PIsaacson » Thu Feb 19, 2009 1:55 pm

Draco,

You're more than welcome to download the code/executable and experiment with it. It's just a framework/testbed that I use when developing various "engines" as I call them. The ALS engine is my current project under development, so this is just a snapshot as of a few days ago. Lots has changed since in terms of ALS loops and paired ALS/AHS interactions. When that code is stable, I'll upload the revised editions, so you might want to track the thread that StrmCkr indicated.

I probably should have posted in the programming forum, but the "Advanced solving techniques" seems to draw the really deep thinkers. I'm finding some really interesting ALS chains/loops, so please, feel free to join in!

BTW, the command line interface options are listed with "sudoku -h", but most of them are for prior engines that I've finished. The main ones you need are:
Code: Select all
-bv      turn on the benchmarking statistics and log all eliminations
-An      set the ALS maximum candidate size (2-9)
-Bn      set the maximum ALS chain/loop size (0-64?)
         use -B0 to get chain size 2         don't ask why
             -B1 to get chain size 2-3
             -B2 to get chain size 2-4 ....
-e       turns on quick exiting logic - use this with really large collections, otherwise they may run for days.
-P       accepts a PM type of input instead of 81 byte lines.
         I use this by copying/pasting a PM into notepad when I want to start from a known position.

sudoku -bve -A4 -B4 <collection>     should be reasonable fast

sudoku -bv -A9 -B10 -P <PM puzzle input>  single puzzle options that I use

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

Postby Allan Barker » Thu Feb 19, 2009 7:50 pm

PIsaacson wrote:I uploaded a version of my current code for you if you want to download:

http://pisaacson.fileave.com/Bernhard/makefile.txt
http://pisaacson.fileave.com/Bernhard/sudoku.cpp
http://pisaacson.fileave.com/Bernhard/sudoku.h
http://pisaacson.fileave.com/Bernhard/sudoku.exe

I use the cygwin environment, so if you don't have that installed, you won't be able to recompile. I used to have a Visual Studio setup, but abandoned that years ago when I switched to using the cygwin/gnu g++ compiler.

Hi Paul, some feedback.

I use gcc with mingw, without anything from cygwin. I successfully compiled your code with a simple command line:

g++ -O3 -D__forceinline="inline" sudoku.cpp.

I did not use the makefile, but it also works if I remove [ -march=k8-sse3 -mtune=k8-sse3 -fwhole_program]. I suspect that most gcc installations that compile a command line program in windows will work the same.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby PIsaacson » Thu Feb 19, 2009 8:23 pm

Allan,

Thanks for compiling it on another machine. The last version I uploaded included #ifdefs around the cygwin specific code. All you perhaps lost was the 5 second interrupt timer that flushes output in the testbed code and the printing of the working directory of the executable.

I'm still experimenting with fitting AHSs into chains/loops. I think I have the linking part working correctly using Champagne's approach of always treating ALS/AHS as a paired unit (which they are of course, but somehow that eluded me) and chaining using the inferences caused by their interaction. When I finish the elimination rules, I'll refresh the source & executable and add a posting to the ALS thread.

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

Postby Draco » Fri Feb 20, 2009 10:39 am

PIsaacson wrote:Draco,

You're more than welcome to download the code/executable and experiment with it. It's just a framework/testbed that I use when developing various "engines" as I call them. The ALS engine is my current project under development, so this is just a snapshot as of a few days ago. Lots has changed since in terms of ALS loops and paired ALS/AHS interactions. When that code is stable, I'll upload the revised editions, so you might want to track the thread that StrmCkr indicated.

Thanks Paul (and StrmCkr). I'll have to set aside some time to review your post in detail. I'm mostly interested in seeing how you've coded it up. It is one thing to have a technique explained... another entirely to have source code (with all the edge conditions handled) for really understanding the details. I've found that as I've learned techniques (or thought I did), when I really learned them is when I've coded up the methods for my solver. Sometimes it takes lots of testing there before I find the finer points I've missed.

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby PIsaacson » Fri Feb 20, 2009 12:29 pm

Draco,

The code depends heavily on STL map/bitset containers, so if you are not familiar with them, you might want to Google "SGI STL". If you have specific questions, send me a PM and we can take it off-line. I have the basic pseudo code design somewhere in my manual notes, so I'll look for that and upload it to the hosting site with the source code. I should have done that before.

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

Postby RobO » Mon Feb 23, 2009 4:20 am

As I said before, I've been pondering over this one and would like to add a few points:

Yes, it's an ALS but, I would say, of a fundamentally different type to the ones that I've seen posted as examples. Unfortunately, that 'fundamental' difference is purely subjective. What I mean by that is that my pattern is clearly visible to anyone who knows y-wings and has a little bit of additional expertise, while the ALS examples are not.

ALSs are a complex technique to get your head around. When I've read about them in the past, I have failed to really get to grips with them. Similarly, I've posted this pattern on another forum (far less expert than this one), and also mentioned the reaction here that this is an ALS. Another poster from there (who I know can handle xyz-wings without too much problem) said that "his eyes glazed over" when reading about them.

I think I have it correct that y-wings, xyz-wings and wxyz-wings (plus the ones with even more letters) are all also ALSs.

My conclusions:

Examples introducing ALSs are weak and difficult to understand due to their complexity. A better method of getting people used to them would be desirable. Certainly, the process that I've been through with posting this pattern and reading comments on this thread have aided me in getting a better idea of them (not so far that I've actually spotted any more in live puzzles so far, but I live in hope.)

Therefore, I would suggest the introduction of a 'type 2 wxyz-wing category' which would be defined as 'an ALS featuring any four numbers'. Documentation about that technique should clearly state the link to ALSs - and also point out that y- and xyz- wings are cases as well. My hope would be that people would be able to see the patterns in standard wxyz-wings and my example, and then extend the technique.

One point where this breaks down a touch is where there are only four numbers involved but the pattern is still 'complex'. e.g. this example from scanraid (top left four boxes only) ...

Code: Select all
 279   3       29      |  6    8       47   
 6     48      1       |  5    2479    3
 579   48      59      |  29   2479    1
 ----------------------+--------------------------+
 129   129     4       |  8    179     5
 8     6       239     |  239  23479   47 
 13    5       7       |  123  12346   26 


...which has the 13 in r6c1 and the 1239 in col 4 eliminating the 3 from r6c5. This I would count as a 'complex' ALS but think that that is a good thing as it would encourage the user to understand the pattern in both simple and complex forms and get them to make the bridge from one to the other.

Thoughts?
RobO
 
Posts: 16
Joined: 16 February 2009

Postby DonM » Mon Feb 23, 2009 5:08 am

RobO wrote:Yes, it's an ALS but, I would say, of a fundamentally different type to the ones that I've seen posted as examples. Unfortunately, that 'fundamental' difference is purely subjective. What I mean by that is that my pattern is clearly visible to anyone who knows y-wings and has a little bit of additional expertise, while the ALS examples are not... Examples introducing ALSs are weak and difficult to understand due to their complexity.

Can you really be sure of that as a general statement or does it perhaps have more to do with the point in the learning curve one is at? I don't know if you have been referred to it or not, but I will humbly point out the ALS tutorial which starts with the simplest 2-set ALS and works it's way up:

http://forum.enjoysudoku.com/viewtopic.php?t=6443

ALSs are a complex technique to get your head around. When I've read about them in the past, I have failed to really get to grips with them. Similarly, I've posted this pattern on another forum (far less expert than this one), and also mentioned the reaction here that this is an ALS. Another poster from there (who I know can handle xyz-wings without too much problem) said that "his eyes glazed over" when reading about them.

Trying to sell people in a more expert forum on a method based on anecdotes from a 'far less expert' forum has its limitations.

Therefore, I would suggest the introduction of a 'type 2 wxyz-wing category' which would be defined as 'an ALS featuring any four numbers'. Documentation about that technique should clearly state the link to ALSs - and also point out that y- and xyz- wings are cases as well. My hope would be that people would be able to see the patterns in standard wxyz-wings and my example, and then extend the technique...

Thoughts?


The reason I particularly resist this approach is that my (and sirdave's) ALS tutorial was an attempt to simplify the understanding of ALSs by reducing the need for/use of separate names for structures that were actually closely related patterns. For instance, the original simplest pattern, the ALS-xz rule, is a 2-set ALS chain. Likewise the ALS xy-wing rule is simply a 3-set ALS chain. With that in mind, it is IMO a backward step to add another multi-letter based name to signify 'an ALS featuring any four numbers.'

There are several examples in graphics of the simple ALS xz-rule beside the more extensive ALS Chain tutorial. Since the use & understanding of ALSs is very useful in basic pattern-solving & becomes necessary in more advanced solving, I think it is more constructive for one to simply hunker down and understand them. They aren't really all that difficult.
Last edited by DonM on Mon Feb 23, 2009 11:48 pm, edited 1 time in total.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby PIsaacson » Mon Feb 23, 2009 5:45 am

DonM,

The basic concept of ALS chaining may not be all that difficult, but the rules for RCDs are getting complex. In order to subsume XY chains, which are simple chains of bi-value ALS cells, the RCD rules need some revision yet again. Currently, the RCD rules do not allow a "string" of conjugate pairs, but this is perfectly legal in XY chains. SirDave's original ALS chaining posting and your reposting demonstrate this in the 7th example. I don't want to hijack this topic, so I'll post the newly revised RCD rules on some other germane thread.

Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby RobO » Mon Feb 23, 2009 6:28 am

DonM wrote:
RobO wrote:Yes, it's an ALS but, I would say, of a fundamentally different type to the ones that I've seen posted as examples. Unfortunately, that 'fundamental' difference is purely subjective. What I mean by that is that my pattern is clearly visible to anyone who knows y-wings and has a little bit of additional expertise, while the ALS examples are not... Examples introducing ALSs are weak and difficult to understand due to their complexity.

Can you really be sure of that as a general statement or does it perhaps have more to do with the point in the learning curve one is at? I don't know if you have been referred to it or not, but I will humbly point out the ALS tutorial which starts with the simplest 2-set ALS and works it's way up:

http://forum.enjoysudoku.com/viewtopic.php?t=6443



Nope. I hadn't seen that link. I shall take a look but might take a few days as I'm fairly busy. Thanks in advance.
RobO
 
Posts: 16
Joined: 16 February 2009

Postby DonM » Mon Feb 23, 2009 8:13 am

PIsaacson wrote:DonM,

The basic concept of ALS chaining may not be all that difficult, but the rules for RCDs are getting complex. In order to subsume XY chains, which are simple chains of bi-value ALS cells, the RCD rules need some revision yet again. Currently, the RCD rules do not allow a "string" of conjugate pairs, but this is perfectly legal in XY chains. SirDave's original ALS chaining posting and your reposting demonstrate this in the 7th example. I don't want to hijack this topic, so I'll post the newly revised RCD rules on some other germane thread.

Paul


Just so this doesn't cause any confusion in this thread, the typical ALS patterns that one will come across in most puzzles will not require complex rules for the restricted common connections. However, the interesting work you are doing may allow the extension of what were the 'usual' rules for restricted commons to allow the repeat use of the same restricted common digit values in certain situations which may allow, more typically in computer solver applications, the finding of more useful ALS eliminations.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

PreviousNext

Return to Advanced solving techniques