SudokuSolver Forum
http://www.rcbroughton.co.uk/sudoku/forum/

Puzzle Generation in SudokuSolver
http://www.rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=11&t=1267
Page 2 of 2

Author:  Ed [ Tue May 13, 2014 8:50 pm ]
Post subject:  Re: Puzzle Generation in SudokuSolver

rcbroughton wrote:
I set a batch running to generate 102 puzzles and got the following stats after it completed in just over 35 minutes.
Code:
Avg Time   22s
This includes scoring which means it's very fast.
rcbroughton wrote:
Code:
1.15   2
1.2   4
1.25   2
1.3   1
1.35   2
1.4   2
1.5   1
This is the range I would select in order to pick one. To get that many in 35 minutes is excellent.

rcbroughton wrote:
A lot of work done . . . but a bit more to go
Not much more from what you've explained. This is looking fantastic!

Author:  rcbroughton [ Wed May 14, 2014 10:10 am ]
Post subject:  Re: Puzzle Generation in SudokuSolver

tarek wrote:
I used to (like many others) to generate the cage 1st which can be symmetric or asymmetric, then I superimpose on it a solution grid that was then reshuffled keeping the cage pattern until it gave a killer puzzle.
This seems to be the tricky part. What I'm observing at the moment is that the program can come up with a cage pattern that proves very difficult to shuffle candidates to produce a unique puzzle. Other times it comes up with a cage pattern that yields very quickly.

For example, I made a tweak yesterday to abandon a grid pattern if it did not yield a unique puzzle after 2 tries - this reduced the average generation time down to about 3 seconds (22 seconds was based on abandoning a cge pattern after 40 unsuccessful attempts to find a unique solution).

I'm also looking at trying to get a balance of "larger" cages - again the puzzles with larger cages seem more reluctant to yield unique solutions.

I've experimented with allowing diagonally connected (semi-disjoint) cages. I've got a couple of beautiful cage patterns and puzzles but am thinking I need to limit the number of these in any given puzzle pattern. e.g.
3x3::k:2304:2304:5633:5633:5633:9474:9475:9474:9474:5380:5380:5633:1285:4102:4102:9474:9475:9474:6407:2056:5380:1285:4102:9475:9475:9474:9475:2569:6407:2056:4102:9475:2314:9475:4107:9474:2569:6407:6407:4364:2314:9475:4107:4107:5389:2574:2569:9231:3600:4364:4107:2321:2321:5389:2574:9231:3600:9231:4114:4371:2836:5389:5389:9231:9231:9231:5141:4114:4114:4371:2836:2582:9231:9231:2327:2327:5141:5141:4114:2836:2582:

I'm pretty sure my cage generation algorithm could do with some improvement. It would be interesting to hear your approach . . . I've implemented the following mechanism

1. Work through the grid to find cell with most symmetry constraints (or if no symmetry, simply start in centre and spiral outwards) looking for an uncaged cell.
2. Start a new cage at that cell - randomly choose a "preferred" size from a weighted list of 2, 3, 4, 5, 6, 7 cells (i.e. more chance of picking 4 or 5 cells than 2 or 7 cells)
3. Randomly add an unused connected cell to the cage (and all required symmetry cells)
4. Repeat until the cage size is equal or greater to "preferred" size or no more unused connected cells are available
5. If the puzzle is symmetric, replicate the cage to it's symmetric locations
6. Repeat from 1 until there are no more unused cells
7. If there are any single cell cages, throw away and start again!

I'm not happy with step 7 - it was a quick fix. What I really want to do is modify the cage "growth" step 3 to avoid creating a single isolated cell but I haven't got my head around that yet. Since the approach works quite quickly anyway, I'm not sure if I need to be more sophisticated in the cage creation.

Author:  tarek [ Thu May 15, 2014 9:18 pm ]
Post subject:  Re: Puzzle Generation in SudokuSolver

I haven't invested enough time in Killer puzzle generation to claim to be an expert. JC was probably the best because he mentioned IIRC his efforts to tackle this very issue (cage template generation).

Weak spots are always the edges & corners. IMO these should be included 1st to get them out of the way. Better than searching for an (Uncaged cell) is to exclude any caged cell from the pool of cells to look into. This way you will guarantee hitting a free cell each time.

tarek

Author:  rcbroughton [ Fri May 16, 2014 12:37 pm ]
Post subject:  Re: Puzzle Generation in SudokuSolver

tarek wrote:
I haven't invested enough time in Killer puzzle generation to claim to be an expert. JC was probably the best because he mentioned IIRC his efforts to tackle this very issue (cage template generation).
Anyone who has even looked at it is going to be more of an expert than me!

Quote:
Weak spots are always the edges & corners. IMO these should be included 1st to get them out of the way.
Interesting - I think that's OK for non-symmetric puzzles, but if I have symmetry, I found I was ending up with cages that broke the symmetry rules if I didn't use up cells on the lines of symmetry first. I've now implemented a relatively quick checking algorithm to ensure that adding a cage doesn't leave an orphaned single cell.
Quote:
Better than searching for an (Uncaged cell) is to exclude any caged cell from the pool of cells to look into. This way you will guarantee hitting a free cell each time.
I'm effectively doing that, keeping a track of unused cells to choose from (but subject to picking symmetry cells first from this unused pool).

In any event, the cage template creation is very quick. What I'm now trying to do is see if there are any template-specific characteristics that I can identify that are indicators of likelihood of hitting a unique solution. This is based on the empirical observation that I am tending to get cage patterns that yield a unique solution quickly - or not at all.

Author:  Ed [ Mon May 19, 2014 10:13 am ]
Post subject:  Re: Puzzle Generation in SudokuSolver

rcbroughton wrote:
I've experimented with allowing diagonally connected (semi-disjoint) cages. I've got a couple of beautiful cage patterns and puzzles but am thinking I need to limit the number of these in any given puzzle pattern.
That puzzle you posted is incredible, especially n3! I agree that overally, there are too many of those diagonally connected cages in the whole pattern. Very intimidating. So, a limit on how many of those would be a very practical step.

Cheers
Ed

Author:  enxio27 [ Wed Nov 05, 2014 10:09 pm ]
Post subject:  Re: Puzzle Generation in SudokuSolver

tarek, are you still around? Can you give Richard any pointers on generating multi-grid sudoku?

Page 2 of 2 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/