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 29F4EBB81 for ; Sat, 19 Nov 2005 13:43:51 +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 jAJChoa6020922 for ; Sat, 19 Nov 2005 13:43:50 +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 NAA07691 for ; Sat, 19 Nov 2005 13:43:49 +0100 (MET) Received: from ciao.gmane.org (main.gmane.org [80.91.229.2]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAJChmf7013818 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Sat, 19 Nov 2005 13:43:49 +0100 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1EdS2e-0001ka-PS for caml-list@inria.fr; Sat, 19 Nov 2005 13:42:04 +0100 Received: from visnu.math.unifi.it ([150.217.33.18]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 19 Nov 2005 13:42:04 +0100 Received: from maggesi by visnu.math.unifi.it with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 19 Nov 2005 13:42:04 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Marco Maggesi Subject: Yet another sudoku solver (838 bytes) Date: Sat, 19 Nov 2005 12:41:32 +0000 (UTC) Message-ID: X-Complaints-To: usenet@sea.gmane.org X-Gmane-NNTP-Posting-Host: visnu.math.unifi.it User-Agent: slrn/0.9.8.1 (Linux) Sender: news X-Miltered: at nez-perce with ID 437F1E06.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 437F1E04.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; solver:01 solver:01 solvers:01 ocamlopt:01 struct:01 rec:01 scanf:01 scanf:01 printf:01 printf:01 iter:01 838:98 838:98 functions:01 argument: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 While we are there, this is my soduku solver. It is not as efficient as the other solver proposed in this list, but it takes a fraction of seconds to compute a solution on a P4 anyway. Perhaps, the distinguishing feature of this implementation is that it uses higher order functions in an essential way (that is, the accumulator argument of the "fold" in the body of "search" is a function). And it is only 838 of code of clear (?) and concise code. BTW, now that we have so many sudoku solvers, wouldn't be be nice to have one with a computer certified implementation? Marco ------------------------------------------------------------ Instructions: $ ocamlopt -o sudoku sudoku.ml $ cat schema 0 6 0 1 0 0 0 5 0 0 0 8 3 0 5 6 0 0 2 0 0 0 0 0 0 0 1 8 0 0 4 0 7 0 0 6 0 0 6 0 0 0 3 0 0 7 0 0 9 0 1 0 0 4 5 0 0 0 0 0 0 0 2 0 0 7 0 0 6 9 0 0 0 4 0 0 0 8 0 7 0 $ ./sudoku < schema 9 6 3 1 7 4 2 5 8 1 7 8 3 2 5 6 4 9 2 5 4 6 8 9 7 3 1 8 2 1 4 3 7 5 9 6 4 9 6 8 5 2 3 1 7 7 3 5 9 6 1 8 2 4 5 8 9 7 1 3 4 6 2 3 1 7 2 4 6 9 8 5 6 4 2 5 9 8 1 7 3 ------------------- 8< ----------------------------------- 8< ------- include Set.Make(struct type t = (int * int) * int let compare = compare end) let (@) g f x = g (f x) and id x = x and sw f x y = f y x and zip x y = (x, y) let fold9 f = let rec loop i = if i>8 then id else loop (i+1) @ f i in loop 0 let fold81 f = fold9 (fold9 @ (@) f @ zip) let mark ((i,j),x as e) : t -> t = add e @ fold9 (fun k -> remove ((i/3*3 + k/3, j/3*3 + k mod 3), x) @ remove ((i,j),k) @ remove ((i,k),x) @ remove ((k,j),x)) let search = let g p f s = fold (f @ sw mark s) (filter ((=) p @ fst) s) in fold81 g let read () = let f p = Scanf.scanf "%d " (fun x -> if x>0 then mark (p,x-1) else id) in fold81 f (fold81 (fold9 @ ((@) add @ zip)) empty) let print s () = let pr ((i,j),x) = Printf.printf "%d%c" (x+1) (if j=8 then '\n' else ' ') in iter pr s; print_newline ();; search print (read ()) ();;