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 89243BB9C for ; Wed, 16 Nov 2005 07:12:45 +0100 (CET) Received: from ptb-relay01.plus.net (ptb-relay01.plus.net [212.159.14.212]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAG6CiHh016101 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Wed, 16 Nov 2005 07:12:45 +0100 Received: from [80.229.56.224] (helo=chetara) by ptb-relay01.plus.net with esmtp (Exim) id 1EcGXE-0001AR-N9 for caml-list@yquem.inria.fr; Wed, 16 Nov 2005 06:12:44 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Sudoku solver Date: Wed, 16 Nov 2005 06:07:59 +0000 User-Agent: KMail/1.8.2 References: <200511150427.45996.jon@ffconsultancy.com> <4379A294.1050007@inria.fr> In-Reply-To: <4379A294.1050007@inria.fr> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200511160608.00635.jon@ffconsultancy.com> X-Miltered: at concorde with ID 437ACDDD.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 solver:01 frisch:01 solver:01 ocaml:01 caml-list:01 frisch:01 ocaml:01 solvers:01 integers:01 optimise:01 branching:01 bitfields:01 frog:98 wrote:01 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 On Tuesday 15 November 2005 08:55, Alain Frisch wrote: > Funny. My father told me about the game last sunday and I was willing to > write a solver too :-) On Tuesday 15 November 2005 20:56, Karl Zilles wrote: > Heh. My parents showed me a Sudoku puzzle when I last visited them. I > solved one just to get a feel for them, then wrote a simple > constraint/brute force solver in OCaml for fun. Looks like a lot of us > have. LOL. It seems that everyone on the caml-list just discovered and solved them. :-) > Here it is: > http://www.eleves.ens.fr/home/frisch/info/af-sudoku-brute.ml > http://www.eleves.ens.fr/home/frisch/info/af-sudoku.ml I'll add links from my page to everyone else's OCaml Sudoku solvers, if that's ok. :-) > It is faster than yours. :-p > E.g., when displaying all the solutions (there are 247 solutions for the > example): I found the 1905-solution "Sky blunder" to be a good example (warning: 6' penis): http://www.sudoku.org.uk/blunder.htm > 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. > The -brute version is a simple-minded brute force search. There other > one tries to use the constraint "each digit must appear in each bloc" > (where a bloc is a line, a column, or a 3x3 sub-bloc) to place digits. > It also chooses a cell with a minimal number of remaining choices when > branching. My program uses bitfields to keep track of which digits are valid. That may make it asymptotically faster than a brute force approach. I haven't thought about it much though (obviously not as much as Pascal!). > Interestingly, disabling these optimizations does not seem to > change the performance significantly. On real Sudoku puzzles? 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... -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. Objective CAML for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists