Stage 2 - Choosing the Givens

cobnut · Posted: Fri May 30, 2008 3:10 pm Post subject: Stage 2 - Choosing the Givens

Hi everyone, newbie here, in most senses of the word.

I think I've completed stage one of my sudoku generator in that I've got it to produce valid grids in a reasonable time (the best yet less than 0.02s). However, I'll admit that I'm basing this only on proof by inspection - is there a better way?

Stage 2 is, I guess, identifying the givens. I want my puzzles to have a unique solution so am I right in saying that, if showing 25 or so givens, I need to have at least 8 unique numbers showing. Are there any other requirements to ensure a unique solution?

Obviously the other problem with givens is placement. I imagine for easier puzzles I'll want to ensure some 'grouping' of givens in a row or column to give a start. Are there any references on this?

Sorry if I've asked too many FAQs but there's so much info here!

Jon

m_b_metcalf · Posted: Fri May 30, 2008 8:50 pm Post subject: Re: Stage 2 - Choosing the Givens

cobnut · Posted: Mon Jun 02, 2008 10:18 am Post subject:

Hi Mike, yes, thanks, it's useful to have some feedback.

We actually formed most of the rules for the givens in the pub on Friday night, though the one about entirely empty rows/columns was missed!

We also came to the conclusion that it might be easier to create a valid puzzle from a set of givens, rather than choose the givens from a valid puzzle, as you suggest and, fortunately, my generator would permit this method so we're going to give that a go.

I have to admit that this is largely an exercise for us rather than a need to create a puzzle generator and, as such, we're trying to do it all from scratch rather than using the work of others. Having said that, when we started we had no idea of the complexity of the subject!

We hope to have a working puzzle in the next day or so, expect some more questions!

Jon[/i]

Pete · Posted: Mon Jun 09, 2008 10:36 pm Post subject:

The restrictions mentioned here seem to be valid, though I'm not sure that they're really necessary.

My program is based in Knuth's DLX algorithm. (Other solvers can certainly be used, though they would take more time.) The best way to guarantee a unique solution may be to run a solver.

Here's how my generator works:

Step 1: I seed an empty grid with some random digits, then ask the DLX algorithm to solve it. The first solution generated is my solution grid.

Step 2: I randomly select a pair of digits, remove them from the grid, then run the solver again. If the solution is still unique, I start this step again to remove another pair. Otherwise, the removed digits are put back. (Digits are removed in pairs to maintain symmetry.) This continues until no more pairs can be removed.

This approach is reasonably fast and does not need to consider these restrictions at all. I'm still working on it and should have some Java source code to show you in a couple of weeks.

I wish you success with your program.

Pete

wapati

Pete · Posted: Thu Jun 12, 2008 6:33 pm Post subject:

I've been thinking about this one some more.

It sounds like you're trying to create a generator without a solver. Is that the case? Even with some number of restrictions, can we prove that a sudoku is valid (i.e., that it has exactly one solution) without actually solving it?

It's an interesting idea, though I'm not convinced that it's at all possible.

Pete

cobnut · Posted: Mon Jun 16, 2008 5:33 pm Post subject:

Hi Pete,

That was originally the idea - when we had no idea what we were doing Laughing

I've now got what I think is a pretty good solver up and running on the site and doing that has made it obvious that the solver gives us tools and data to not only create 'solvable' puzzles but might also give a good indication of difficulty.

I hope to have a trial puzzle creator up soon and will bump the thread as and when.

Cheers for staying interested.

Jon