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   

Sudoku generator success =D

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

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Thu Dec 15, 2005 8:45 pm    Post subject: Sudoku generator success =D Reply with quote

Well after seeing the techniques here and learning what I can; I finally have a super fast sudoku generator.

I did a speed test of 100 puzzles and it came out to 1 puzzle every 42 milliseconds. I'm very happy with that. (this doesn't include uniqueness test and visible clues processing because I'm just not at that level yet)

Now I have a couple of questions.

1. How do I know if a sudoku has only 1 solution?

2. Does the selection of visible clues determine if it only hase one solution? (and if that's true...then every sudoku potentially has only 1 solution...but it's determined by what spaces you uncover?)
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Dec 15, 2005 9:34 pm    Post subject: Reply with quote

Hi,

When you based your generator on Dukosu's code, every sudoku you generate should have a unique solution, because the exact-cover principle is used to generate it.

To test your generator, use a known solver and test a representative set of your output.

The number of clues is not relevant to the uniqueness of the solution, unless you have less than 17 clues. The placement is more important. The only way to find out is to do some testing.

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

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Thu Dec 15, 2005 10:56 pm    Post subject: Reply with quote

Ruud,
My code isn't based off dusuko's that's why i don't know if they are unique or not. So far I've produced over 5000 sudoku's averaging 23 millisecs each with no repeats.

It's still going atm...it's up to 10000...23ms average time to make and still no repeats. I have it set to make 500,000 then stop. Basically I don't know how valid the sudokus are and I just have to find a way to analyze them.

KW
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Dec 15, 2005 11:07 pm    Post subject: Reply with quote

KW wrote:
My code isn't based off dusuko's that's why i don't know if they are unique or not

I'd suggest you first generate only a few puzzles and check if the algorithm is OK, before going into bulk mode and generate half a million.

Secondly, your generator should check itself that the puzzle is unique. The common way to do this is build a solver into your generator program, and use it to verify the puzzle. A backtracking solver with a dancing links algorithm would be OK, but any thorough solver would be OK. Check some of the older topics on this forum about backtracking.

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

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Thu Dec 15, 2005 11:15 pm    Post subject: Reply with quote

Up to 25,000...still 23ms but I had 1 repeat....is that acceptable?

I'm still learning here and I'm not sure what constitutes a unique puzzle (other than only one solution). Can a puzzle be determined unique before any numbers are removed from it?

Plus, my solver uses strings and is logic only. And only uses the first couple of solving methods. It can solve easy and medium difficulty but has problems with hard ones.
Back to top
View user's profile Send private message
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Thu Dec 15, 2005 11:22 pm    Post subject: Reply with quote

Stopped it at 200,000. Had a total of 11 repeat sudokus. Final average create time was 24ms. On to figuring out how to do a uniqueness test.
Back to top
View user's profile Send private message
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Fri Dec 16, 2005 6:36 am    Post subject: Reply with quote

Here's 5 sudokus from the generator. Can you check em out and see if I'm on the right track?

At the moment they're just being stored in a grid[10,10] array.

Code:

Sudoku #1
7.9.2.4.6.8.3.5.1
1.3.6.7.5.2.9.8.4
4.5.8.9.1.3.6.7.2
2.4.1.6.8.9.7.3.5
8.7.3.5.4.1.2.6.9
5.6.9.2.3.7.1.4.8
6.2.4.1.7.5.8.9.3
3.1.7.8.9.4.5.2.6
9.8.5.3.2.6.4.1.7
created in: 4ms


Sudoku #2
2.1.6.5.7.4.9.8.3
9.7.8.1.2.3.6.5.4
3.4.5.9.6.8.7.1.2
5.6.2.8.1.9.4.3.7
1.9.4.6.3.7.8.2.5
7.8.3.2.4.5.1.9.6
8.2.9.4.5.6.3.7.1
4.3.1.7.8.2.5.6.9
6.5.7.3.9.1.2.4.8
created in: 52ms


Sudoku #3
7.6.1.3.8.4.5.9.2
4.2.3.9.5.1.6.8.7
5.9.8.7.2.6.1.3.4
1.5.4.8.6.3.7.2.9
2.3.7.4.9.5.8.6.1
9.8.6.2.1.7.3.4.5
3.7.2.1.4.8.9.5.6
8.4.5.6.7.9.2.1.3
6.1.9.5.3.2.4.7.8
created in: 32ms


Sudoku #4
9.3.5.2.7.1.8.4.6
1.6.4.5.3.8.7.2.9
7.8.2.4.6.9.5.3.1
3.5.1.9.2.6.4.7.8
4.9.6.8.5.7.2.1.3
8.2.7.1.4.3.6.9.5
2.7.8.3.1.5.9.6.4
5.4.3.6.9.2.1.8.7
6.1.9.7.8.4.3.5.2
created in: 4ms


Sudoku #5
2.6.9.4.1.5.3.7.8
7.4.3.6.2.8.9.5.1
5.8.1.7.3.9.6.4.2
1.7.2.8.4.6.5.3.9
3.5.6.1.9.7.2.8.4
4.9.8.2.5.3.7.1.6
6.3.5.9.8.1.4.2.7
8.2.7.5.6.4.1.9.3
9.1.4.3.7.2.8.6.5
created in: 29ms
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Dec 16, 2005 8:31 am    Post subject: Reply with quote

The grids are OK.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
lchs

Joined: 13 Oct 2006
Posts: 1
:

Items
PostPosted: Fri Oct 13, 2006 4:55 pm    Post subject: Reply with quote

can you show us your algorithm or the code?
thank you very much
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