Hardest Sudoku Ever

kammi · Posted: Mon Nov 27, 2006 7:23 pm Post subject: Hardest Sudoku Ever

Hi... I'm relatively new to Sudoku and just finished my 1st Sudoku Solver & Generator.

I am wondering what would be the hardest Sudoku of all times, so I can put my code to the limit. So far the hardest Sudoku I've been able to generate is this one:

400000108
000630042
000000000
006340007
730000000
900050000
070200083
002010500
600900004

2 questions:
Is this really a hard Sudoku ? (and how can I objectively rate this?)
Does anyone know a reference to the real 'hardest sudoku ever' ?

Regards
Arnold

daj95376 · Posted: Mon Nov 27, 2006 7:49 pm Post subject:

Nice puzzle Arnold, but far from being the hardest. There's a long thread here about finding and ranking the hardest puzzles.

dmkAlex · Posted: Sat Jun 02, 2007 2:04 am Post subject:

My solver solved it in 22 trials.

atkman · Posted: Fri Jan 04, 2008 6:30 pm Post subject:

A very hard sudoku will need to contain X-Wing type solving techniques, unless there is a harder way. How would one create something like the question.

brasshopper · Posted: Tue Jun 02, 2009 8:37 pm Post subject: difficult puzzle

I am attempting to write a solver that more or less duplicates what a human would do when solving a puzzle. This is hard, because my human will almost certainly do something different in real life - it is hard to predict what patterns a human would actually be likely to see and I'm just starting to refine that.

Right now, in general, I'm applying gross techniques. The first technique I apply is to look for solo candidates - if there is only one "1" in a row, column, or cell, it wins.

Then I look for solo candidates (although if I've placed 2/3rds of the potential numbers, I do solo candidates first).

Then I start on candidate reductions - I look for naked sets, and then for hidden sets.

After that, I do "box/line" reductions - when the only candidates on a line are in a box, and so forth.

After that I do xwing and fish of any rank.

And, while I have plans to code more techniques, you reach a point where it is simpler for a human to just do guess and select. As far as I can tell, any puzzle that has multiple solutions must be solved using trial guessing techniques and the multiple solutions will show up in the guessing. But it is not practical for a human to solve a whole puzzle using trial guessing. Furthermore, you want to reduce the trial set as much as you can before resorting to guessing.

I use a simple recursive technique to do the guess and select stuff, and if I have to do one guess, well, I do the technique and then place the rest of the numbers. But I always try all the alternatives to see if I can get more than one valid solution. Between guesses I try to place as many puzzle

So I only found one valid solution, and I had to make five guesses to solve it. To answer the person who thought that a hard puzzle required x-wing sorts of techniques, I am reasonably sure that I reduced no candidate sets from winging before my first "guess" but I did reduce candidates after the first winging.

You provided 25 numbers. I placed 18 before my first guess. Only 2 numbers were placed after my first guess. 68 numbers are placed before my next guess, but that tree is dead. We drop back to the 40's and make an alternate selection. We guess at 49, and run into an xwing at 55. That does not help us, we have to make a guess at 55. up to 72 and back to 55 again. Another guess at 58 this time, and we find our solution going from 58 to 81.

Then we run from 55-78 before we fail, and we are probing from 49. It fails at 66 and we are probing at 44. And on and on - no other leg of the search arrives at a solution - and we saved the one good solution.

As far as my solver is concerned, this is a difficult puzzle. I have never thrown a puzzle at it that has taken more than three levels of guessing, and as I said, this one took 5.

Now, I suppose that I could look for an optimum path through the guesses. Right now, I just pick a position and work through the choices. I know that if I choose differently, it may take a different number of guesses.

Tobitab · Posted: Mon Dec 14, 2009 1:50 am Post subject:

hi i love to play sudoku. does anyone have a link for a site or program that generate new puzzles.

lkSudoku · Posted: Mon Dec 14, 2009 4:20 pm Post subject:

sudoking · Posted: Mon Dec 14, 2009 11:51 pm Post subject:

Oezden Aynali · Posted: Sun Mar 07, 2010 4:22 pm Post subject: Re: Hardest Sudoku Ever

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

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

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

Thank you.
Shocked

Oezden Aynali