The New Sudoku Players' Forum

[Luke]

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

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

[RobO]

RoboWing

I'm going away for a few days. Will reconsider if I can think of a better way of 'selling' it.

[PIsaacson]

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

[Draco]

Paul,

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

Cheers...

- drac

[StrmCkr]

http://forum.enjoysudoku.com/viewtopic.php?t=6580
thats pauls. thread..
theres is a link to it on there. second post

[PIsaacson]

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

[Allan Barker]

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.

[PIsaacson]

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

[Draco]

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

[PIsaacson]

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

[RobO]

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?

[DonM]

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.

[PIsaacson]

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

[RobO]

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.

[DonM]

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.