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.