1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
(**************************************************************************)
(* *)
(* 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 ()
|
