The New Sudoku Players' Forum

[stuartn]

This is on ' another site'...

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

This is the famous "toughest known puzzle".

Solving this puzzle requires an advanced deductive technique called Tabling. Currently, the only app that implements tabling is the Sudoku Susser.

What exactly is 'tabling'?

stuartn

[Karyobin]

I'm commenting on this simply because I don't want it to fall out of everyone's notice. This is certainly a seriousy tough puzzle (for me, anyway), so come on you battery of clever-clogs out there, let's have an explanation of 'tabling' - or at least an explanation of how to solve this one with our methods.

[george-no1]

I've heard of something called 'Bowman Bingo', but I don't know what it is. I think I may have heard in this kind of context. Otherwise, good luck everyone, a few solvers I've tried said there was no solution.

G

[Doyle]

FYI: I Googled "sudoko tabling" and was led to a solving program named Sudoku Susser, freeware, that mentions tabling, whatever that is, as one of its routines. However, it's for the Mac only, so had to pass.

[Nick70]

Tabling has been described here.

It is a further generalization of simple forcing chains, more powerful because it can concatenate them.

E.g. a multiple forcing chain applied to this puzzle would be:

Code: Select all

r6c2=1 => r1c2<>1 => r1c2=2 => r3c3<>2
r6c2=2 => r7c2<>2 => r7c3=2 => r3c3<>2
r6c2=9 => r3c2<>9 => r3c3=9 => r3c3<>2

From any possible starting point you can get to the same conclusion, so the conclusion must be true. However, to reach that conclusion, simple forcing chains are used--a succession of strong and weak links where each statement is implied by the one preceding it.

Tabling can draw more conclusions from forcing chains.

For example, let's say that r1c1 can be 1, 2, 3 or 4.
If r1c1=1 or 2, then r2c2=4.
However, if r1c1=3, we don't know what r2c2 will be.
Now let's say that r4c4 can be either 7 or 8.
If r4c4=7, then r1c1<>3.
If r4c4=8, then r2c4=4.

Simple forcing chains will not be able to do anything with the above data, because .
Tabling, however, will. It will conclude that r2c4=4 no matter what you put in r4c4.

At least, that's my understanding, since the details of the algorithm haven't been published yet.

[pjdowney]

215876943
678394215
349125876
587432169
463981752
192657384
826743591
734519628
951268437

and this is the only solution.
My quickbasic program doesn't seem to care if the puzzle is
"difficult" or not because of the complete search routine.
I am working on some of the fundamental questions in sudoku, such
as the number of legal arrays and the minimum clue matrix.
I am solving 75,000 arrays a minute on a hyper threading machine but it is not nearly fast enough. More analysis is required, not brute force. I am starting to consider using monte carlo techniques for answer approximations until I get a better hold on the problem. /pjd

[Big Blue]

...has turned out to be extremely difficult for me.

I had to resort to proof by contradiction (for those who believe in logic is all you need for Sudoku) aka trial&error (for those who believe there are things beyond logic needed for Sudoku), and it took me hours to prove that r1c2 is NOT the number 2, but the other candidate.

The bivalue and bilocation graphs were only useful at later stages.

I'll try to apply tabling to this puzzle once I have understood what it is, it sounds wonderful...

Just a remark: this puzzle contains an awful lot of threesomes - three candidates for a cell or three possible locations for a number. So I thought there should be a generalization of bi-methods to trivalue and trilocation graphs. Has anybody thought about these issues?

I attempted to draw a trilocation graph and it looked horrible. I proceeded as follows: connect the three vertices by edges and label the ensuing triangle with the corresponding number. If you are lucky (I wasn't) you might find a tetraeder or some other closed surface, which should be the trilocation equivalent of a closed path in the bilocation graph. If, for instance, the 4 faces of the tetraeder have all different labels, then you can eliminate all numbers besides these 4 from all vertices of the tetraeder. If one digit repeats itself then this will yield some restriction on the vertices similar to closed cycles with 1 repetition. Probably there is also something comparable to "conflicting paths", but the problem is just that my drawing is so awful that I could not spot anything. Note also, that the trilocation graph can/should be combined with the bilocation graph to establish more restrictions.

Anyway, I gave in and used proof by contradiction.

[Max Beran]

Big Blue; how about giving it more of a go? The way I see it is that the very basic unit of decision making includes an element of trial and error so there is always going to be some ambiguity at the boundary between what is a bifurcation method and what isn't.

It was your trilocation idea that suggested a usable strategy. Because or our two-value logic all viable methods are going to be based on pairs, even in bi- or tri-location diagrams. So to turn the trilocation diagram into something that is usable requires that one of the other numbers is "collapsed". And what is that but another way of saying bifurcation.

What the puzzle needs is more bivalue and bilocation opportunities, not just for Eppstein's moves but all the other devices in the toolkit. After the 8 in r1c4 and r5c5 plus a little tidying, which is the limit of simple logic as far as I can see, there are only six cells with pairs and an extremely lean looking bilocation path map. The number one reason for this is the blockage due to having such a dearth of 1's.

So my suggestion is to try to fix a couple of 1's, say in blocks 4 or 5, with 9's to follow, in order to clear the decks and get some real decision paths going. I've already had a little look (aided of course by Angus' program) at what happens if you force a 9 into the right cell and it certainly opens things out hugely. It is instructive to see the bilocation map grow as you make an assignment.

