SudokuSolver Forum

A forum for Sudoku enthusiasts to share puzzles, techniques and software
It is currently Thu Mar 28, 2024 12:09 pm

All times are UTC




Post new topic Reply to topic  [ 16 posts ]  Go to page Previous  1, 2
Author Message
PostPosted: Tue May 13, 2014 8:50 pm 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
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!


Top
 Profile  
Reply with quote  
PostPosted: Wed May 14, 2014 10:10 am 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
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.


Top
 Profile  
Reply with quote  
PostPosted: Thu May 15, 2014 9:18 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Tue Aug 05, 2008 11:43 am
Posts: 251
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


Top
 Profile  
Reply with quote  
PostPosted: Fri May 16, 2014 12:37 pm 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
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.


Top
 Profile  
Reply with quote  
PostPosted: Mon May 19, 2014 10:13 am 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
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


Top
 Profile  
Reply with quote  
PostPosted: Wed Nov 05, 2014 10:09 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Thu Apr 24, 2008 4:27 pm
Posts: 791
tarek, are you still around? Can you give Richard any pointers on generating multi-grid sudoku?


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 16 posts ]  Go to page Previous  1, 2

All times are UTC


Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group