The New Sudoku Players' Forum

[TFC Rob]

I’m fairly new to Sudoku. After spending 2+ hours on my first gentle puzzle, I started reading various documents on solving Sudoku using a sharware program to explore the various techniques. My program can auto-calculate the pencil marks (which is really just a bookkeeping task), and will also allow you to take one step in a solution and show you how it came to that move – a feature that, for me, accelerated my understanding of how the basic strategies, like naked pairs, hidden pairs, etc. , are utilized. So now, I find that the most difficult puzzles I can locate online, labeled fiendish, very hard, difficult, are solved fairly quickly with the application of just a few of the common strategies. Once you get past the crux of the puzzle, it comes together as a series of unique values. Not that much fun.

There are many discussions of advanced techniques like X-wing, starfish, and, for really difficult puzzles, guessing (or Ariadne’s thread as describe by Michael Mepham in his online document “Solving Sudoku”). I’ve not found a puzzle that comes close to requiring these more “advanced” techniques.

I don’t claim high skills in puzzles. Sudoku was my entry into the realm of calisthenics for the little gray cells in a belated attempt to forestall the decline in function.

Am I missing something?
Is Sudoku mostly about bookkeeping?

[Wolfgang]

... I’ve not found a puzzle that comes close to requiring these more “advanced” techniques.

I agree that it is cumbersome to find them. Most hard, very hard, fiendish and diabolical puzzles can be solved with the simple techniques. The most of the interesting puzzles i found, are under those that have been discussed here. Then there are some of the very hard of the "daily sudoku" and a few else, eg the first 2 of www.tiscali.co.uk/games/play/sudoku/hard need xwing.
xwing puzzles i can generate myself, eg this one:
..6|.58|3..
.9.|23.|6..
7..|...|4..
-----------
8..|9..|..6
..9|6..|..1
...|.12|...
-----------
9..|.25|..4
...|74.|...
.5.|..9|8..

[tso]

I totally feel your pain. There are several descrete levels of difficulty beyond which are typically published.

There are lots of extremely hard puzzles scattered around in The Sudoku Programers Forum, many of which are beyond the deductive powers using known methods by most humans. For example, this one by NICK70:

Code: Select all

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



... and another from RUBYLIPS:

Code: Select all

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


TILPS says this is the hardest of 1000000 s/he generated:

Code: Select all

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



Another TILPS:

Code: Select all

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


The majority of the puzzles below will be far less difficult than the ultimate level puzzles above.

There are currently 150 "outlaw" puzzles here. that may require x-wings, swordfish, forcing chains, etc. Also, his solver will give a descriptive rating of any puzzle you enter. If it says "Outlaw", it's likely to be beyond publishing levels.

These are nice, these too, because in addition to being difficult, they are named according to what solving method you'll need -- swordfish, x-wing, etc. You don't need his software to read the puzzles, as they're in a simple text file. (The extreme setting on his program creates puzzles harder than anything published.)

The "unreasonable" setting on SOLO can go beyond anything published.

SOME of Fiendish created by this one are beyond published levels, but you have to replace the template file with one of your own in order to get any at that level. Here's one I made that should require forcing chains or an analog of that method:

Code: Select all

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


Plus, you can make mid range puzzles harder and hard puzzles challenging again by using only a pen -- no making notes. Because you're right -- it does eventually come down to housekeeping and searching if the puzzles are not hard enough.

[dukuso]

deleted

[Wolfgang]

tso, many thanks for the links, i didnt know half of them

[TFC Rob]

I was uncomfortable posting my query in the first place, but your responses show that there is indeed a demand for more challenging puzzles.

