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 E8B5CBB9A for ; Tue, 15 Nov 2005 14:22:18 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAFDMI1q007234 for ; Tue, 15 Nov 2005 14:22:18 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA21429 for ; Tue, 15 Nov 2005 14:22:17 +0100 (MET) 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 jAFDMHLP007230 for ; Tue, 15 Nov 2005 14:22:17 +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 jAFDMEBe085229 ; Tue, 15 Nov 2005 14:22:14 +0100 (CET) X-Ids: 165 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 OAA37576 ; Tue, 15 Nov 2005 14:17:54 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id OAA1327136 ; Tue, 15 Nov 2005 14:22:03 +0100 Date: Tue, 15 Nov 2005 14:22:02 +0100 (NFT) From: Diego Olivier Fernandez Pons To: Pascal Brisset Cc: caml-list@inria.fr Subject: Re: [Caml-list] Sudoku solver In-Reply-To: <4379DAEF.7060108@recherche.enac.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.165]); Tue, 15 Nov 2005 14:22:14 +0100 (CET) X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Miltered: at concorde with ID 4379E10A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4379E109.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 4379E106.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 backtracking:01 solvers:01 algorithm:01 instances:02 instances:02 checking:02 checking:02 constraints:02 hoc:02 seems:03 matching:05 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 "optimal algorithm" is not enough; some grids require more (for > example a "shaving" technique as described by Helmut). What I understood in Helmut's paper is that most of the Sudoku instances were backtrack-free when a combination of matching constraints was used (same with card, cardinality matrix, etc.) When shaving is allowed, forward checking or just bound consistency closes almost all the instances without backtracking. That might be a better advice for "ad hoc" solvers like Frisch's since he seems to be already doing forward checking. > where search is not included. So it does not solve all the instances: It shouldn't be difficult to add a simple search (generate) is it ? Diego Olivier