The New Sudoku Players' Forum

[AMcK]

Tabling has been described here.
It is a further generalization of simple forcing chains, more powerful because it can concatenate them.
... the details of the algorithm haven't been published yet.

In fact, there version of Mad Overlord's Sudoku Susser for Wimdows, Mac and Linux downloadable from http://www.madoverlord.com/projects/sudoku.t

It's an excellent piece of software which shows just how well it can be done.

Although the full algorithm for tabling hasn't yet been published, you can switch on the option "Show Trebor's Tables" to trace exactly how the algorithm constructs the proof.

When fed on "toughest" it does seem to perform even better than concatenated forcing chains. My "Ultracolouring" solver (which incorporates contradictions and ver(ac)ities) stalled at a position that still seems to require a depth=3 search.

When I fed this partial solution into the Susser and compared the transcript with my Ultracolourer, I was able to see clearly how it manages to make the additional implications necessary to solve the puzzle "logically". It did take me a few false attempts and a few hours, which probably rules it out for those only interested in manual solving.

I'd like to check my results carefully and dicsuss them with Mad Overlord before making them public.

However, I feel that we may be approaching some kind of limit for strictly logical solvers.

Regards
Andrew

[stuartn]

Andrew - very helpful - thanks.

If we are approaching a limit - and I too suspect that there is one, how will we know what defines it? - will we able to say - 'Nope - don't even try that one because it's got etc etc' ?

Nice day in London today.

stuartn

http://www.brightonandhove.org/Sudolinks.htm

[Wolfgang]

In fact, there version of Mad Overlord's Sudoku Susser for Wimdows, Mac and Linux downloadable from http://www.madoverlord.com/projects/sudoku.t

yes, its really working under my debian linux also

Although the full algorithm for tabling hasn't yet been published, you can switch on the option "Show Trebor's Tables" to trace exactly how the algorithm constructs the proof.

eeh, what i see is, the conclusions are made out of

A total of 6887 implications about the puzzle were generated ...
A total of 5752 implications about the puzzle were generated ...
A total of 8009 implications about the puzzle were generated ...

Can one follow this manually (eg it shows that r1c1 cannot be 2, because it follows from all candidates {1258} in r1c3 that r1c1<> 2 - in the same way i could "try" 2 in r1c1 and show that no candidate is left then for r1c3) ? Is it easier/better than using t&e (or proof by contradiction, if one wants to to call it this way) ?

... which probably rules it out for those only interested in manual solving.

so i think about the presented solution ...

[Max Beran]

I never meant to suggest there was any a priori reason for forcing a 4 into r9c7. What I was suggesting is that in cases where trial and error is necessary it would be interesting to find steps that minimise the role of trial and error and maximise the role of logic. Unfortunately in this case the answer is one more than what was given because there is this trial and error solution that we know about (and is deeply unsatisfying because the onward path is so simple).

Perhaps one would have to be more specific about what is meant by maximising the role of logic, e.g. to include methods beyond the simplest cell-fillers. And that introduces subjectivity.

Big Blue, I know precisely what you meant by spotting prime candidates on the basis of the bilocation diagram. I did one for an arbitrary assignment of the 1 in box 7. There were no Eppstein-type paths but you could see certain cells were screaming out for forcing to allow whole new sets of pathways to be opened up which were blocked, eg by contiguous paths sharing the same label, and which would have led to Eppstein paths. However when I checked these cells against the known solution they were not all by any means correct - perhaps 3 out of 5 would have been a step in the right direction and the other 2 a blind alley.

[Sue De Coq]

Mad Overlord has claimed it's possible to deduce the following in the published position by 'tabling' forced chains:

r3c3<>3
r7c3<>9
r8c3<>9

Nick has explained the forced chains that underlie the first deduction. Here are the chains for the second:

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

Does anyone see the chains for the third?

[Big Blue]

Max: I agree - it just would have been nice if there actually WAS a constructive proof that r9c7 is 4; it would have been an elegant way to solve the puzzle...

I think the main problem with this particular puzzle is the way to organize the threesomes into something useful. Tabling is pure bureaucracy and trilocation triangles don't give you enough info unless you draw all of them, together with the trivalue network - but if you are able to spot anything in this bizarre collections of edges, vertices and triangles then you might as well solve quantum gravity, I suppose ;-)

In a sense, for my current abilities this puzzle is simply too difficult, I have to admit - yes, I did solve it, but in a way that I consider very ugly. Although it was quite fun to eliminate some candidates by trilocation methods, I was not able to solve the whole thing in this way and eventually had to "guess" (as usually, I guessed wrong first).

What worked quite nicely is to use some closed paths in these networks and to assume at some "critical cells" that there was a number different from the labels attached to this vertex - and thereby show some contradiction. If by such a reasoning a sudoku could be solved I would say "Wow! Tough, but constructed beautifully!" - but if after such sophisticated methods you still have to resort to guessing or bureaucratic excesses it is a bit frustrating...

In order to get practice with and reveal the the usefulness (or uselessness) of trilocation/-value methods I should start with simpler sudokus, which still are sufficiently difficult...

So... please, please is there somewhere a list of sudokus which are not quite in the range of the one above (or TILPS' most difficult one), but which are still so complicated that x-wing + co. is not sufficient?

[AMcK]

r6c2=9 => r3c2<>9 => r3c3=9 => r7c3 <> 9
Does anyone see the chains for the third?

Aren't these just conjugate 9's in c2, r3 and c3?
I can cope with that
AMcK