Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Hardest Sudoku Ever

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
kammi

Joined: 27 Nov 2006
Posts: 7
:
Location: www.sudokupower.com

Items
PostPosted: Mon Nov 27, 2006 7:23 pm    Post subject: Hardest Sudoku Ever Reply with quote

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
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Mon Nov 27, 2006 7:49 pm    Post subject: Reply with quote

Nice puzzle Arnold, but far from being the hardest. There's a long thread here about finding and ranking the hardest puzzles.
Back to top
View user's profile Send private message
dmkAlex

Joined: 02 Jun 2007
Posts: 11
:
Location: USA

Items
PostPosted: Sat Jun 02, 2007 2:04 am    Post subject: Reply with quote

My solver solved it in 22 trials.
Back to top
View user's profile Send private message
atkman

Joined: 04 Jan 2008
Posts: 4
:

Items
PostPosted: Fri Jan 04, 2008 6:30 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
brasshopper

Joined: 02 Jun 2009
Posts: 2
:
Location: Clewiston, FL

Items
PostPosted: Tue Jun 02, 2009 8:37 pm    Post subject: difficult puzzle Reply with quote

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.
Back to top
View user's profile Send private message
Tobitab

Joined: 14 Dec 2009
Posts: 1
:
Location: San Jose

Items
PostPosted: Mon Dec 14, 2009 1:50 am    Post subject: Reply with quote

hi i love to play sudoku. does anyone have a link for a site or program that generate new puzzles.
Back to top
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Mon Dec 14, 2009 4:20 pm    Post subject: Reply with quote

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


I have created a website for playing sudoku, it has 5 difficulty levels and a hint to show a cell value

www.lksudoku.co.cc

The website also contain a link to an offline version which generates puzzles and allows the solving of external puzzles
Back to top
View user's profile Send private message Send e-mail
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Mon Dec 14, 2009 11:51 pm    Post subject: Reply with quote

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


I have created a website for playing sudoku, it has 5 difficulty levels and a hint to show a cell value

www.lksudoku.co.cc

The website also contain a link to an offline version which generates puzzles and allows the solving of external puzzles


It really needs the ability to enter in pencil marks. As it is, each cell can only contain 1 value. There's little point in having extreme puzzles without this ability.

Also, I'd do away with the status, which tells the user when they've made an illegal move. That's part of the fun.

Finally, a timer would be nice. Smile
Back to top
View user's profile Send private message
Oezden Aynali

Joined: 07 Mar 2010
Posts: 1
:

Items
PostPosted: Sun Mar 07, 2010 4:22 pm    Post subject: Re: Hardest Sudoku Ever Reply with quote

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
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron