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   

the slowest simple sudoku

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
weia

Joined: 12 Nov 2005
Posts: 5
:

Items
PostPosted: Mon Nov 14, 2005 9:37 pm    Post subject: the slowest simple sudoku Reply with quote

Many sudoku's in newspapers can be solved by only filling in naked singles and hidden singles, without having to look at more complex patterns. This 'simple sudoku's' (or do they already have another name?) start with a position that often leads to say 3 singles (hidden or not). I call it one round when you fill in those 3. This leads to another say 4 singles for the second round. In the third round you can add 5 singles or so. Now what I am wondering is: what is the slowest simple sudoku that takes the most rounds to find the complete solution?
In theory one could start with 17 hints and so 64 blanks, but the last 4 always go in one round, so theoretically a simple sudoku is possible that takes 60 rounds to complete, with every round existing of finding only one single (naked or hidden).
Have others looked at this? Who knows a very slow sudoku? (Which I like more than the fast ones.)

As an example: on http://www.csse.uwa.edu.au/~gordon/sudokumin.php all sudoku's with 17 hints are given. The first is done after 15 rounds, the second after only 11 rounds, the next three aren't simple. The two simple ones have only one round with only 1 single, their last round.
Back to top
View user's profile Send private message
weia

Joined: 12 Nov 2005
Posts: 5
:

Items
PostPosted: Mon Jan 30, 2006 6:02 pm    Post subject: Reply with quote

The slowest among the first 2500 of Gordon's 17-sudoku's takes 26 rounds to the solution. This one:
000000063
000100000
200000000
050000100
000400200
009006000
630090000
000200740
008000000
Nine rounds have only 1 (hidden) single.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Jan 30, 2006 8:13 pm    Post subject: Reply with quote

Hi,

I perform these tests on my own generated sudokus, so I was able to run the test on the complete sudoku17 collection (32930 entries)

There are 15198 sudokus in the collection that can be solved with FN only.


The winner, with 27 rounds:

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


The runners-up, with 26 rounds:

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

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


The losers are, with only 8 rounds:

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


and

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


In my experience, counting rounds is a very good way to assess relative difficulty for these easy Sudokus.

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

Joined: 12 Nov 2005
Posts: 5
:

Items
PostPosted: Tue Jan 31, 2006 8:34 am    Post subject: Reply with quote

Ah! You tested them all, thanks!

Weia
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Feb 18, 2006 2:49 am    Post subject: Reply with quote

Ruud wrote:

I perform these tests on my own generated sudokus, so I was able to run the test on the complete sudoku17 collection (32930 entries)


FYI: I believe Gordon's collection is around 35,396 entries now.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Feb 18, 2006 3:54 am    Post subject: Reply with quote

daj95376 wrote:
FYI: I believe Gordon's collection is around 35,396 entries now.

Actually, it's 36,628 already. The search is going faster than planned Smile.

Thanks for the tip. I've updated my local copy.

Ruud.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of 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