Sudoku Players' Forum (clone)

Myth Jellies wrote: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.

I have a question and a remark.

Question: What (or where) are the others Tso's Killer Sudokus?

Remark: The puzzle above can be solved without T&E and without POM.

Thanks in advance.

Carcul

Carcul wrote:Question: What (or where) are the others Tso's Killer Sudokus?

I just happened to be reading what seems to be the thread in question, <here>.

Carcul wrote:Question: What (or where) are the others Tso's Killer Sudokus?

I believe it was one of several puzzles provided in a Tso response in another thread. I really don't know where the puzzle originated. [Edit: r.e.s. found the thread (thanks r.e.s). My apologies for misrepresenting the credit for the puzzle.]

Carcul wrote:Remark: The puzzle above can be solved without T&E and without POM.

If I claimed otherwise, chalk it down to the folly of youth. There's a bunch of stuff in some of those earlier posts that I look back at now and wonder what was I thinking.

I hope that you do see that POM is quite different from other methods, is very powerful, and allows for a lot of creative thinking on the solver's part. So much creative thinking, as you can tell from the post, that I am somewhat surprised that vidarino's program is as effective as it is. It will be very intriguing to see how far it gets against some of our most difficult puzzles.

R.e.s. wrote:I just happened to be reading what seems to be the thread in question, <here>.

Thanks R.e.s., it turns out that I already knew that thread after all.

Myth Jellies wrote:I hope that you do see that POM is quite different from other methods, is very powerful, and allows for a lot of creative thinking on the solver's part.

I agree that POM is very powerfull, but with the application of it that you have described in the thread "Advanced POM: Taking on a Killer Tso Puzzle" it looks very hard to apply by hand in the solving of a puzzle (correct me if I am wrong), and manual solving is my primary interest. So, I was just pointing out that, for some possible interested reader, the puzzle in question can be solved in almost one third of the steps by other not less interesting (and simpler) methods. Obviously, I was not and I am not reducing the importance of POM. I don't know if the following expression exists in English, but in Portuguese we say something like "For a good understanding person, half a word is enough."

Regards, Carcul

Allrighty, I've just spent a large chunk of the weekend rewriting a substatial part of the POM analyzer internals. It now supports much larger pattern sets (up to some 700 patterns per digit, and easily extendable if need be). The current system is; a-z, then Aa-Az, then Ba-Bz, etc., up to Za-Zz.

Consecutive patterns are now grouped together; abcde => a-e, defghjkmnopq => d-hjkm-q. Perhaps a bit more tricky to follow, but easier on the eye (and web browser) on large sets. (I'm planning to make this adaptive. I.e. switch to compact form when the number of patterns go over a defined threshold.)

Also, when doing equation substitutions, it now goes 4 levels deep, so to speak. (Se previous post for explanation of what "deep" is.) I have yet to find a grid that requires more than 3, though, so I think I'm erring on the safe side.

It does not yet crack the puzzle in the original "Tso's Killer Puzzle" posting, but it's getting closer, I think. (I've added that puzzle to the top menu for easy access.)

But I'm going to be needing some hints from Myth Jellies or some other POM guru as to how to proceed from here. I've read through the "Killer" story a few times, but I'm having a hard to mapping the techniques into a computer algorithm. (I'm not even sure I understand what's going on myself... I've made the solver spit out its current equation database when it gets stuck, as an aid in finding more reductions.

One small note; The server which hosts the solver isn't exactly the spiciest piece of hardware around, unfortunately, so it's not particularly fast, and I get occasional timeouts when running it on complex grids. Also, it's putting a bit of a strain on the rest of the server, so if it gets hammered on a regular basis, I'll have to find a new home for it. (I'll host it on my home box if it comes to that, so it's no biggie.)

Vidar

Update: It seems I don't need any help after all.

I added an extra "feature" to the equation gatherer; If any generated equation has only one candidate on the right hand side (i.e. bivalue cells), the equation is valid in both directions. Adding this little obviousity(?) to the code did the trick.

