| View previous topic :: View next topic |
| Author |
Message |
| King Wonka
| | Joined: 14 Dec 2005 | | Posts: 26 | | : | |
Items |
|
 Posted: Thu Dec 15, 2005 8:45 pm Post subject: Sudoku generator success =D |
 |
|
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 |
|
 |
| Ruud
Site Admin
 | | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
| Posted: Thu Dec 15, 2005 9:34 pm Post subject: |
|
|
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 |
|
|
| King Wonka
| | Joined: 14 Dec 2005 | | Posts: 26 | | : | |
Items |
|
| Posted: Thu Dec 15, 2005 10:56 pm Post subject: |
|
|
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 |
|
|
| Ruud
Site Admin
| | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
| Posted: Thu Dec 15, 2005 11:07 pm Post subject: |
|
|
| 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 |
|
|
| King Wonka
| | Joined: 14 Dec 2005 | | Posts: 26 | | : | |
Items |
|
| Posted: Thu Dec 15, 2005 11:15 pm Post subject: |
|
|
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 |
|
|
| King Wonka
| | Joined: 14 Dec 2005 | | Posts: 26 | | : | |
Items |
|
| Posted: Thu Dec 15, 2005 11:22 pm Post subject: |
|
|
| 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 |
|
|
| King Wonka
| | Joined: 14 Dec 2005 | | Posts: 26 | | : | |
Items |
|
| Posted: Fri Dec 16, 2005 6:36 am Post subject: |
|
|
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 |
|
|
| Ruud
Site Admin
| | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
| Posted: Fri Dec 16, 2005 8:31 am Post subject: |
|
|
The grids are OK.
_________________
Meet me at sudocue.net |
|
| Back to top |
|
|
| lchs
| | Joined: 13 Oct 2006 | | Posts: 1 | | : | |
Items |
|
| Posted: Fri Oct 13, 2006 4:55 pm Post subject: |
|
|
can you show us your algorithm or the code?
thank you very much |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
