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 Possible Sudoku

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

Joined: 15 Feb 2006
Posts: 3
:

Items
PostPosted: Wed Feb 15, 2006 2:58 pm    Post subject: Hardest Possible Sudoku Reply with quote

Hello --

I'm not a sudoku programmer or anything, but I have a question that maybe someone here wouldn't mind answering.

Wouldn't it be fairly easy for a computer to create "the hardest possible sudoku"? That is, a puzzle that gives you the absolute minimum number of clues and yet has only one possible solution?

When working a sudoku, I always feel like I'm pitting my brain against a computer (a losing proposition). Whereas with a crossword puzzle (or better yet, a double-crostic), I feel like I'm matching wits with the person who created the puzzle.

So my feeling is: "Show me the hardest possible sudoku, and I'll wrack my brain until it's solved, and then I'll never have to work another one!" Is "the hardest possible sudoku" as defined above a possibility, or is there something I'm missing?

Thanks --

Galen
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Wed Feb 15, 2006 3:45 pm    Post subject: Reply with quote

Hi there Galen

The number of clues doesn't relate to difficulty, many 17 clue puzzles are very easy while some 30+ clue-puzzles can be very hard.

Tarek
Back to top
View user's profile Send private message
galenfott

Joined: 15 Feb 2006
Posts: 3
:

Items
PostPosted: Wed Feb 15, 2006 4:06 pm    Post subject: Reply with quote

Well, it seems to me that the number of clues obviously has some bearing on difficulty. A puzzle with 80 clues would be ridiculously easy to solve, whereas a puzzle with only 1 clue wouldn't be much of a sudoku at all, as it would have hundreds and hundreds of possible solutions.

So I'd think there has to be a finite answer to this question: What is the minimum number of clues a sudoku must contain for the puzzle to have only one possible solution? Is the answer "17"? I understand that you're saying that this puzzle wouldn't necessarily be the "most difficult," but it seems to me it would be some sort of "ultimate" sudoku.

--Galen
Back to top
View user's profile Send private message
galenfott

Joined: 15 Feb 2006
Posts: 3
:

Items
PostPosted: Wed Feb 15, 2006 4:32 pm    Post subject: Reply with quote

Ah, I think I found my own answer:

http://www.csse.uwa.edu.au/~gordon/sudokumin.php
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Feb 15, 2006 6:46 pm    Post subject: Reply with quote

Hi,

you will find many difficult sudokus on Gordon's site, but not the most difficult. If you want to be cured of your sudoku addition, try this 18-clue example from the top1465.

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


Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
Cristian2006

Joined: 25 Feb 2006
Posts: 6
:

Items
PostPosted: Sat Feb 25, 2006 7:15 pm    Post subject: About the "clues" Reply with quote

I think it's wrong to call visible numbers "clues" because..
The amount of already solved numbers don't equal to the difficulty
and
true "clues" are found during the solving (you know, when you find for example hidden candidate, I call that a "clue".. so I call those little turn points to the solution "clues")

That's why I just call for example a puzzle where 21 numbers are solved "21-number puzzle" or "Puzzle with 21 numbers".

Later I am going to release on my site some of the HARDEST EVER made sudokus and they are not 17-number puzzles.

It was said somewhere, this would be the hardest sudoku ever made:
7.8...3.....2.1...5.........9.6....4....7.5............4.....263...8.......1...9.
and yes, it is really hard but I can make at least that hard or even harder with many more numbers. (Edit: I wanted to add that that's not even actual sudoku because it's not symmetric!)

