Sudoku: Difference between revisions
Content added Content deleted
m (added link to a C GPL code, while slowly translating from tcl ... :)) |
|||
Line 87: | Line 87: | ||
=={{header|J}}== |
=={{header|J}}== |
||
See [http://www.jsoftware.com/jwiki/Essays/Sudoku Solving Sudoku in J]. |
See [http://www.jsoftware.com/jwiki/Essays/Sudoku Solving Sudoku in J]. |
||
=={{header|OCaml}}== |
|||
uses the library [http://ocamlgraph.lri.fr/ ocamlgraph] |
|||
<lang ocaml>(* Ocamlgraph demo program: solving the Sudoku puzzle using graph coloring |
|||
Copyright 2004-2007 Sylvain Conchon, Jean-Christophe Filliatre, 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. *) |
|||
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 ()</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |