SudokuSolver Forum

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

All times are UTC




Post new topic Reply to topic  [ 16 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Sun May 11, 2014 2:55 pm 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
Hi all

I've been working through incorporating puzzle generator routines into SudokuSolver. I've got some routines working now to product standard 3x3 and Samurai puzzles - which I will work towards generalizing to other Gattai. A long way to go, as I need to think about catering for all the other constraints that SudokoSolver can handle. It's been a major effort just to get some basic logic going that works quickly enough, so might not be quick to resolve.

What I'm not entirely comfortable with yet is working out how complex the puzzles are . . . for example this is a Samurai from the generator:

Image

Is this puzzle too difficult? Do I need to crank back a little on how aggressively I remove givens?

Other thing I haven't turned my attention to yet is extending the generator to Killer puzzles. Any good tips on Killer design would be welcome.

Rgds
Richard


Top
 Profile  
Reply with quote  
PostPosted: Mon May 12, 2014 9:36 am 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
As usual, I'm very killer focused
rcbroughton wrote:
I haven't turned my attention to yet is extending the generator to Killer puzzles. Any good tips on Killer design would be welcome.
One of our active members here tarek made a killer generator, see viewtopic.php?p=2491#p2491 He was still working on it then but did achieve the generator and posted an Assassin or two. He might be worth contacting.

Don't know how useful this old thread is. http://www.setbb.com/phpbb/viewtopic.ph ... rum=sudoku or perhaps in that section of that forum http://www.setbb.com/phpbb/viewforum.ph ... rum=sudoku

Great that are trying this!
Ed


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

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
I try and spread my interests just a little...
rcbroughton wrote:
Is this puzzle too difficult? Do I need to crank back a little on how aggressively I remove givens?
I ran it through a neat program called SudokuSolver :) and it gives that samurai a score of 1.55. Andrew has given the SS score for all Ruud's samarai here Most of them are about 0.90 so Ruud's are much, much easier.
Here is the code:
000000069006100030900580000030809051090000300014030000050008000000900000809070600
610000000040001300000048007150803060003000050000070810000400030000002000002060908
000000000000060000600809002160090035000603000930010087500407006000050000000000000
609040500000700000050008000086030000040000100090201064700890000004600030000000058
006040508000005000000900040000050910009000080680309070000083001070006400360000000
Here is how SudokuSolver did it:
Puzzle Completed. Step Analysis:
278 Naked Singles
18 Naked Pairs
19 Naked Triples
9 Naked Quads
3 Hidden Singles
1 Hidden Pairs
19 Locked Candidates (Box/Line)
1 X-Chain Simple 3
1 X-Chain Simple 2
1 X-Chain Complex 4
8 XY-Chain Simple 3
1 XY-Chain Complex 4
1 ALS Simple 2
1 Empty Rectangle
Total solving time (seconds): 0.78
Calculated score: 1.55
Here is how JSudoku did it using my solver order:
The grid is solved!
Techniques used:
9 Last Digit
174 Naked Single
68 Hidden Single
6 Naked Pair
3 Hidden Pair
10 Intersection
1 X-Wing
1 Empty Rectangle
3 XY-Wing
5 Y-Wing
2 Uniqueness Test 4
2 Hidden Unique Rectangle
3 XY-Chain up to 5 links
Cheers
Ed


Top
 Profile  
Reply with quote  
PostPosted: Mon May 12, 2014 9:38 pm 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
Ed wrote:
I try and spread my interests just a little...

So I've got some rudimentary Killer generation working. Symmetry is up and running, but difficulty of output is quite variable. Haven't looked at any other constraint types yet.

Here are a few examples

SS Score 0.85
Code:
3x3::k:2320:5122:5122:5382:3082:3082:3082:3854:3854:2320:5122:2066:5382:3082:5398:5139:2051:2051:4364:2066:2066:5382:5398:5398:5139:5139:2051:4364:4632:4632:4632:5889:5398:4615:4615:4615:4364:4364:4632:5889:5889:5889:4631:4363:4363:4872:4872:4872:6425:5889:4631:4631:4631:4363:5636:2580:2580:6425:6425:4873:1813:1813:4363:5636:5636:2580:6425:4109:4873:1813:6149:2831:1809:1809:4109:4109:4109:4873:6149:6149:2831:F

SS Score 1.30
Code:
3x3::k:6146:6146:4358:4358:4362:3598:3598:3598:4611:5648:6146:6146:4358:4362:4362:3346:4611:4611:5648:1044:1044:2582:4362:3095:3346:4611:4103:5648:5388:2582:2582:7425:3095:3095:4103:4103:5388:5388:5388:7425:7425:7425:6411:6411:6411:1800:1800:4120:4120:7425:2585:2585:6411:3087:1800:5892:3605:4120:5901:2585:2835:2835:3087:5892:5892:3605:5901:5901:4617:4869:4869:3087:5892:2577:2577:2577:5901:4617:4617:4869:4869:

SS Score 2.40
Code:
3x3::k:7681:7681:7681:2825:2840:2840:2840:2844:2844:7681:2818:2818:2825:2825:2315:2315:3597:3597:7681:2818:4099:4099:6415:6415:6415:1297:4883:3594:3594:4099:3588:3588:6415:5397:1297:4883:3095:3594:6672:3588:3333:3333:5397:5397:4883:3095:3084:6672:6672:3333:3078:3078:5397:1817:3095:3084:6672:3862:3862:3078:5895:5895:1817:2843:2830:3346:3346:3862:3862:5895:5895:3080:2843:2830:3604:3604:3604:3354:3354:3080:3080:


