Calcudoku puzzle forum http://www.calcudoku.org/forum/ 

describe your solver http://www.calcudoku.org/forum/viewtopic.php?f=3&t=64 
Page 2 of 3 
Author:  pnm [ Sun Aug 19, 2012 10:55 pm ] 
Post subject:  Re: describe your solver 
Some more (!) http://dlbeer.co.nz/oss/cdok.html 
Author:  pnm [ Mon Aug 20, 2012 11:39 pm ] 
Post subject:  Re: describe your solver 
sneaklyfox wrote: Wow, that is really good. (I mean a good solver.) I tried today's 9x9 difficult and it took less than a second to give me the answer (although I already did the puzzle). I'm still quite pleased that my solver is an order of magnitude faster (that said, I don't know of course what's running on their server, maybe it's interpreted haskell) Edit: now it looks like it's faster for some puzzles and slower for others (!) Patrick 
Author:  pnm [ Tue Aug 21, 2012 1:10 pm ] 
Post subject:  Re: describe your solver 
pnm wrote: That is easy to do, but maybe it'd be better to talk to the site owners themselves instead. Maybe make it so they modify the page so today's puzzles are never accepted, for example. Update: Henry Laxen has been very helpful, and quickly implemented a restriction that only allows you to solve yesterday's puzzles (and older than 3 days if it's a 12x12) Patrick 
Author:  clm [ Tue Aug 21, 2012 1:53 pm ] 
Post subject:  Re: describe your solver 
pnm wrote: pnm wrote: That is easy to do, but maybe it'd be better to talk to the site owners themselves instead. Maybe make it so they modify the page so today's puzzles are never accepted, for example. Update: Henry Laxen has been very helpful, and quickly implemented a restriction that only allows you to solve yesterday's puzzles (and older than 3 days if it's a 12x12) Patrick Congrats! and very reasonable Henry Laxen 
Author:  pharosian [ Tue Aug 21, 2012 4:23 pm ] 
Post subject:  Re: describe your solver 
Sadly, I was not up to the challenge of the 5x5 difficult of 19 August. I was curious to know the solution, so I entered the URL into Henry Laxen's solver, and this is the answer it gave me in 0.01 seconds: 2 5 1 3 4 5 1 3 4 2 4 3 2 1 5 3 4 5 2 1 1 2 4 5 3 The only problem is that it's wrong. The cage at a1b1a2 is 30x, so the 2,5,5 provided doesn't work. Likewise, the 10+ cage doesn't work, but all the others do. 
Author:  pnm [ Tue Aug 21, 2012 4:31 pm ] 
Post subject:  Re: describe your solver 
pharosian wrote: The only problem is that it's wrong. The cage at a1b1a2 is 30x, so the 2,5,5 provided doesn't work. Likewise, the 10+ cage doesn't work, but all the others do. I sent Henry a note about this. Note that you can always get the solution of "expired" puzzles by clicking "Show solution" (so for this puzzle: http://www.calcudoku.org/en/20120819/5/3/1) Patrick 
Author:  pharosian [ Wed Aug 22, 2012 1:27 am ] 
Post subject:  Re: describe your solver 
Yes, I've used the "Show Solution" link many times... usually for the larger puzzles. But I thought this would be a good test of the solver. I also sent him a note. I meant to mention that in my original post. 
Author:  maffoo [ Sun Feb 02, 2014 1:09 pm ] 
Post subject:  Re: describe your solver 
I wrote a solver in scala that follows strategies very similar to those others have described here. Basically, I encode cages, rows and columns as constraints; each constraint contains a set of grid coordinates, and a mathematical operation that must be satisfied by the numbers assigned to those grid squares, plus whether or not the numbers must be unique. Then, the program keeps track of candidates in each grid location, and at each stage simply picks one candidate for one particular square, then recursively applies all the constraints to eliminate any candidates that are no longer possible. If a constraint violation is ever detected or a square is found with no remaining candidates, the program backtracks and tries a different candidate. This naive approach works very nicely for almost all of the puzzles, though it seems to take longest on the killer sudoku puzzles. I have some ideas about including some more specific strategies of the kind I use when solving killer sudoku manually, but the generic solver works quickly enough for now. One thing I developed that might be of interest to others is a textual description of the puzzles that the program can parse into its internal representation and then solve. I wanted something I could type easily while scanning the puzzle visually, and basically the idea is to use the numeric value and math operation in squares where it appears (e.g. 8+ or 5; I use '%' for mod and '/' for division, and otherwise the standard math operators), and for other squares indicate which cage they belong to by 'pointing' at a neighboring square that is also in the cage (e.g. '<' indicates this belongs in a cage with the square to the left, '>' is to the right, 'v' is below, and '.' is above [wanted to use '^' but that is the exponentiation operator]). So a puzzle like this 8x8 (http://www.calcudoku.org/en/20140130/8/3) becomes: Code: 5=288x<256x<10+4= 0%>..24x>.< .4%8=0%.3%2%< 4%.1%.2=.8=3% .28x.0%<110+. 2%.<8=1..0% .2%0%>.120x<. 8=..30x<2=.7= It looks a little cryptic, but is pretty quick to type once you get the hang of it. The only additional piece of information the solver needs is what the starting number is (if not 1) and whether this is a killer sudoku puzzle, since those have additional 3x3 constraints in addition to the cages and rows/cols. With this representation, I can read the puzzle right into the solver, and the solver spits back the solution to be entered into the grid. Of course, all that typing gets tedious so now I have a greasemonkey script that produces this representation directly from the html page and copies it to the clipboard so I can just paste it into the solver. Next I'm planning to just run the solver right in the page, cut out the middleman (myself) altogether, possibly compiling what I have with a scalatojavascript compiler (http://www.scalajs.org/) so I don't have to rewrite things in javascript. 
Author:  pnm [ Sun Feb 02, 2014 1:42 pm ] 
Post subject:  Re: describe your solver 
Thanks for the detailed post, very interesting maffoo wrote: Of course, all that typing gets tedious so now I have a greasemonkey script that produces this representation directly from the html page and copies it to the clipboard so I can just paste it into the solver. Yes, greasemonkey, you can do a lot with that. A totally simple thing would be to reenable error checking for the timed puzzles (although I could of course make some changes to make that harder). Patrick 
Author:  pnm [ Mon Mar 03, 2014 1:52 pm ] 
Post subject:  Re: describe your solver 
I came across this page, a couple of solvers written in Fortran 90 (!) https://sites.google.com/site/skjgeek 
Page 2 of 3  All times are UTC + 1 hour [ DST ] 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ 