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 1 of 2

Author:  rcbroughton [ Sun May 11, 2014 2:55 pm ]
Post subject:  Puzzle Generation in SudokuSolver

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

Author:  Ed [ Mon May 12, 2014 9:36 am ]
Post subject:  Re: Puzzle Generation in SudokuSolver

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

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

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

Author:  rcbroughton [ Mon May 12, 2014 9:38 pm ]
Post subject:  Re: Puzzle Generation in SudokuSolver

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?

Author:  Ed [ Tue May 13, 2014 9:20 am ]
Post subject:  Re: Puzzle Generation in SudokuSolver

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

Author:  rcbroughton [ Tue May 13, 2014 9:26 am ]
Post subject:  Re: Puzzle Generation in SudokuSolver

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

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

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.

Author:  rcbroughton [ Tue May 13, 2014 11:41 am ]
Post subject:  Re: Puzzle Generation in SudokuSolver

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.

Author:  rcbroughton [ Tue May 13, 2014 4:17 pm ]
Post subject:  Re: Puzzle Generation in SudokuSolver

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

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

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!!!

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