I think one will still get a sense of achievement out of minimising the number of forced cell assignments and bringing the more "kosher" logical devices into play at the earliest possible moment. In particular can this puzzle be solved by just a single forced cell?

[Big Blue]

Regarding tabling: I have read the thread mentioned by Nick70. I am afraid that I do not have "inhuman patience", as apparently required for successful application of this method ("inhuman patience" is what the creator of this method seems to require, see the thread - link is above in a post by Nick70).

The problem I have with tabling is the following: it does not tell you where to start looking, which patterns to follow etc. It is, IMHO, only slightly better than educated guessing or random guessing for humans - for programmes it might be a different story, but my ambition is to solve Sudokus by hand in a way that is not just pure bureaucracy.

I strongly advocate graphical methods, mostly because I am used to this kind of "doing calculations by looking at pictures", but also because IMHO geometric proofs are far more beautiful than algebraic ones - seeing is proofing, cf. Pythagoras for the canonical example.

Now, regarding the puzzle at hand: I agree with Max - bilocation and bivalue methods are useful only at much later stages. The bi-networks are not very dense initially.

Still, I was able to use especially the bilocation graph to eliminate some candidates in the first three columns, once I combined them with my trilocation triangles.

I still need a lot of practice with trilocation graphs, but it works better than I had hoped initially.

At one instant one particular trilocation triangle (in column 4) for all practical purposes turned out to be a bilocation edge - this is an interesting property, so I think the trilocation graph methods may have their merits once they are better developed.

There are certainly a lot of simple rules that you may establish in this way.

[Wolfgang]

This is a really tough one
I tried per program, which of the numbers can be eliminated by contradiction without advanced techniques, ie i inserted one candidate after the other and let the program try to solve it using box elimination (1) and pairs, until it either came to a contradiction or would have had to guess. There are only a few (compared to other sudokus) that you can eliminate this way and each needed a lot of steps.
The upper code is, from where i started, the other after all (single) eliminations (unfortunately cant use colors in code)

Code: Select all

1256 12    1258   1368 7    1236   9     4     1236       
126  7     1248   1368 9    12346  2368  136   5         
3    1249  12489  168  1248 5      268   7     126       

259  8     7      4    235  2369   1     3569  2369       
4    6     3      1589 1258 129    257   59    279       
1259 129   1259   3569 235  7      23456 8     23469     

8    12349 12469  7    1345 1349   3456  13569 13469     
7    1349  1469   1359 1345 1349   3456  2     8         
19   5     149    2    6    8      347   139   13479     
---
1256 12    158    1368 7    126    9     4     1236       
26   7     48     138  9    24     238   136   5         
3    49    9      168  124  5      268   7     126   
     
59   8     7      4    235  26     1     3569  2369       
4    6     3      159  8    1      27    59    279       
1259 129   1259   569  35   7      346   8     46     

8    12349 126    7    45   349    456   1569  1469     
7    349   46     159  145  349    456   2     8         
19   5     149    2    6    8      347   139   13479     



PS: the only guess that would solve it this way is r9c7=4

[tso]

FYI: I Googled "sudoko tabling" and was led to a solving program named Sudoku Susser, freeware, that mentions tabling, whatever that is, as one of its routines. However, it's for the Mac only, so had to pass.

Actually, it runs under Mac, Windows and Linux. I use it under windows. Killer, must have ap.

[Max Beran]

My suggestion that this could be converted into a "what's the smallest number of forced cell assignments" is ruined by rediscovery that a 4 in r9c7 solves it without the need even for a x-wing let alone a bilocation chain.

[Ocean]

My suggestion that this could be converted into a "what's the smallest number of forced cell assignments" is ruined by rediscovery that a 4 in r9c7 solves it without the need even for a x-wing let alone a bilocation chain.

My experience is that for most 'hard' sudokus there is only one really tough step. That means it is possible to reach the solution by proper guessing and solving two branches - but this is not fully satisfactory. The goal is to find all the logical steps - and preferably the simplest or shortest solution path.

[Big Blue]

I think it is possible only in retrospect to see which one is the critical cell, i.e., a cell where an "educated guess" collapses the sudoku.

Or is there some "derivation" that in r9c7 only the number 4 can enter? (besides trial and error)

While "educated guessing" may be faster than some of the more advanced methods (like tabling, for instance) usually these advanced methods help you to guess educatedly in the first place - by looking at bivalue or bilocation patterns very often you sort of "spot" the best candidates ofr critical cells.

[Wolfgang]

Maybe i should mention the following.
The numbers i eliminated above include all you might be able to eliminate with many advanced techniques like triples, coloring, forcing chains, xyz-wings etc (not swordfish and quads). I didnt study bilocation graphs (?).
So looking above, i dont believe that there is "some derivation that in r9c7 only the number 4 can enter".