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 8B9EFBB9C for ; Tue, 15 Nov 2005 20:05:21 +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 jAFJ5LXk017176 for ; Tue, 15 Nov 2005 20:05:21 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA31811 for ; Tue, 15 Nov 2005 20:05:19 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAFJ5J3W004906 for ; Tue, 15 Nov 2005 20:05:19 +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 jAFJ5IBN055672 ; Tue, 15 Nov 2005 20:05:18 +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 UAA25182 ; Tue, 15 Nov 2005 20:00:58 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id UAA1478662 ; Tue, 15 Nov 2005 20:05:07 +0100 Date: Tue, 15 Nov 2005 20:05:06 +0100 (NFT) From: Diego Olivier Fernandez Pons To: Christophe Raffalli Cc: caml-list Subject: Re: [Caml-list] Sudoku solver In-Reply-To: <4379F37C.2010408@univ-savoie.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 20:05:18 +0100 (CET) X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Miltered: at concorde with ID 437A3171.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 437A316F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 437A316E.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 higher-level:01 algorithm:01 constraint:01 guess:02 programming:03 notion:04 problem:05 problem:05 fernandez:06 fernandez:06 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, > And what about a sudoko generator with a pertinent notion of level for a > human ? Would be nice if you could choose the cases that are filled from > start ... Actually that is what Helmut Simonis was trying to do with his paper. He considers : - difficulty (= level of "complexity" of the filtering algorithm needed to solve the problem without backtracking) - minimality (= number of non-redundant information for each deduction) > These are not formal definition ... yet, but using a representation of > the problem as a set of close, I think we can do something with the > complexity of the proof search ... Constraint programming is has a higher-level representation but I guess the same could be achieved in SAT. Diego Olivier