Example:
- We have patterns "1abcd" and "2abcdef", and a cell with candidates "1ab" and "2ab".
- From this we get basic equations "1cd = 2ab" and "2cdef = 1ab"
- But since these only have one right hand side, they have equally valid counterparts "2ab = 1cd" and "1ab = 2cdef"

This little extension cracks the "Killer Puzzle". It takes a little while to run (and some 70 steps, if I recall correctly), but it gets there eventually. (And I still can't fathom how MJ managed to do that by hand!)

Vidarino,

Ah yes, A = B implies B = A. Dang computers, you have to spell out everything for them

Here is another little trick that may be of use to your program .

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

Using the quoted example, remember we got three equations from the cell containing 3 candidates. But what if we have managed to derive one of these equations from other equations, and there is no "cell"?

We can still get the other two equations using the following trick
Assume we have derived 8abcdfg = 1b 9c.
Note that TRUE = 8abcdefg = 1ab = 9abc.
Thus we can say

TRUE + 8abcdfg = 1b 9c + TRUE
1ab 8abcdfg = 1b 9c 8abcdefg
cross cancelling gives you
1a = 8e 9c

also

TRUE + 8abcdfg = 1b 9c + TRUE
9abc 8abcdfg = 1b 9c 8abcdefg
cross cancelling gives you
9ab = 1b 8e

So you can alway derive the other equations from one, even without a cell to base them on.

Hmm, darn, it sounds so obvious now that you have pointed it out...

This means you can basically move a set from one side of the equation to the other by "inverting" it.

The upside is that I'm almost certain that this technique will make the solver crack just about anything. (It almost does so already, but I've found a few that still won't budge.)

The downside is that it's a computer, and needs exact instructions. I guess the simple "brute force" way would be to pre-generate every possible combination of equations and iterate through them to find substitution-eliminations. I'll do some thinking on how to attack this in a less CPU and RAM intensive way, though...

Great tip. Thanks a bundle.

Here is a POM observation which might be of some interest to those who like nice loops / forcing chains / uniqueness. If cells A and B are vulnerable pairs for the digit n then A <> n implies that B = n; and B <> n implies A = n. We know this holds because A and B contain all of the potential solution patterns for N, therefore they cannot both be false.

It works in the other direction too. If A <> n implies that B = n; then A & B are a vulnerable pair. You can eliminate all potential patterns for n which are not in either A or B. Note that you can use this rule with almost unique rectangles of the form

Code: Select all

ab  | abn
    |
abn | ab


to kill all potential patterns of n that are not part of this structure.

More generally, since you know a, b, and n must all be a part of the following to avoid multiple solutions,

Code: Select all

abn | abn
    |
abn | abn


You can kill all potential patterns of n, a, and b, that are not part of this structure. [Edit: eliminated the untrue portion of this statement]

The program at the moment still gets stuck (after step 21) for this old puzzle of mine:

Code: Select all

..9|.7.|.8.
..8|..6|...
...|8..|6.5
-----------
..3|..2|.5.
..7|6..|...
1..|..5|..9
-----------
.4.|...|.92
7..|...|..3
9..|.1.|5..

23456 12356 9     12345 7      134    1234  8     14         
2345  12357 8     12345 2345   6      9     12347 147       
234   1237  124   8     2349   1349   6     12347 5         
468   689   3     1479  489    2      1478  5     14678     
2458  2589  7     6     3489   13489  12348 1234  148       
1     268   246   347   348    5      23478 23467 9         
368   4     156   35    3568   378    178   9     2         
7     1268  1256  2459  245689 489    148   146   3         
9     2368  26    234   1      3478   5     467   4678       


I called it this way
BTW, i still dont know a way to solve it manually, maybe one of the newer techniques could apply.

Hi Wolfgang.

Wolfgang wrote:The program at the moment still gets stuck (after step 21) for this old puzzle of mine:

Code: Select all

..9|.7.|.8.
..8|..6|...
...|8..|6.5
-----------
..3|..2|.5.
..7|6..|...
1..|..5|..9
-----------
.4.|...|.92
7..|...|..3
9..|.1.|5..


BTW, i still dont know a way to solve it manually, maybe one of the newer techniques could apply.

This is one of the most interesting puzzles that I have met so far. Where did you get it? Anyway, I have now solved manually this grid in 15 steps, although I have used one or two quite complicated multiple implication nice loops. This is an excelent puzzle, where some quite advanced and interesting nice loops can be found.

Regards, Carcul

Carcul wrote:This is one of the most interesting puzzles that I have met so far. Where did you get it?

It was one of the first puzzles i posted about a half year ago. It was looked at being uninterestingly difficult and for me it is it still today. With a forcing net over 22 cells i could fix r7c1=8, but this does not solve the puzzle. You seem to play in a higher league

Wolfgang wrote:It was one of the first puzzles i posted about a half year ago. It was looked at being uninterestingly difficult and for me it is it still today. With a forcing net over 22 cells i could fix r7c1=8, but this does not solve the puzzle. You seem to play in a higher league

fixing any one of these (backdoors) cracks the puzzle:

Code: Select all

[1,2]=1[6,7]=8[8,3]=1[9,9]=8

Hi Gsf.

Gsf wrote:fixing any one of these (backdoors) cracks the puzzle:

Code: Select all

[1,2]=1[6,7]=8[8,3]=1[9,9]=8

Very nice. But how do you make these deductions manually, without trial and error? Could you post your logical arguments for these backdoors?

Thanks in advance.

Regards, Carcul

Carcul wrote:

Gsf wrote:fixing any one of these (backdoors) cracks the puzzle:

Code: Select all

[1,2]=1[6,7]=8[8,3]=1[9,9]=8

Very nice. But how do you make these deductions manually, without trial and error? Could you post your logical arguments for these backdoors?

that's the rub for sudoku and other constraint satisfaction problems
most are known to have small backdoor solution sets
but no one has come up with a method to identify the backdoors
besides exhaustive search

backdoor must be qualified by the logic methods being applied
using the 2 simplest constraints the conjecture is that
the maximum minimal 9x9 sudoku backdoor set size is 2
most of the hard puzzles posted on the forums have backdoor set size 1

n-constrained means the minimal backdoor set size is n

here's a 2-constrained (not including cycle methods) puzzle with 39 backdoor pairs

Code: Select all

. . 3 | 4 . . | 6 . .
. 5 . | . . 9 | . . .
. . . | 2 . . | . . 5
------+-------+------
2 6 . | . 7 . | 1 3 .
. . . | 8 . . | . 6 7
9 . . | 3 . . | . . .
------+-------+------
5 . . | . . . | . . 8
. . 4 | . 2 . | . . .
. 1 . | . . 3 | 7 . .


the pairs with values are

Code: Select all

[1,1]=1*{[2,3]=6}
[1,8]=8*{[2,3]=6[2,4]=1[3,1]=7[7,4]=6[7,6]=1}
[1,9]=9*{[2,3]=6[7,4]=6}
[2,3]=6*{[2,5]=8[3,8]=1[6,6]=4[7,2]=9[7,7]=3[8,2]=3[8,8]=9[8,9]=1[9,5]=9}
[2,4]=1*{[9,5]=9}
[2,5]=8*{[7,4]=6}
[3,1]=7*{[3,2]=8[3,8]=1[7,2]=9[8,2]=3[8,9]=1[9,5]=9}
[3,6]=6*{[7,3]=7[8,1]=6[8,4]=7[9,5]=9}
[3,8]=1*{[7,5]=4}
[6,6]=4*{[7,4]=6}
[7,2]=9*{[7,3]=7[8,1]=6[8,4]=7}
[7,3]=7*{[9,5]=9}
[7,4]=6*{[9,5]=9}
[7,6]=1*{[9,5]=9}
[8,1]=6*{[9,5]=9}
[8,4]=7*{[9,5]=9}


solve any pair (one left of * and one right of *), e.g. [1,8]=8[2,3]=6,
and the puzzle cracks

so do any of the cycle/loop/pattern methods identify any of the backdoor
pairs for this puzzle?