(**************************************************************************) (* *) (* Ocamlgraph: a generic graph library for OCaml *) (* Copyright (C) 2004-2007 *) (* Sylvain Conchon, Jean-Christophe Filliatre and Julien Signoles *) (* *) (* This software is free software; you can redistribute it and/or *) (* modify it under the terms of the GNU Library General Public *) (* License version 2, with the special exception on linking *) (* described in file LICENSE. *) (* *) (* This software is distributed in the hope that it will be useful, *) (* but WITHOUT ANY WARRANTY; without even the implied warranty of *) (* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *) (* *) (**************************************************************************) (* Ocamlgraph demo program: solving the Sudoku puzzle using graph coloring *) open Format open Graph (* We use undirected graphs with nodes containing a pair of integers (the cell coordinates in 0..8 x 0..8). The integer marks of the nodes will store the colors. *) module G = Imperative.Graph.Abstract(struct type t = int * int end) (* The Sudoku grid = a graph with 9x9 nodes *) let g = G.create () (* We create the 9x9 nodes, add them to the graph and keep them in a matrix for later access *) let nodes = let new_node i j = let v = G.V.create (i, j) in G.add_vertex g v; v in Array.init 9 (fun i -> Array.init 9 (new_node i)) let node i j = nodes.(i).(j) (* shortcut for easier access *) (* We add the edges: two nodes are connected whenever they can't have the same value, i.e. they belong to the same line, the same column or the same 3x3 group *) let () = for i = 0 to 8 do for j = 0 to 8 do for k = 0 to 8 do if k <> i then G.add_edge g (node i j) (node k j); if k <> j then G.add_edge g (node i j) (node i k); done; let gi = 3 * (i / 3) and gj = 3 * (j / 3) in for di = 0 to 2 do for dj = 0 to 2 do let i' = gi + di and j' = gj + dj in if i' <> i || j' <> j then G.add_edge g (node i j) (node i' j') done done done done (* Displaying the current state of the graph *) let display () = for i = 0 to 8 do for j = 0 to 8 do printf "%d" (G.Mark.get (node i j)) done; printf "\n"; done; printf "@?" (* We read the initial constraints from standard input and we display g *) let () = for i = 0 to 8 do let s = read_line () in for j = 0 to 8 do match s.[j] with | '1'..'9' as ch -> G.Mark.set (node i j) (Char.code ch - Char.code '0') | _ -> () done done; display (); printf "---------@." (* We solve the Sudoku by 9-coloring the graph g and we display the solution *) module C = Coloring.Mark(G) let () = C.coloring g 9; display () (* Local Variables: compile-command: "make -C .. bin/sudoku.opt" End: *)