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: 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: Here is how SudokuSolver did it: Here is how JSudoku did it using my solver order: 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: 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 This sounds really good!1) generating a cage pattern (or you could define one) with zero cage values - 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 Which implies 2 axis symmetry is more difficult to create than single axis symmetryOneEightDeg 15 NinetyDeg 19 None 10 DiagonalTLBR 19 HorizVert 2 DiagonalTRBL 16 FULL 2 Diagonal 7 Vertical 10 Horizontal 2 Code: SS Score Which shows a preponderance for simple puzzles at the moment.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 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/ |