And we have to consider also that the current difficulty level of the puzzle often depends on what is your path to the solution. With your "moves" you can make it easier or (believe it or not, the following is sometimes but more rarely true) even HARDER (which proves the amount of visible numbers doesn't equal to difficulty) by "hiding" yourself better paths to the solution.
_________________
My new website (doesn't include sudokus, at least yet):
http://www.cristianium.fi
(it's in finnish)
Back to top
View user's profile Send private message MSN Messenger
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sun Feb 26, 2006 2:30 pm    Post subject: Reply with quote

Hi Cristian2006,

There are many different view on sudoku terminology. Use what you like and most people here will understand what you mean.

Quote:
It was said somewhere, this would be the hardest sudoku ever made:
7.8...3.....2.1...5.........9.6....4....7.5............4.....263...8.......1...9.

That is the same sudoku I posted right before you. Only rows 4-6 have been swapped with rows 7-9.

Quote:
and yes, it is really hard but I can make at least that hard or even harder with many more numbers. (Edit: I wanted to add that that's not even actual sudoku because it's not symmetric!)

Symmetry is nice, but not a requirement for sudokus.
If you can make harder sudokus, then please post a few of them here on the forum. We really like extremely hard sudokus here. Smile

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
Henk

Joined: 13 Nov 2005
Posts: 105
:

Items
PostPosted: Sun Feb 26, 2006 9:34 pm    Post subject: Reply with quote

Quote:
We really like extremely hard sudokus here.


But not too hard or I get sleepless nights...Razz
_________________
Generate and solve Sudoku puzzles with Into Sudoku!
Back to top
View user's profile Send private message
Cristian2006

Joined: 25 Feb 2006
Posts: 6
:

Items
PostPosted: Mon Feb 27, 2006 6:13 am    Post subject: Reply with quote

Ruud wrote:
Hi Cristian2006,

There are many different view on sudoku terminology. Use what you like and most people here will understand what you mean.

Quote:
It was said somewhere, this would be the hardest sudoku ever made:
7.8...3.....2.1...5.........9.6....4....7.5............4.....263...8.......1...9.

That is the same sudoku I posted right before you. Only rows 4-6 have been swapped with rows 7-9.

Quote:
and yes, it is really hard but I can make at least that hard or even harder with many more numbers. (Edit: I wanted to add that that's not even actual sudoku because it's not symmetric!)

Symmetry is nice, but not a requirement for sudokus.
If you can make harder sudokus, then please post a few of them here on the forum. We really like extremely hard sudokus here. Smile

Ruud.


Ok. Yes, I understand. Thanks for your answer. I didn't notice that the sudoku you posted was almost the same. I copied that but didn't take a look. I think that swapping could make your sudoku even a slight harder, but it's not that clear. It could be that your sudoku is also easier if you use advanced technics but it looks like you don't "need" them during every path to the solution what might make it easier. However, it's pretty hard in every way.

The difficulty level is complex because if you restrict or order people to use something to make solution it changes (of course it's not been like that with sudokus). It changes more with very complex puzzles. Sometimes I think it would be cool if sudoku designers started to inform about "requirements", don't you think? I think it could be possible. To inform what technics are required to solve it... Smile There are so many "stars" in the magazines and even if it's said "hard" or "easy" it's not necessarily Pappocom's or Nikoli's table either. it changes a lot how it's in reality and you're sometimes confused or disappointed. I think I am going to try to have that info with my sudokus in the future. Because categories "hard or "easy" don't say in any cases what you really need.

And what you said about symmetrics, IMO it IS required for a sudoku. Otherwise it's not a sudoku but just a puzzle called "Number Place". But it's partly my opinion. I just think if you have for example 8 puzzles on 2 pages side by side, it's much more enticing if your puzzles look beautiful like sudokus than like a mess. Smile And, there are almost 5,5 billion symmetric puzzles. So, that's enough. Of course they are not all solvable (if I have understood right) but it means if someone started to release 10 000 "new" symmetric puzzles everyday, it would take around 1500 years to release them all... And no one would even remember if it's already been or not... Laughing
_________________
My new website (doesn't include sudokus, at least yet):
http://www.cristianium.fi
(it's in finnish)
Back to top
View user's profile Send private message MSN Messenger
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