From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 7A6B2BB9C for ; Wed, 16 Nov 2005 08:30:37 +0100 (CET) Received: from smtp2-g19.free.fr (smtp2-g19.free.fr [212.27.42.28]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAG7UbHU024190 for ; Wed, 16 Nov 2005 08:30:37 +0100 Received: from [192.168.0.2] (rke75-3-82-229-183-156.fbx.proxad.net [82.229.183.156]) by smtp2-g19.free.fr (Postfix) with ESMTP id ED2FD5231E; Wed, 16 Nov 2005 08:30:36 +0100 (CET) Message-ID: <437ADEEC.2050904@inria.fr> Date: Wed, 16 Nov 2005 08:25:32 +0100 From: Alain Frisch User-Agent: Debian Thunderbird 1.0.2 (X11/20050602) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Sudoku solver References: <200511150427.45996.jon@ffconsultancy.com> <4379A294.1050007@inria.fr> <200511160608.00635.jon@ffconsultancy.com> In-Reply-To: <200511160608.00635.jon@ffconsultancy.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 437AE01D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; frisch:01 frisch:01 caml-list:01 solver:01 ocaml:01 solvers:01 integers:01 optimise:01 doubles:01 solver:01 solvers:01 98%:98 74%:98 87%:98 86%:98 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 Jon Harrop wrote: > I'll add links from my page to everyone else's OCaml Sudoku solvers, if that's > ok. :-) No problem for me. > I found the 1905-solution "Sky blunder" to be a good example (warning: 6' > penis): > > http://www.sudoku.org.uk/blunder.htm $ time ./sudoku < sky > /dev/null 14.40s user 0.01s system 98% cpu 14.630 total $ time ./af-sudoku-brute < sky > /dev/null 0.05s user 0.00s system 74% cpu 0.068 total $ time ./af-sudoku < sky > /dev/null 0.14s user 0.01s system 87% cpu 0.168 total >>I guess your choice of a functional data structure explains the 100x >>slow-down... Hint: copying an array of 81 integers is fast. > > > I'd be surprised if the functional data structure was responsible for a 100x > slowdown, 10x maybe. I was going to optimise it but, because it solves > puzzles in <1sec anyway, I decided to concentrate on making it concise > instead. Using this compare function: let compare (x1,y1) (x2,y2) = if x1 = x2 then y1 - y2 else x1 - x2 already doubles the speed of your program. In general, the built-in polymorphic comparisons are a bad idea as soon as effiency matters. >>Interestingly, disabling these optimizations does not seem to >> change the performance significantly. > On real Sudoku puzzles? Hard to tell, I'd need to find a slower machine ;-) For today's puzzle from http://www.sudoku.org.uk/daily.asp: $ time ./sudoku < daily > /dev/null 0.25s user 0.00s system 86% cpu 0.291 total $ time ./af-sudoku < daily > /dev/null 0.00s user 0.00s system 76% cpu 0.001 total $ time ./af-sudoku-brute < daily > /dev/null 0.00s user 0.00s system 81% cpu 0.001 total > I found a brute force solver written in Lisp on the net. My implementation was > much slower for valid Sudoku puzzles but just as fast for Sky's erroneous one > and much faster at finding any solution from a blank board. Of course, I may > well have been measuring nothing more than language start-up time... Again, my solvers give the first solution in 0.00s from a blank board ;-) I'm not yet convinced that for solving 9x9 grids, complex resolution techniques from constraint solving bring much. They do probably for larger grids and maybe for problem generation... -- Alain