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 EB9CFBB9A; Tue, 15 Nov 2005 10:23:29 +0100 (CET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAF9NTwM009342; Tue, 15 Nov 2005 10:23:29 +0100 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.13.5/jtpda-5.4) with ESMTP id jAF9NKE2089899 ; Tue, 15 Nov 2005 10:23:20 +0100 (CET) X-Ids: 168 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id KAA22606 ; Tue, 15 Nov 2005 10:19:00 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id KAA663748 ; Tue, 15 Nov 2005 10:23:08 +0100 Date: Tue, 15 Nov 2005 10:23:08 +0100 (NFT) From: Diego Olivier Fernandez Pons To: Alain Frisch Cc: Jon Harrop , Subject: Re: [Caml-list] Sudoku solver In-Reply-To: <4379A294.1050007@inria.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.7.2 (shiva.jussieu.fr [134.157.0.168]); Tue, 15 Nov 2005 10:23:25 +0100 (CET) X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Miltered: at concorde with ID 4379A911.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 4379A908.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 caml-list:01 solver:01 branching:01 solver:01 graph:01 algorithm:01 algorithm:01 constraint:01 constraint:01 constraints:02 algorithms:03 optimization:03 naive:03 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 Bonjour, > 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. Interestingly, disabling these optimizations does not seem to > change the performance significantly. The constraint "a single digit by block" is named "all different" in combinatorial optimization literature. The problem is that your implementation is too naive : the "optimal" version (in the sense it can ensure you always make a choice that has at least one solution for the 'alldiff' constraint) needs a matching algorithm and some graph theory. There is a nice paper by Helmut Simonis "Sudoku as a constraint problem" with reference to the relevant paper for the algorithms. http://www.icparc.ic.ac.uk/~hs/ You could also try to write a solver with FaCiLe (which actually contains the optimal algorithm for "alldiff" constraints) Diego Olivier