The discussion under Wishlist (http://forum.enjoysudoku.com/viewtopic.php?t=634) deals with some of the issues I had raised. It was suggested that the difficulty ratings perhaps refer to the context in which the puzzles are solved. That is, filled in with pen or pencil on newsprint, for example, where it is difficult to do the full pencil marks that can be done easily with software, a gentle puzzle can indeed be relatively challenging. I can appreciate that distinction, and do enjoy pulling out a puzzle with pencil in hand. However, I very much appreciate the leads given here.

Thanks for the great info.

Rob

[tso]

Dukuso put together a list of hard Sudokus HERE.

[tso]

Medium/hard:

Code: Select all

 7 6 . . . . . . .
 5 . 9 . . . . . .
 1 2 . . . . 7 5 .
 3 . 7 . . . 2 . 1
 . . . . . . 6 9 .
 . . 1 8 7 . 4 . 5
 . . 6 . 4 . 8 2 .
 . . 5 . 3 . . . .
 . . 3 1 8 . . . .


Fiendish/outlaw:

Code: Select all

 8 2 . . . . . . .
 4 . 1 . . . . . .
 3 5 . . . . 2 6 .
 9 . 4 . . . 5 . 7
 . . . . . . 9 8 .
 . . 5 6 9 . 3 . 1
 . . 9 . 7 . 8 3 .
 . . 2 . 1 . . . .
 . . 8 5 4 . . . .


[darq]

these were rated outlaw

Code: Select all

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

Code: Select all

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

[Big Blue]

Has anybody tried to solve the first TILPS Sudoku mentioned in tso's message (the one which is "the hardest of 1000000")?

It took me two evenings to figure out the solution, and I wonder whether I had overlooked any short cuts.

Without spoiling the fun I think I can reveal that I had to perform a binary trial and error on 3 occasions. Like a very long forcing chain which eventually ended in contradiction.
Incidentally, I always chose wrong first, which is probably why it took me ages to finish...

But at least I am sure now that the solution is indeed unique

Thanks to TILPS for finding this Sudoku and to tso for posting it here!

[udosuk]

That "hardest of 1000000" puzzle, I think the "key" missing clue is R7C7.
You have 3 choices for that one, one will lead to a contradiction pretty soon, another will lead you to the unique solution. The 3rd choice, after you apply all the possible logic, still need one more binary trial-and-error at the central R5C5 square (both with pretty long branches/forcing chains towards contradiction...)

That's the best T&E analysis I have done on that one, a total of 4 branches...

[swjms]

If you go to http://websudoku.com/ then click on hard or evil. I think they are pretty hard.

[Big Blue]

@udosuk: I suppose you mean R2C7 instead of R7C7? I used precisely that column, although instead of employing the row with a triple choice I used the two rows with binary choices, which of course amounts to the same. You are right that one case almost immediately leads to a contradiction (although IMHO it still takes long enough so that you actually have to try it - at least I did not spot the contradiction just by staring hard at the partial sudoku), while the second case splits into two subcases both of which take some time.

So it appears that there is no simpler way! Amazing...

You are also correct that even after C7 is finished there is still one binary ambiguity left that has to be solved by a long forcing chain (a.k.a. "trial and error") - but funnily here I used R3C2 instead of R5C5. The branch which led to contradiction was a bit lengthy, but the other one (leading to the unique solution) collapsed pretty fast.

I think that this sudoku by TILPS may be considered as a "canonical" sudoku to test the efficency of solving routines - it is a very nice example of "extended forcing chains".

I know the notion of "hard" is rather subjective, but... if anyone is able to produce a sudoku which is even harder than "TILPS 1000000" please post it here!

[dukuso]

my old "bifurcations-solver" solves this without "guessing".
It only considers furcations with two forks and always
fills in forced placements immediately.
Forced = the canonical 324 constrints.

I can send a (long) logfile (48K) by email. (sterten@aol.com)
if someone wants to figure out a bifurcations-solution.
I was too lazy to do it by myself.

My new, faster, backtracking solver uses 8 guesses and
172 placements, which is not so bad, when you consider
that a forced puzzle already takes about 50 placements
just to fill in the numbers.

[udosuk]

Big blue, now you're confusing me... maybe it's best if we share the details more (people who want no spoiler can click away now).

Okay, after some obvious steps (singles, hidden 1's) the cell R7C7 (no mistake) has 3 choices: 3, 5 & 6:

Try 3, then after some chains there will be a contradiction on ROW 3 (2 cells, R3C2 & R3C7, must be both 6).

Try 6, then it leads to the unique solution pretty straightforwardly... (I mean if a solver program make that choice randomly at the start, it will think the puzzle is actually quite easy peasy...)

Try 5, then you are stalled after a couple more steps. Then you have 2 choices in the central R5C5 cell: 3 & 8:

Try 3, then after a pretty long chain (over 20~30 cells filled) you'll discover that 2 cells in BOX 4 (R4C2 & R5C3) must be both 9...

Try 8, then again after a similarly long chain there is a contradiction in BOX 1/COLUMN 3 (R1C3 & R2C3 must both be 5)...

So, there are a total of 4 branches:

R7C7=3 -> contradiction
R7C7=6 -> unique solution
R7C7=5 -> R5C5=3 -> contradiction
R7C7=5 -> R5C5=8 -> contradiction

I suppose it's similar to use R3C2 (6 or 7) instead of R5C5... but they both lead to double contradictions and I think the chains on R5C5 are slightly shorter... maybe I should do a step count...

Don't understand your R2C7 or "two rows with binary choices" reasoning though. Elaborate more please...