# Code Review: Sudoku solver

41 messages
123
Open this post in threaded view
|

## Code Review: Sudoku solver

 Hi All, I really appreciate all the help I received when I asked you to   critique my PrefixMap module a few weeks ago.  I think I am making   good progress in correcting the "lisp" in my Haskell programming.   I'll be very grateful to anyone who can take a glance at the attached   short program and say if any unidiomatic usages pop out.  It solves   sudoku puzzles.  (What pleasure do people get by doing these in their   heads?!?) Cheers, David -------------------------------- David F. Place mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe sudoku.hs (4K) Download Attachment
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 On 3/22/06, David F. Place <[hidden email]> wrote: > Hi All, > > I really appreciate all the help I received when I asked you to > critique my PrefixMap module a few weeks ago.  I think I am making > good progress in correcting the "lisp" in my Haskell programming. > I'll be very grateful to anyone who can take a glance at the attached > short program and say if any unidiomatic usages pop out Try > cellIndex r c = 3*(r `div` 3) + c `div` 3 It's much much shorter and should produce the same results. > It solves > sudoku puzzles.  (What pleasure do people get by doing these in their > heads?!?) > They are probably asking the same question: why take hours to write a program to do it when with my mad sudoku solving skills I can solve it in X seconds? My roommate is like this. Cheers,    Jared. -- http://www.updike.org/~jared/reverse ")-:" _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 In reply to this post by Jared Updike Jared Updike wrote: > On 3/22/06, David F. Place <[hidden email]> wrote: > ... > > It solves > > sudoku puzzles.  (What pleasure do people get by doing these in their > > heads?!?) > > > > They are probably asking the same question: why take hours to write a > program to do it when with my mad sudoku solving skills I can solve it > in X seconds? My roommate is like this. I would say because they have chosen the wrong language for this problem :-) Solving Sudoku is a typical finite domain constraint problem. Thus, a language with constraint solving facilities like Curry (a combination of Haskell and constraint logic programming) is much better suited. Actually, I wrote a Sudoku solver in Curry and the actual code for the solver is 10 lines of code which is compact and well readable (if you are familiar with Haskell), see http://www.informatik.uni-kiel.de/~curry/examples/CLP/sudoku.curryRegards, Michael _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 Chris wrote: > You need more than 5 examples.  The truly evil puzzles are rarer than that.  Go > get the set of minimal puzzles and see how far your logic takes you. Chris elucidated some of my questions before I finished writing my email... Claus wrote: > (*) actually, that was a bit disappointing!-( How much harder is the problem of generating (hard/medium/easy) (solvable) Sudoku puzzles? Are all puzzles solvable (that don't break the rules at any point)? I imagine a simple way is to start with a correctly saturated grid of numbers and then start randomly shooting holes in it and testing if it is still solvable (either unambiguously or ambiguously) with your Sudoku solver? A rough mesaure of the difficulty of the unsolved puzzle could be how long the solver took to solve it (number of steps) (and the number of possible solutions)? Are puzzles with multiple solutions usually considered harder or easier? Are these considered proper puzzles? Is this a more interesting problem to try to solve (generating) rather than solving puzzles? I haven't investigated it much but I thought about it when I was writing YASS (Yet Another Sudoku Solver) of my own. What makes a Sudoku puzzle fiendish? Just the amount of missing information, the amount of lookahed required?   Jared. P.S. Another interesting problem could be trying other number arrangements besides 9x9, e.g. hexadecimal puzzles... I wrote my solver to handle these but I never saw other than 9x9 puzzles to try it on (hence the idea of generating puzzles)... Is that because most people want puzzles to solve by hand instead of computer? -- http://www.updike.org/~jared/reverse ")-:" _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 In reply to this post by Claus Reinke > since I haven't factored out the constraint propagation into a > general module, the core of my code is a lot longer than the Curry version > (about 60 additional lines, though I'm sure one could reduce that;-). the > only negative point I can find about the Curry example is that it isn't > obvious what tricks the FD-constraint solver is using Curry does not have a constraint solver of its own. It simply delegates all constraints to the FD solver of SICStus Prolog. The all_different constraint subsumes the rules that you describe, depending on the consistency algorithm used. FD solvers implement general but efficient algorithms that are much more complex than a few simple rules. See http://www.sics.se/sicstus/docs/latest/html/sicstus/Combinatorial-Constraints.html#Combinatorial%20Constraintsfor the SICStus FD all_different documentation. > (ie., it would be nice > to have a concise language for expressing propagation techniques, and then > explicitly to apply a strategy to the declarative specification, instead of > the implicit, fixed strategy of the built-in solver). CHR is meant as a highlevel language for expressing propagation. It (currently) does not include a strategy language though. Cheers, Tom -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: [hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re[2]: Code Review: Sudoku solver

 In reply to this post by Jared Updike Hello it seems that sudoku solver may be a good candidate for nofib suite / language comparison shootout -- Best regards,  Bulat                            mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 In reply to this post by Bulat Ziganshin-2 bulat.ziganshin: > Hello > > it seems that sudoku solver may be a good candidate for nofib suite / > language comparison shootout It would also be nice to see some example sudoku solvers posted on an `Idioms' page on haskell.org:    http://www.haskell.org/haskellwiki/Category:Idioms  someone could just  create a new page 'Sudoku' and add the phrase [Category:Idioms]] to the text, and it will be indexed. Seeing 4 or 5 solutions would be a useful tutorial, I'd imagine. -- Don _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 In reply to this post by Daniel Fischer-4 On 2006-04-03, Daniel Fischer <[hidden email]> wrote: > does anybody know whether in a uniquly solvable sudoku-puzzle guessing is > never necessary, i.e. by proper reasoning ('if I put 6 here, then there must > be a 3 and thus the 4 must go there...' is what I call guessing) there is > always at least one entry determined? No, it sometimes is, (well, depending on your set of base inference rules -- throwing all possible solutions in and doing pattern matching technically allows no-backtracking solutions). Most people use "eliminate all impossible numbers in a given box (that is, that number occurs in same row, column, or square)", combined with "if there is only one place in this {row, column, square} a number can be, place it." But there are additional common patterns such as "if there are N boxes in a {row, column, square}, each with a subset of N numbers, then eliminate those numbers in the other squares.  For example if two boxes in a row both only allow 2 and 3, then 2 and 3 can be eliminated from all the other boxes in that row.  These are often worth implementing as they can radically reduce guessing.  Also worth doing may be chains of reasoning that can restrict a number to be in a given row or column of a square (or square of a row or column), which can then eliminate it from other places. -- Aaron Denney -><- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 In reply to this post by Daniel Fischer-4 Daniel Fischer wrote: > does anybody know whether in a uniquly solvable sudoku-puzzle guessing is > never necessary, i.e. by proper reasoning ('if I put 6 here, then there must > be a 3 and thus the 4 must go there...' is what I call guessing) there is > always at least one entry determined? > http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf"As an application, we prove the ASP-completeness (which implies NP-completeness) of three popular puzzles: Slither Link, Cross Sum, and Number Place." As the size of the puzzle N increases, it is np-complete. (3x3x3,4x4x4,5x5x5,...) And the definition of "logic" vs "brute force" is a imprecise.  Complex logic looks like "hypothetical guess and check", and the efficient dancing links algorithm by Knuth is very smart brute force. -- Chris _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 In reply to this post by Jared Updike On Mon, 3 Apr 2006, Jared Updike wrote: > or ambiguously) with your Sudoku solver? A rough mesaure of the > difficulty of the unsolved puzzle could be how long the solver took to > solve it (number of steps) (and the number of possible solutions)? Are > puzzles with multiple solutions usually considered harder or easier? > Are these considered proper puzzles? It's an interesting test to run a Sudoku solver on an empty array. :-) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Code Review: Sudoku solver

 Henning Thielemann wrote: > > On Mon, 3 Apr 2006, Jared Updike wrote: > >> or ambiguously) with your Sudoku solver? A rough mesaure of the >> difficulty of the unsolved puzzle could be how long the solver took to >> solve it (number of steps) (and the number of possible solutions)? Are >> puzzles with multiple solutions usually considered harder or easier? >> Are these considered proper puzzles? > > It's an interesting test to run a Sudoku solver on an empty array. :-) I am cleaning up my old (aka inexperienced) solver based on Knuth's dancing links to put on the wiki.  The code is very different than most Haskell solutions, since it revolves around a mutable data structure (which is not an MArray). It "solves" an empty array in 81 steps with no backtracking.   It will produce a list of all the solutions of an empty board quite efficiently. Cleaning up my "logic" based solver will take longer. -- Chris _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe