View unanswered posts | View active topics It is currently Tue Mar 19, 2024 5:19 am



← Back to the Calcudoku puzzle page




Reply to topic  [ 31 posts ]  Go to page Previous  1, 2, 3, 4  Next
 describe your solver 
Author Message
User avatar

Posted on: Sun Aug 19, 2012 10:55 pm




Posts: 3295
Joined: Thu May 12, 2011 11:58 pm
Post Re: describe your solver
Some more (!)

http://dlbeer.co.nz/oss/cdok.html


Profile
User avatar

Posted on: Mon Aug 20, 2012 11:39 pm




Posts: 3295
Joined: Thu May 12, 2011 11:58 pm
Post 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


Last edited by pnm on Tue Aug 21, 2012 3:43 pm, edited 1 time in total.



Profile
User avatar

Posted on: Tue Aug 21, 2012 1:10 pm




Posts: 3295
Joined: Thu May 12, 2011 11:58 pm
Post 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


Profile

Posted on: Tue Aug 21, 2012 1:53 pm




Posts: 855
Joined: Fri May 13, 2011 6:51 pm
Post 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! [thumbsup] and very reasonable Henry Laxen [thumbup]


Profile

Posted on: Tue Aug 21, 2012 4:23 pm




Posts: 116
Joined: Sat May 14, 2011 3:18 am
Post 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 a1-b1-a2 is 30x, so the 2,5,5 provided doesn't work. Likewise, the 10+ cage doesn't work, but all the others do.


Profile
User avatar

Posted on: Tue Aug 21, 2012 4:31 pm




Posts: 3295
Joined: Thu May 12, 2011 11:58 pm
Post Re: describe your solver
pharosian wrote:
The only problem is that it's wrong. The cage at a1-b1-a2 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/2012-08-19/5/3/1)

Patrick


Profile

Posted on: Wed Aug 22, 2012 1:27 am




Posts: 116
Joined: Sat May 14, 2011 3:18 am
Post 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.


Profile

Posted on: Sun Feb 02, 2014 1:09 pm




Posts: 1
Joined: Sun Mar 04, 2012 12:48 am
Post 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/2014-01-30/8/3) becomes:

Code:
5=288x<2-56x<10+4=
0%>..24x>.<
.4%8=0%.3%2%<
4%.1%.2=.8=3%
.28x.0%<1-10+.
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 scala-to-javascript compiler (http://www.scala-js.org/) so I don't have to rewrite things in javascript.


Profile
User avatar

Posted on: Sun Feb 02, 2014 1:42 pm




Posts: 3295
Joined: Thu May 12, 2011 11:58 pm
Post Re: describe your solver
Thanks for the detailed post, very interesting [thumbup]

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 re-enable error checking
for the timed puzzles (although I could of course make some changes to make that harder).

Patrick


Profile
User avatar

Posted on: Mon Mar 03, 2014 1:52 pm




Posts: 3295
Joined: Thu May 12, 2011 11:58 pm
Post Re: describe your solver
I came across this page, a couple of solvers written in Fortran 90 (!)

https://sites.google.com/site/skjgeek


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 31 posts ]  Go to page Previous  1, 2, 3, 4  Next

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

Search for:
Jump to:  
cron
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.