The New Sudoku Players' Forum

[Myth Jellies]

M. Mepham's "unsolvable" #10 is a nice one for showing off the simplest of POM functions.

Code: Select all

 *-----------*
 |..4|.5.|9..|
 |...|.7.|..6|
 |37.|...|..2|
 |---+---+---|
 |..9|5..|.8.|
 |..1|2.4|3..|
 |.6.|..9|2..|
 |---+---+---|
 |2..|...|.93|
 |1..|.4.|...|
 |..6|.2.|7..|
 *-----------*


Basic methods will take the grid to this point.

Code: Select all

 6   *18*    4   |*3*   5    2   | 9     7   *18* 
 59   189    2   | 4    7    18  | 58    3    6   
 3    7      58  | 6    9    18  | 458   145  2   
-----------------+---------------+-----------------
 4    2      9   | 5    3    6   | 1     8    7   
 7    5      1   | 2    8    4   | 3     6    9   
 8    6      3   | 7    1    9   | 2     45   45   
-----------------+---------------+-----------------
 2   -48-    578 | 1    6    57  | 458   9    3   
 1   *389*  #578#|*89*  4    357 | 6     2   *58* 
 59  *3489*  6   |*89*  2    35  | 7     145 *1458*


An 8's filet-o-fish swordfish in r189c249 (fin in r8c3) kills 8 in r7c2. This solves for a couple 4's and takes the grid to the following point.

Code: Select all

 6    18     4   | 3    5    2   | 9     7    18   
*59*  189    2   | 4    7    18  |*58*   3    6   
 3    7      58  | 6    9    18  | 4     15   2   
-----------------+---------------+-----------------
 4    2      9   | 5    3    6   | 1     8    7   
 7    5      1   | 2    8    4   | 3     6    9   
 8    6      3   | 7    1    9   | 2     45   45   
-----------------+---------------+-----------------
*2*   4     -578-| 1    6    57  |*58*   9    3   
 1    389    578 | 89   4    357 | 6     2    58   
#59#  389    6   | 89   2    35  | 7     14   14   


From here, a sashimi x-wing for 5's in r27c17 (fin r9c1) kills candidate 5 in r7c3. This opens the way for a normal 5's swordfish in r279c167 to eliminate the 5 in r8c6. Now the grid looks like this

Code: Select all

 6    18     4   | 3    5    2   | 9     7    18   
 59   189    2   | 4    7    18  | 58    3    6   
 3    7      58  | 6    9    18  | 4     15   2   
-----------------+---------------+-----------------
 4    2      9   | 5    3    6   | 1     8    7   
 7    5      1   | 2    8    4   | 3     6    9   
 8    6      3   | 7    1    9   | 2     45   45   
-----------------+---------------+-----------------
 2    4      78  | 1    6    57  | 58    9    3   
 1    389    578 | 89   4    37  | 6     2    58   
 59   389    6   | 89   2    35  | 7     14   14   


Now we will put POM labels on just the 5's and 7's in this grid. Since the 5's and the 7's appear exactly twice in each box, we know there can't be more than 2 potential solution patterns for each of them. They are the same patterns that you would get from simple coloring. So labeling them 'A' and 'B' for each, we get the following.

Code: Select all

 6    18     4    | 3    5    2   | 9     7    18   
 5B9  189    2    | 4    7    18  | 5A8   3    6   
 3    7      5A8  | 6    9    18  | 4     15B  2   
------------------+---------------+-----------------
 4    2      9    | 5    3    6   | 1     8    7   
 7    5      1    | 2    8    4   | 3     6    9   
 8    6      3    | 7    1    9   | 2     45A  45B 
------------------+---------------+-----------------
 2    4      7A8  | 1    6    5A7B| 5B8   9    3   
 1    389    5B7B8| 89   4    37A | 6     2    5A8   
 5A9  389    6    | 89   2    35B | 7     14   14   


A pair of cells which contain all of the potential patterns for a number, I call a vulnerable pair. You can note by inspection that in r8c3 and r7c6, the 7B pattern occupies cells containing both of 5's patterns. This means that if 7B were true, then 5's could not possibly have a valid pattern. Thus we can eliminate 7B, which basicly solves the puzzle.

Of course this puzzle could have been solved dozens of other ways, but it does show one of the basic POM operations quite nicely.

[Jeff]

Hi MJ, This is the nicest way to demonstrate the operation of POM I have even seen. Instead of setting up these solution patterns by hand, could you or someone produce a computer software with an input of a grid and output of all possible solution patterns for all 9 digits. I would have done that if I am capable.

[vidarino]

Hi MJ, This is the nicest way to demonstrate the operation of POM I have even seen. Instead of setting up these solution patterns by hand, could you or someone produce a computer software with an input of a grid and output of all possible solution patterns for all 9 digits. I would have done that if I am capable.

Heh, funny you should say that. I'm working on adding some POM functionality to my solver as we speak, as a response to MJ's post.

My program is web-based currently (written in PHP), so it shouldn't be too hard to set up something you can feed a grid and get a dump of all the patterns. The plan is to generate labelled output similar to the last one in MJ's post.

I'll keep you posted.

[Jeff]

My program is web-based currently (written in PHP), so it shouldn't be too hard to set up something you can feed a grid and get a dump of all the patterns. The plan is to generate labelled output similar to the last one in MJ's post.

Hi vidarino, Good on you, mate.

[vidarino]

Voila.

OK, I have make a very basic POM analyzer. It's a bit awkward to use currently, but it appears to be working.

There are some very limited solving capabilities included. It checks for vulnerable pairs and their common components, just to demonstrate that it works. I'll probably extend this with more POM rules a bit later, but its primary usage is the generation of the patterns and resulting "map".

Click here to see the analysis of MJ's sample grid from above.

