* -----------------------------------------------------------------------
SUDOKU
------------------------------------------------------------------------*)

(* ____________________version sans exception _____________________ *)


(* la fonction correct teste si le numéro en position (i,j) crée une contradiction ie si ce numéro apparait ailleurs sur la même ligne ou colonne, ou dans le même bloc 3x3 *)

let correct (t:int vect vect) (i:int) (j:int) =
let a = t.(i).(j) and x = 3 * (i / 3) and y = 3 * (j / 3) in
let resultat=ref true and k=ref 0 and p=ref 0 in
while (!k<9) && !resultat do
if !k <> i && t.(!k).(j) = a then resultat:=false;
if !k <> j && t.(i).(!k) = a then resultat:=false;
incr k
done;
k:=x;
while (!k<x+3) && !resultat do
p:=y;
while (!p<y+3) && !resultat do
if (!k, !p) <> (i, j) && t.(!k).(!p) = a then resultat:=false;
incr p
done;
incr k
done;
!resultat;;

(* la fonction cherche_vide cherche une case vide dans le tableau (contient 0 par convention ). renvoie un couple (i,j), (-1,-1) si aucune case vide n'est trouvée. *)

let cherche_vide (t:int vect vect)=
let solution=ref (-1,-1) and i=ref 0 and j=ref 0 in
while !solution=(-1,-1) && !i<9 do
j:=0;
while !solution=(-1,-1) && !j<9 do
if t.(!i).(!j)=0 then solution:=(!i,!j);
incr j
done;
incr i
done;
!solution;;

let rec sudoku (t:int vect vect) =
match cherche_vide t with
|(-1,-1)->true (* plus de case vide. On a fini *)
|(i,j)-> let k=ref 1 and trouve=ref false in
while !k<10 && (not !trouve) do
t.(i).(j)<- !k;
if correct t i j then trouve:= sudoku t;
incr k;
done;
if not !trouve then t.(i).(j)<-0;
!trouve;;

(*______________________ interface graphique ______________________*)

#open "graphics";;
open_graph "";;

let sudo t =

(* tracé du quadrillage *)
clear_graph();
let xx = ref (- 1) and yy = ref (- 1) in
let base = 30 in
let refresh() =
for i = 0 to 8 do
for j = 0 to 8 do
set_color black; fill_rect (base * i) (base * j) base base;
if !xx = i && !yy = j then set_color red else set_color green;
fill_rect (base * i + 1) (base * j + 1) (base - 1) (base - 1);
if t.(i).(j) <> 0 then begin
set_color black; moveto (base * i + base / 3) (base * j + base / 3); draw_string (string_of_int t.(i).(j))
end;
done;
done;
in
refresh();
set_color black; moveto base (base * 12); draw_string "Choix de case a la souris";
moveto base (base * 23 / 2); draw_string "Taper sur un chiffre pour changer une valeur (0 pour effacer)";
moveto base (base * 11); draw_string "touche <espace> pour résoudre";


(* boucle interactive *)
let continue = ref true in
while !continue do
let ev = wait_next_event [Button_down; Key_pressed] in
if ev.button then begin
let x = ev.mouse_x / base and y = ev.mouse_y / base in
if x < 9 && y < 9 then begin
xx := x; yy := y; refresh();
end
end
else
begin
match ev.key with
| ` ` -> continue := false
| c -> let n = int_of_char c in
if 48 <= n && n <= 57 then begin
t.(!xx).(!yy) <- n - 48; refresh()

end;

end;

done;
let ok = sudoku t in
if ok then begin
for i = 0 to 8 do
for j = 0 to 8 do
set_color black; fill_rect (base * i) (base * j) base base;
set_color green; fill_rect (base * i + 1) (base * j + 1) (base - 1) (base - 1);
set_color black; moveto (base * i + base / 3) (base * j + base / 3); draw_string (string_of_int t.(i).(j))
done;
done;
end
else
begin
set_color black; moveto base (base * 10); draw_string "PAS DE SOLUTION"
end;;


(*___________________________test____________________________*)

let grille = [|[|1; 0; 0; 0; 5; 4; 6; 7; 2|]; [|0; 0; 0; 0; 1; 0; 0; 9; 0|];
[|0; 0; 9; 8; 3; 0; 0; 5; 0|]; [|0; 0; 0; 1; 0; 0; 9; 4; 0|];
[|9; 2; 0; 7; 0; 5; 0; 1; 6|]; [|0; 1; 4; 0; 0; 8; 0; 0; 0|];
[|0; 7; 0; 0; 2; 3; 5; 0; 0|]; [|0; 3; 0; 0; 7; 0; 0; 0; 0|];
[|5; 9; 2; 6; 8; 0; 0; 0; 7|]|];;
sudo grille;;