Ironically, the last one generate more quickly than the other two.

Thoughts?


Top
 Profile  
Reply with quote  
PostPosted: Tue May 13, 2014 9:20 am 
Offline
Grand Master
Grand Master

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
You've made real progress!
rcbroughton wrote:
Symmetry is up and running
None of my Assassins are symmetrical. Symmetry is a bit boring to me.
rcbroughton wrote:
but difficulty of output is quite variable
That 1.30 puzzle looks like a really good one. I can spend half an hour getting JSudoku to churn out puzzles and none of them will be 1.30-1.45, my favourite range for an Assassin. Variability of SudokuSolver score output from JSudoku generated killers is standard.

I like to make my own cage pattern then get the generator to find a valid puzzle with that cage pattern. That's the way I use JSudoku now. I never use the cage patterns it can come up with. For one thing, I prefer asymmetrical and prefer some big unusual shaped cages.

Cheers
Ed


Top
 Profile  
Reply with quote  
PostPosted: Tue May 13, 2014 9:26 am 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
And I also managed to get a unique but unsolvable puzzle . . . is this normal?

Code:
3x3::k:2048:3073:4866:4866:4866:5635:5635:3076:3076:2048:3073:3589:4866:3590:5635:5635:1543:1543:6920:6920:3589:3589:3590:3590:4873:4873:4106:6920:6920:4619:4619:7692:3590:4873:4106:4106:3853:4619:4619:7692:7692:7692:4878:4878:4106:3853:3853:5135:4624:7692:4878:4878:5649:5649:3853:5135:5135:4624:4624:5138:5138:5649:5649:2835:2835:5396:5396:4624:3605:5138:3094:2327:1816:1816:5396:5396:3605:3605:3605:3094:2327:

Image

Symmetry is optional in my cage generation . . . I am creating puzzles by
1) generating a cage pattern (or you could define one) with zero cage values -
2) I then find a 9x9 solution that fits general constraints of no digits repeated in row, cols, nonets and cages
3) then sum up the cages
4) check if it is unique
5) if not unique go back to step 2
6) if I'm generating the grid pattern and still haven't found a solution after 50 tries - try a new pattern at step 1


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

Joined: Wed Apr 16, 2008 1:16 am
Posts: 1040
Location: Sydney, Australia
rcbroughton wrote:
And I also managed to get a unique but unsolvable puzzle . . . is this normal?
Yes, very normal, though in this case, my version 3.6.3 does solve it using the default scoring routines with a score of 4.15. JSudoku is still grinding away trying to find a way through so it is a brute.

rcbroughton wrote:
Symmetry is optional in my cage generation . . . I am creating puzzles by
1) generating a cage pattern (or you could define one) with zero cage values -
This sounds really good!

How long does it take on average to find a valid puzzle? Usually JSudoku takes a few milliseconds but sometimes can take minutes or even hours. If SS was too slow, I'd probably stick to JSudoku then just take the few extra clicks to put them into SS to get the score.

IF it was possible for SS to generate a valid puzzle to a specified score/ or (minimum) technique level this would be a huge advance over JSudoku.


Top
 Profile  
Reply with quote  
PostPosted: Tue May 13, 2014 11:41 am 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
Ed wrote:
How long does it take on average to find a valid puzzle? Usually JSudoku takes a few milliseconds but sometimes can take minutes or even hours. If SS was too slow, I'd probably stick to JSudoku then just take the few extra clicks to put them into SS to get the score.
With the way I currently have it configured we are talking a few seconds to generate - but occasinally it is going away for longer. If I put in more checks on minimum score then it will take a little longer, as many of the puzzles are coming out at the bottom of the range at the moment.

The template generation is quite quick - it's finding a unique solution to fit into the template that is taking the time. At the moment there's no correlation between the time it takes and the complexity of the resulting puzzle - I'm still experimenting.


Top
 Profile  
Reply with quote  
PostPosted: Tue May 13, 2014 4:17 pm 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
rcbroughton wrote:
With the way I currently have it configured we are talking a few seconds to generate - but occasinally it is going away for longer. If I put in more checks on minimum score then it will take a little longer, as many of the puzzles are coming out at the bottom of the range at the moment. .


For example . . . I set a batch running to generate 102 puzzles and got the following stats after it completed in just over 35 minutes.
Code:
Min Time   0.02s
Max Time   140s
Avg Time   22s

Code:
Symmetry   
OneEightDeg   15
NinetyDeg   19
None   10
DiagonalTLBR   19
HorizVert   2
DiagonalTRBL   16
FULL   2
Diagonal   7
Vertical   10
Horizontal   2
Which implies 2 axis symmetry is more difficult to create than single axis symmetry
Code:
SS Score
0.85   45
0.9   13
0.95   8
1   7
1.05   5
1.1   3
1.15   2
1.2   4
1.25   2
1.3   1
1.35   2
1.4   2
1.5   1
2.05   1
2.1   1
2.15   1
2.2   1
4.05   1
6.05   1
6.9   1
Which shows a preponderance for simple puzzles at the moment.

A lot of work done . . . but a bit more to go


Top
 Profile  
Reply with quote  
PostPosted: Tue May 13, 2014 8:19 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Tue Aug 05, 2008 11:43 am
Posts: 251
Hi all,

Regarding generating killer sudokus. 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. What Richard's software can do on top of this however is to apply the solver following these two steps to check the suitability of the puzzle as a third step. Alternatively you can filter out a large batch of valid puzzles generated using the 1st two steps only with your batch solver to get suitable puzzles!!!


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

All times are UTC


Who is online

Users browsing this forum: No registered users and 10 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