choosing givens

mea · Posted: Sat Aug 05, 2006 5:43 pm Post subject: choosing givens

Hi there,

this is my first post here, cause so far I've been doing fine. My solver is able to solve all human solvable puzzles I could find, so I want it to create puzzles on its own now.

The problem is choosing the givens. Is there any logic about the patern in which they need to be placed? Like I found an official sudoku has between 17 and 32 givens. I can't find any statistical information about how many numbers there need to be in a row, how many in a box, how many in a column, or how many of a certain number.

Currently it places in between 17 and 32 random numbers of a full sudoku grid, but this doesn't seem to give a solvable solution, so I guess I need a bit more logic and a bit less randomness. Anyone got some givens logic for me? Very Happy

Thanks in advance!

Mike Barker · Posted: Sun Sep 03, 2006 11:18 pm Post subject:

Interestingly I can give you the same advice I gave devil. In addition to a solver there is also a generator, suexg, at http://magictour.free.fr/sudoku.htm. I don't know of any statistics on puzzles, but you can use this to generate as many puzzles as you want and generate your own statistics or just use it directly (my recomendation). There are also collections of puzzles there.

Ruud · Site Admin

Hi mea,

In my opinion, the best approach to generate a valid sudoku is:

1. Use a fast algorithm to generate a random solution grid;
2. Clear a random cell and use a fast solver to validate the puzzle;
3. If the solver fails, restore the cell, prevent it from being chosen again and try another cell;
4. Stop when:
- a) You're satisfied;
- b) You cannot clear any cells (the puzzle is now locally minimal);

Some notes:

Start validating only after 4 cells have been cleared. This saves a little time. You can suspend the solver even longer if you count how many cleared cells can "see" each other. As long as this count is below 4, the puzzle will always be valid.

Clear cells in pairs, quads or 8-tuples when you want to generate symmetrical puzzles.

Ruud
_________________
Meet me at sudocue.net

Jean-Christophe · Posted: Mon Sep 04, 2006 7:37 am Post subject:

Another approach might be to :
Generate a valid filled grid.
Search for unavoidable sets. See : http://www.setbb.com/sudoku/viewtopic.php?t=490&highlight=clique&mforum=sudoku
Since this is very costly, I would search only for the simplest unavoidable sets. Those with 4 & 6 cells.
You know that for each of these unavoidable sets, you need at least one given clue to break the multiple solution cycle it forms.

Based on the same idea, I was also thinking of using Uniqueness techniques while generating puzzles, during the generation process. This might minimize the unavoidable sets in the resulting grid. But Uniqueness techniques should be applied only if it does not lead to a conflict. After all, every puzzle must have unavoidable sets.

Also note that you need at least 8 different numbers in the givens, otherwise it will have multiple solutions.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.