(To feed it a custom grid, edit the URL. The format should be self-explanatory. I'll add some kind of import function later.)

Oh, and it's currently limited to 26 patterns per number (a-z). Too lazy to fix that right now. ;) (It will most likely generate bogus results on larger sets.)

Have fun.

[Jeff]

To feed it a custom grid, edit the URL. The format should be self-explanatory. I'll add some kind of import function later.

Well done vidarino. Could you explain how to edit the URL to input a new grid?

[edit: Got it MJ, Thanks. ]

[Myth Jellies]

Very cool

I think you just plug in your comma separated list of candidates into the url and go. I did that with the grid at the top of this post and voila! Note that the elimination of 8fg solves for 5g [edit - in r3c3] and basically cracks the puzzle right there. Very cool.

Well done, vidarino.

[Jeff]

Hi MJ, With vidarino's solver, we are one giant step closer to prove that POM can be used to solve every grid in the universe.

[ronk]

I did that with the grid at the top of this post and voila! Well done, vidarino.

Yes, vidarino, very well done indeed.

However, in MJ's original link above, I did notice a 4c in r9c2 despite col 2 already having a 4. [edit: Oh, that's MJ's extraneous candidate in r9c2, so I deleted it from the link in this post.]

Ron

[vidarino]

Glad you like it so far.

Thanks to my insomniophilia (I love not sleeping ;) it has been extended significantly lately. (I just uploaded the new version.)

But the pattern exclusion equations don't seem to work properly, so it incorrectly eliminates the wrong patterns. I hope I have added enough debug output to identify what I'm doing wrong, so if Myth Jellies or any other POM guru would look closer at it, I would be delighted.

I have included a few sample grids now, one that demonstrates that there is indeed an error (Mepham's Unsolvable 1), and a couple of others that demonstrate successful solving.

To skip inspect the equation generation, open "Mepham's 1", hit "Analyze" and fast-forward to Step 5. I believe I have followed the instruction in MJ's "Taking on a killer Tso puzzle" walk-through, but something is definitely amiss.

(Well, I should point out that I naively assume that the equations are to blame. My only reasoning is that puzzles that don't require the use of them seem to solve nicely.)

It's here: http://vidar.gimp.org/sudoku/

Vidar

[Myth Jellies]

As long as we are here, I might as well use vidarino's program on the original grid (after basic methods were applied) to illustrate POM's second basic method: POM Equation Analysis.

Many of our advanced methods, such as colors and forcing chains, are concerned with keeping track of, and using, Sudoku's elusive "logical NOT". POM is no different, and POM has a very effective and useful "logical NOT". For example, in our grid we have 8abcdefg as all the potential patterns for the eights. Thus,

NOT 8e = 8abcdfg = 8a OR 8b OR 8c OR 8d OR 8f OR 8g

Now consider every unsolved cell. For each candidate digit N in each cell there is a POM equation

NOT digit N's patterns in the cell = the remaining patterns in the cell.

For example, our r2c2 cell contains (1b 8e 9c). That's three candidates, which means we get the following three equations

NOT 1b = 1a = 8e 9c
NOT 8e = 8abcdfg = 1b 9c
NOT 9c = 9ab = 1b 8e

Sudoku's elusive NOT has been turned into something that looks positively algebraic (an oxymoron for some I'm sure ).

Now consider the cells r2c6, r2c7, r3c8 along with r3c6. This is an xy-wing which allows us to kill the candidate 1 in r3c6; but, what does POM indicate about this setup.

From the grid,
r2c6 = (1a 8abfg); r2c7 = (5g 8cd); r3c8 = (1a 5f);
r3c6 = (1b 8cde);

Well we can take a shortcut and note the (1:8)-(8:5)-(5:1) chain in cells r2c6, r2c7, and r3c8. This means that the 1 in r2c6 and/or the 1 in r3c8 is true. Since the pattern in both those cells is 1a, we know that 1a is true and thus 1b is false. Hence, we can remove 1b from r3c6. This is consistant with what we know about xy-chains.

But, lets try it the long way using POM Equation Analysis techniques.

from r2c6
1b = 8abfg;
8cde = 1a;

from r2c7
5abcdef = 8cd;
8abefg = 5g;

from r3c8
1b = 5f;
5abcde = 1a;

Thus substituting...
1a = 8cde = 8cd 8e
1a = 5abcdef 8e = 5f 5abcde 8e
1a = 1b 5abcde 8e

But wait, there is nothing on the left side of the equals sign for 1b to be equal to. It can't be equal to 1a and be true at the same time, thus 1b must be false. Via the equations we know that 5f and 8abfg must be false as well.

For those who might want to play, there is another chain you can analyze in r7c7, r6c8, r6c9, and r9c8.

It turns out that a POM Equation Analysis using the same cells as any method that does not employ uniqueness will be able to make at least the same deductions as that other method.

[vidarino]

Hmm, this is very interesting approach, I must admit.

But what exactly is the goal of these reductions?

Thus substituting...
1a = 8cde = 8cd 8e
1a = 5abcdef 8e = 5f 5abcde 8e
1a = 1b 5abcde 8e

The reason I'm asking for a specific goal is that I'm trying to add this logic to my program, so then I need to know what exactly I'm trying to do.

A possible goal, as far as I can see, is to try to reduce the left-hand side of the equations as much as possible, to be able to match more cells.

Currently I'm just using the equations as they are generated, without reductions, to kill patterns that match, and that appears to be working, but that alone isn't enough to crack the puzzle, so reductions are apparently needed.

Pseudocode for my algorithm:

Code: Select all

for each generated equation Nx=My {
    for each cell that has candidates N and M {
        if equation's Nx is a subset of cell's Nx, then {
            duplicates = intersection equation's My and cell's My
            for each duplicate d { kill Md }
        }
    }
}


(Erk, interrupted by offline matters. To be continued...)

[vidarino]

Whee, got it!

The updated POM analyzer (still here) now does basic equation reductions, and solves Mepham's Unsolvable 1 and 2 right off the bat.

There are some limitations, but I hope to get around to addressing them soon. First and foremost, the maximum number of patterns for a digit is around 100. I'm planning to extend this considerably by using two-letter names on larger sets.

I also intended to keep track of which cells contributed to which equations (and it used to do that) in order to make it easier for a human to follow the eliminations. However, as the equations are reduced, merged and generally manhandled, their constituents' origins became almost impossible to keep track of. I still haven't given up on that, because it would be very helpful in understanding what's going on, but it might take some time and redesign.

So there you have it.

Big thanks to Myth Jellies for his excellent explanations on the subject!

Vidar

[Myth Jellies]

For those of iron constitution who may have missed it, here is the link to the Advanced POM: Taking on a Killer Tso Puzzle thread.

Vidarino, this is more than excellent . I think I can see that you have used pattern substitution and the removal of duplicated patterns. That was the very first POM technique I found. For those I have just left in the dark, this technique amounts to taking any equation derived from POM equations and using it to make a substitution in a cell. After the substitution, any patterns which were duplicated in the cell could be deemed invalid. I eventually found that patterns deleted using this substitution/duplication/deletion technique were a subset of the patterns that can be killed from a full POM equation analysis, at least that seems to be the case when doing POM by hand. If you have the patience and tenacity of a computer when jockeying the equations around, it could be that a substitution/duplication/deletion program eventually finds them all.

I was curious if your program used any of the other techniques. It looks like the vulnerable pairs logic has fallen by the wayside in the latest incarnation.

I just can't stop playing with your program. I await your upgrade to handle more patterns with great anticipation. One of the ideas I had when it came to displaying digits that had a great number of patterns was a clickable field that would reveal the patterns in a little pop-up window. Not sure what you had in mind, but for the tougher puzzles you could end up with a ton of labels in the cells.

[vidarino]

I was curious if your program used any of the other techniques. It looks like the vulnerable pairs logic has fallen by the wayside in the latest incarnation.

Oops, indeed. I disabled the VP tests to give the equation substitution more to work with on simpler puzzles. I have enabled them again now.

The pattern substitution was extended a bit in yesterday's version. Whenever it compared the contents of a cell to the stored equation, it also searched for "sub-equations" that go with it.

An example:

Code: Select all

1ab = 2abc 3bcd
3bc = 2cd 4def
4f = 5abcdef


Now, whenever the solver finds a cell with a candidate 1 (e.g. "1abcd"), it finds all matching (subset of left hand side) equations, "1ab" in this case. Then, for each right hand side component, it does a new lookup for further extensions. In this case, "3bcd" matches "3bc", so the right hand elements of "3bc" are merged into out original equation, making our equation "1ab = 2abcd 3bcd 4def".

Then, a second-level scan for extensions is done, and the "4def" matches "4f", so that one is merged as well. Returning to the cell in question, if it contains any one of the patterns "2abcd 3bcd 4def 5abcdef", they will be killed.

I think this equation expansion scan could (and perhaps should) be even deeper (possibly all the way to the end, so to speak), but it seems to suffice. At least for now, with a limit on the pattern set size. (And I will work on fixing this Real Soon Now(tm).)

I just can't stop playing with your program. I await your upgrade to handle more patterns with great anticipation. One of the ideas I had when it came to displaying digits that had a great number of patterns was a clickable field that would reveal the patterns in a little pop-up window. Not sure what you had in mind, but for the tougher puzzles you could end up with a ton of labels in the cells.

Yeah, I've thought about how to address this, too. Displaying a huge list of dozens and dozens of patterns just makes the whole thing humanly unreadable anyway (not to mention that the table grows way off the screen), so it would probably be better to just hide them until the user wants to see them. Good suggestion.

Anyway, glad you like it so far. I'll take the liberty of consulting you on the algorithms if it becomes necessary to extend them further.

Vidar