On 8/7/07, Hugh Perkins wrote:

Note that the "official" way to solve sudoku is to use "dancing links", but I guess you are creating a naive implementation precisely as a base-line against which to measure other implementations?

Well, Dancing Links (DLX) is just a data structure + few techniques to help with the backtrack, after modeling Sudoku as a contraint satisfaction problem. You can write a backtracking algorithm that is at least as fast as DLX :-) -- Vimal

On 8/7/07, Donald Bruce Stewart wrote:

See also,

http://haskell.org/haskellwiki/Sudoku

-- Don

Just out of ... errr.... curiosity... which of those implementations is the fastest?

On 8/7/07, Donald Bruce Stewart wrote:

No idea. You could compile them all with -O2, run them on a set of puzzles, and produce a table of results :-)

Well I could, but I wont ;-) If you had to guess which one is fastest which one would you guess? I'm a little surprised no one's tried a parallel solution yet, actually.

We've got an SMP runtime for a reason, people!

Funny that you should mention that, this was actually one of the Topcoder marathon match contests for multithreading: http://www.topcoder.com/longcontest/?module=ViewProblemStatement&compid=5624&rd=9892 (you'll need to login to see the problem statement, but basically it's Sudoku, on a 16-core Xeon (I think))

On 8/7/07, Murray Gross wrote:

I am working on a parallel brute-force solver, which will be tested on 25x25 puzzles (my current serial solver requires less than 1 second for the most difficult 9x9 puzzles I've been able to find; while I haven't tried it on 16x16 puzzles on one of the machines in the Brooklyn College Metis cluster, extrapolation from another machine indicates that 16x16 puzzles will take 15-20 minutes; the 25x25 test case I have requires about a week on a cluster machine).

Question: what do you mean by, for example 25x25? Do you mean grids with a total length of 25 on each side, eg: 21 13 4 19 18 17 22 1 6 24 10 11 8 14 12 2 16 23 7 15 25 20 3 5 9 1 16 6 5 10 14 25 2 8 15 23 7 24 21 13 20 3 17 11 9 19 4 18 22 12 3 2 17 9 11 4 18 7 5 12 16 19 25 20 6 22 13 21 24 10 15 14 8 23 1 23 20 25 12 15 11 16 13 19 3 5 9 1 17 22 14 4 18 8 6 7 2 10 21 24 7 14 8 24 22 23 20 9 21 10 4 2 18 15 3 19 12 1 25 5 6 17 16 11 13 18 5 16 11 4 25 23 6 13 1 21 12 10 24 8 15 20 14 3 22 17 9 2 19 7 17 10 22 8 23 15 7 21 20 4 3 6 2 1 19 25 9 5 12 18 11 13 24 16 14 12 19 13 2 6 3 10 14 24 17 7 20 9 11 4 23 1 8 16 21 22 5 25 15 18 15 9 14 20 3 12 8 19 16 5 22 25 17 23 18 11 24 13 2 7 21 6 1 4 10 25 7 1 21 24 2 9 22 11 18 15 5 14 13 16 10 6 19 4 17 23 8 12 3 20 2 17 23 3 19 8 6 12 10 20 14 18 16 25 24 9 21 15 1 4 13 22 11 7 5 13 24 15 1 20 19 21 23 4 7 6 17 5 2 11 16 18 22 10 3 9 12 14 8 25 9 22 12 16 21 1 13 17 18 25 19 8 15 4 7 5 14 2 20 11 24 3 23 10 6 8 6 7 10 14 16 5 3 22 11 12 23 21 9 20 17 25 24 13 19 4 18 15 1 2 11 18 5 4 25 24 2 15 9 14 13 22 3 10 1 8 23 7 6 12 20 16 19 17 21 16 15 19 13 12 10 3 4 17 6 20 21 23 18 25 24 7 9 14 8 1 11 5 2 22 14 21 18 22 9 7 11 16 23 2 8 1 6 12 5 3 19 20 15 13 10 24 17 25 4 6 8 11 7 2 5 1 24 25 9 17 14 13 16 15 18 10 4 22 23 12 19 21 20 3 5 4 20 25 1 13 15 8 12 22 11 24 19 3 10 6 17 16 21 2 18 7 9 14 23 24 3 10 23 17 18 19 20 14 21 9 4 22 7 2 1 11 12 5 25 8 15 13 6 16 10 12 9 6 5 22 14 18 7 13 25 16 11 8 21 4 15 3 17 1 2 23 20 24 19 19 25 24 18 16 20 17 5 2 8 1 10 4 6 23 12 22 11 9 14 3 21 7 13 15 22 23 3 17 7 6 12 25 15 19 2 13 20 5 14 21 8 10 18 24 16 1 4 9 11 4 11 2 15 8 21 24 10 1 16 18 3 7 19 9 13 5 6 23 20 14 25 22 12 17 20 1 21 14 13 9 4 11 3 23 24 15 12 22 17 7 2 25 19 16 5 10 6 18 8 ... or do you mean grids where each subgrid is 25x25, and the entire grid is 625 x 625?

Yes, by 25x25 puzzles I mean sudoku puzzles with 25 cells on each side, with the smaller squares being 5x5 (i.e., we need to construct rows with the numbers 1-25, and the smaller squares must each contain all of the numbers 1-25). Murray Gross Brooklyn College On Tue, 7 Aug 2007, Hugh Perkins wrote:

On 8/7/07, Hugh Perkins wrote:

...

Question: what do you mean by, for example 25x25? Do you mean grids with a total length of 25 on each side, eg:

(because on my super-dooper 1.66GHz Celeron, generating 10 random 25x25 grids such as the one above takes about 1.01 seconds; solving an actual puzzle should be faster because the solution space is more tightly constrained?)

On Saturday 18 August 2007 19:05:04 Wouter Swierstra wrote:

I hacked up a parallel version of Richard Bird's function pearl solver:

http://www.haskell.org/sitewiki/images/1/12/SudokuWss.hs

It not really optimized, but there are a few neat tricks there. Rather than prune the search space by rows, boxes, and columns sequentially, it represents the sudoku grid by a [[TVar [Int]]], where every cell has a TVar [Int] corresponding to the list of possible integers that would 'fit' in that cell. When the search space is pruned, we can fork off separate threads to prune by columns, rows, and boxes -- the joy of STM!

Is it possible to write a shorter Haskell version, perhaps along the lines of this OCaml: let invalid (i, j) (i', j') = i=i' || j=j' || i/n=i'/n && j/n=j'/n let select p n p' ns = if invalid p p' then filter ((<>) n) ns else ns let cmp (_, a) (_, b) = compare (length a) (length b) let add p n sols = sort cmp (map (fun (p', ns) -> p', select p n p' ns) sols) let rec search f sol = function | [] -> f sol | (p, ns)::sols -> iter (fun n -> search f (Map.add p n sol) (add p n sols)) ns -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e