| View previous topic :: View next topic |
| Author |
Message |
| adc85
| | Joined: 29 Dec 2005 | | Posts: 25 | | : | |
Items |
|
 Posted: Thu Dec 29, 2005 10:41 am Post subject: Determining Difficulty While Creating Puzzle? |
 |
|
| This is the only part I am struggling with here. I have no idea how to go about determining the difficulty while the puzzle is being generated. Why go through all of the trouble of generating the puzzle only to find out that it isn't a hard level puzzle and therefore have to generate a new one (as the user selected a hard level puzzle to do)? How do you guys deal with that? Any methods people have tried in the past? I have to admit though, this has been quite a fascinating puzzle game to learn more about so far and love the challenge. So any thoughts? |
|
| Back to top |
|
 |
| eclark
| | Joined: 28 Dec 2005 | | Posts: 70 | | : | |
Items |
|
| Posted: Thu Dec 29, 2005 10:52 am Post subject: |
|
|
| right now I am using the java dancing links generator posted just a little while ago. It guesses at the difficulty based upon the number of backtracks it has to take to find the completed puzzle. Then I solve the puzzle using more human methods and give it a rating that way. One of my many goals is to get an average of the two as my representation of difficulty. |
|
| Back to top |
|
|
| Ruud
Site Admin
 | | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
| Posted: Thu Dec 29, 2005 1:29 pm Post subject: |
|
|
| acd85 wrote: | | Why go through all of the trouble of generating the puzzle only to find out that it isn't a hard level puzzle and therefore have to generate a new one. |
Hi,
Welcome to this wonderful forum.
This problem is the one that we all face. Here are the alternative solutions that different programmers have used:
1. Optimize code to let it generate puzzles so fast, it doesn't matter that you'll have to skip a few before you have the correct one.
2. Let it build a "cache" of difficult puzzles in the background, while you are puzzling. The next difficult one comes from the cache, and the cache is replenished when you are solving it.
3. Get rid of the difficulty setting. Take it or leave it.
4. Get the difficult sudokus from another source. Check the following websites for a nice free selection:
http://vanhegan.net/sudoku/
http://www.menneske.no/sudoku/eng/
http://websudoku.com/
http://www.sudocue.net/daily.htm
Ruud.
_________________
Meet me at sudocue.net |
|
| Back to top |
|
|
| adc85
| | Joined: 29 Dec 2005 | | Posts: 25 | | : | |
Items |
|
| Posted: Fri Dec 30, 2005 2:34 am Post subject: |
|
|
Thanks for the tips. I thought about doing something like this:
1. Place 1 random digit (can be any number from 1 – 9) on each 3 x 3 region of the board. (Already coded and tested this part.)
2. Implement the dancing links algorithm based on what is given so far. (Currently in progress.)
3. The execution of this algorithm should eventually yield a unique, possible solution in most cases. If not, then the script will regenerate the entire puzzle quickly and then solve it again using the same algorithm. This process will keep occurring until a unique, possible solution exists for the generated puzzle.
4. During phase 3, the program will determine the difficulty based mostly on how efficient the dancing links algorithm performs for the generated puzzle.
5. Oh yeah, and of course more than 9 “givens” will be provided when this program finishes. It just needs to generate a few at the beginning so that it has something to work with and then later on it can add on more “givens”.
What do you guys think? |
|
| Back to top |
|
|
| adc85
| | Joined: 29 Dec 2005 | | Posts: 25 | | : | |
Items |
|
| Posted: Fri Dec 30, 2005 10:07 am Post subject: |
|
|
| Another question. How many "givens" should there be before a puzzle is not impossible anymore? Is there a usual limit? And can the Dancing Links Algorithm solve a puzzle where only 9 givens are provided? Wish me luck in trying to store the data right in that humongous dancing links grid that is tough to test! |
|
| Back to top |
|
|
| Ruud
Site Admin
| | Joined: 17 Sep 2005 | | Posts: 708 | | : | | Location: Netherlands |
Items |
|
| Posted: Fri Dec 30, 2005 12:28 pm Post subject: |
|
|
adc85,
In reply to both your posts:
| Quote: | | Place 1 random digit (can be any number from 1 – 9) on each 3 x 3 region of the board. |
There are a lot of interesting puzzles with an empty 3x3 region. Use the entire board, and use a mechanism to avoid clusters. Symmetry can be used for that.
The minimum number of givens is 17, and not likely to go any lower, but you could try 16, just to see if you're lucky.
With anything below 17, you're only using the Dancing Links algorithm to filter out the invalid grids, the ones with NO solution, but you're not interested in how many solutions there are.
Regenerate a puzzle entirely is not really necessary. You can remove the given that caused the puzzle to become invalid and place another one. That usually works faster than restarting.
| Quote: | | During phase 3, the program will determine the difficulty based mostly on how efficient the dancing links algorithm performs for the generated puzzle. |
There is no direct relationship between the difficulty of a sudoku and the time required to solve it with DLX. The top95 (used as a reference by many programmers) has the 95 sudokus that were the most difficult for DLX, but in terms of human solving, there are quite a few in it that require singles only.
Ruud.
_________________
Meet me at sudocue.net |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
