Creation with Parameters

mugnyte · Posted: Wed Dec 07, 2005 7:17 pm Post subject: Creation with Parameters

(1) Like many generators here, mine starts with a seed: put a random sequence on the board, 1 number in each region. Also, one can hide a pattern on the board (silly, i know, but fun for enthusiasts given an overall puzzle clue, like a crossword - this is interesting when using letters instead of numbers)

(2) Then, using only the "basic rules" (employing Bob Hanson's term Cross-Hatch Scanning), it solves the puzzle, backing up when it's painted itself into a corner. It doesn't use extended logic since it's not really solving the puzzle, just placing numbers that are valid according to just the basic rules alone.

(3) When a solution is reached, proceeds to remove numbers. It uses two methods: do not remove numbers in a certain template to help build an interesting pattern of starts (instead of simply leaving random starts).

Also, each time it removes a number, it counts the number of solutions (stopping at 2) - by solving the puzzle tree using all coded logic modules and backups, much like step 2, but going on until two solutions are reached or the move tree is exhausted. If there are 2 solutions, put that number back and remember not to use it until a different number is removed first (a memory of just one seems fine).

Keep removing numbers until we reach the prescribed number of starts (more are left for minor puzzles) and a theorectical minimum of 17 or no number on the board can be removed without increasing the number of solutions.

(4) When rating a puzzle it solves this puzzle one last time using all logic modules, assigning a weight to each logic method (again, using the techniques employed by Bob on http://www.stolaf.edu/people/hansonr/sudoku/explain.htm)
Each time the best move (a single is revealed), the solver's progression through the modules for that cell (or one that changed it's marks) creates a value that is summed for the entire puzzle.
Then, this total associated with a rating at solution.

I should add that when examining a move tree, one can also supply that the puzzle must demand backups or the puzzle dropped and the process started anew. This means for each logic module combination employed, you are creating puzzles which they alone cannot solve - the solver has a choice of two entries for a cell as a best move. My hope is to write all the modules I can and yet still demand more moves than simply [81-starts] moves, which should expose either a flaw in my logic (haha, likely) or a puzzle which demands another logic module.

Using the above method, puzzles are generated relatively reliably within a narrow band of difficulty and interest. For the end-user, easiest puzzles are instant, while the hardest puzzles may take a few seconds to generate. This is pre code-optimization, but the design seem sound so far.

To create the hardest puzzles, it's been run for hours without yet finding a strong candidate. Example: Using all logic modules, find a puzzle that has an overall move tree of >X moves where X = 500. This reflects that the modules discussed here that I've written so far can solve most puzzles, or that when they cannot, the backup paths are relatively shallow.

This brings up the oft-discussed relation to an overall move tree depth and the difficulty of a puzzle. I was intrigued to learn that with one-higher logic module, some of the largest basic-rule move trees (>81k moves) were eliminated all together. The program is now finding puzzles requiring GridAnalysis and Medusa techniques (again these terms are from the Sudoku Assistant site) - which have not yet been coded.

still under development, but it's here at...
http://sudoku-koubou.com

Comments welcome. Um, except about the crappy site Wink

mug
_________________
thanks