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 nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 672F7BB9A for ; Tue, 15 Nov 2005 13:56:23 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAFCuMKp030451 for ; Tue, 15 Nov 2005 13:56:23 +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 NAA20703 for ; Tue, 15 Nov 2005 13:56:22 +0100 (MET) Received: from normandie.enac.fr (matrix.enac.fr [195.220.159.203]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAFCuM0J003105 for ; Tue, 15 Nov 2005 13:56:22 +0100 Received: from matrix.enac.fr (localhost.enac.fr [127.0.0.1]) by normandie.enac.fr (Postfix) with ESMTP id 911EEDD0070; Tue, 15 Nov 2005 13:56:21 +0100 (CET) Received: by matrix.enac.fr (Postfix, from userid 12347) id 36A31348031; Tue, 15 Nov 2005 13:56:21 +0100 (CET) Received: from indigo.recherche.enac.fr (indigo.recherche.enac.fr [10.3.1.5]) by matrix.enac.fr (Postfix) with ESMTP id 1F57F34802F; Tue, 15 Nov 2005 13:56:19 +0100 (CET) Received: from [10.31.1.82] (sepia.recherche.enac.fr [10.31.1.82]) by indigo.recherche.enac.fr (Postfix) with ESMTP id 5510D5F43B; Tue, 15 Nov 2005 13:56:15 +0100 (CET) Message-ID: <4379DAEF.7060108@recherche.enac.fr> Date: Tue, 15 Nov 2005 13:56:15 +0100 From: Pascal Brisset User-Agent: Debian Thunderbird 1.0.2 (X11/20051002) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Diego Olivier Fernandez Pons Cc: caml-list@inria.fr Subject: Re: [Caml-list] Sudoku solver References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 4379DAF6.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4379DAF6.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; brisset:01 brisset:01 enac:01 caml-list:01 solver:01 enac:01 cstr:01 gcc:01 cstr:01 gcc:01 iteri:01 iteri:01 unify:01 char:01 char: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 The "optimal algorithm" is not enough; some grids require more (for example a "shaving" technique as described by Helmut). Using FaCiLe (http://www.recherche.enac.fr/opti/facile/), a naive solution could look like: --8<----------------------- open Facile open Easy (** THE All Different constraint **) let cards = Array.init 9 (fun i -> Fd.int 1, (i+1)) let ad = fun a -> Cstr.post (Gcc.cstr ~level:Gcc.High a cards) let solve grille = (** The matrix of variables **) let v = Array.init 9 (fun _ -> Fd.array 9 1 9) in (** Preset values **) Array.iteri (fun i vi -> Array.iteri (fun j vij -> let c = grille i j in if c <> '.' then Fd.unify vij (Char.code c - Char.code '0')) vi) v; (** Lines **) Array.iter ad v; (** Columns **) for i = 0 to 8 do ad (Array.init 9 (fun j -> v.(j).(i))) done; (** Regions **) for i = 0 to 2 do for j = 0 to 2 do ad (Array.init 9 (fun k -> v.(3*i+k/3).(3*j+k mod 3))) done done; (** Print **) Array.iter (fun vi -> Fd.fprint_array stdout vi; print_newline ()) v; print_newline () (** Solving all the grids from a file (one per line) **) let _ = let f = open_in Sys.argv.(1) in try while true do let l = input_line f in solve (fun i j -> l.[9*i+j]) done with End_of_file -> () --8<----------------------- where search is not included. So it does not solve all the instances: % cat grids.txt ............87.26..1.6.2..8...1..8.446.....973.1..4...8..2.7.4..49.16............ .18...7.....3..2...7...........71...6......4.3........4..5....3.2..8...........6. % ./sudoku grids.txt [|6; 8; 2; 9; 4; 5; 7; 1; 3|] [|5; 3; 4; 8; 7; 1; 2; 6; 9|] [|9; 1; 7; 6; 3; 2; 4; 5; 8|] [|2; 7; 5; 1; 6; 9; 8; 3; 4|] [|4; 6; 8; 5; 2; 3; 1; 9; 7|] [|3; 9; 1; 7; 8; 4; 6; 2; 5|] [|8; 5; 6; 2; 9; 7; 3; 4; 1|] [|7; 4; 9; 3; 1; 6; 5; 8; 2|] [|1; 2; 3; 4; 5; 8; 9; 7; 6|] [|_81[2;5;9]; 1; 8; _84[2;4;6;9]; _85[2;4-6;9]; _86[2;4-6;9]; 7; 3; _89[4-6;9]|] [|_90[5;9]; 6; 4; 3; _94[1;5;9]; 7; 2; 8; _98[1;5;9]|] [|_99[2;5;9]; 7; 3; _102[1-2;4;6;8-9]; _103[1-2;4-6;9]; _104[2;4-6;8-9]; _105[1;4-6;9]; _106[1;5;9]; _107[1;4-6;9]|] [|8; _109[4-5;9]; 2; _111[4;6;9]; 7; 1; 3; _115[5;9]; _116[5-6;9]|] [|6; _118[5;9]; _119[1;7]; _120[2;8-9]; 3; _122[2;5;8-9]; _123[1;5;9]; 4; _125[7-8]|] [|3; _127[4-5;9]; _128[1;7]; _129[4;6;8-9]; _130[4-6;9]; _131[4-6;8-9]; _132[1;5-6;9]; 2; _134[7-8]|] [|4; 8; _137[6;9]; 5; _139[1-2;6;9]; _140[2;6;9]; _141[1;9]; 7; 3|] [|_144[1;7]; 2; _146[6;9]; _147[1;4;6-7;9]; 8; 3; _150[1;4-5;9]; _151[1;5;9]; _152[1;4-5;9]|] [|_153[1;7]; 3; 5; _156[1;4;7;9]; _157[1;4;9]; _158[4;9]; 8; 6; 2|] For the second instance, the remaining possible values for each number are displayed. Inferences taking into account several constraints (line, column or region) in the same time are required to do more. --Pascal Diego Olivier Fernandez Pons wrote: > 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