Sudoku(9x9).ml

let sudoArray =
  [|
    0;0;0; 0;0;8; 0;0;0;
    2;0;0; 0;5;9; 0;0;0;
    1;0;0; 0;0;0; 2;5;0;

    0;0;8; 0;0;1; 4;6;0;
    3;0;0; 0;0;0; 1;0;0;
    9;0;4; 0;8;3; 0;0;0;

    0;0;0; 5;0;0; 0;8;4;
    0;0;0; 0;0;4; 9;0;0;
    0;2;3; 0;0;0; 0;0;0
  |]

let solution = ref 1

let sudokuRowSize = 9
let sudokuBoxSize = 3

(*
1 => 1, 2
2 => -1, 1
0 => -2, -1
*)

let buildEdgeBox r c acc =
  let rm = r mod sudokuBoxSize in
  let cm = c mod sudokuBoxSize in
  let rl = if rm = 1 then [1; 2] else if rm = 2 then [-1; 1] else [-2; -1] in
  let cl = if cm = 1 then [1; 2] else if cm = 2 then [-1; 1] else [-2; -1] in
  List.fold_left (fun a d -> List.fold_left (fun ai di ->((r + d), (c + di)):: ai) a cl) acc rl

let rec buildEdgesRow r c cnt acc =
  match cnt with
  | 0 -> acc
  | x when c = x -> buildEdgesRow r c (cnt - 1) acc
  | x -> buildEdgesRow r c (cnt - 1) ((r, x)::acc)

let rec buildEdgesCol r c cnt acc =
  match cnt with
  | 0 -> acc
  | x when r = x -> buildEdgesCol r c (cnt - 1) acc
  | x -> buildEdgesCol r c (cnt - 1) ((x, c)::acc)

let lst =
  List.fold_left
    (
      fun a d ->
        let r = (d/sudokuRowSize + 1) in
        let c = ((d mod sudokuRowSize) + 1) in
        let v = Array.get sudoArray d in
        let lst = if v != 0
          then
            []
            else
          (buildEdgeBox r c
             (buildEdgesCol r c sudokuRowSize
                (buildEdgesRow r c sudokuRowSize []))) in
        let slst = if v !=0
          then
            []
            else
          List.fold_left
            (
              fun a (r, c) ->
                let ans = (Array.get sudoArray (((r - 1) * sudokuRowSize) + (c - 1))) in
                if ans = 0
                then
                  a
                else
                (List.filter (fun x -> ans != x) a)
            )
            [1;2;3;4;5;6;7;8;9;] lst in
        (
          d,
          v,
          (r, c),
          lst,
          slst
        )::a
    )
    []
    (List.init 81 (fun x -> x))

let rec solveIt lst =
  match lst with
  | [] ->
    (
      Printf.printf "Solution: %d\n" (!solution);
      solution := (!solution) + 1;
      Array.iter (fun x -> Printf.printf "%d\n" x) sudoArray
    )
  | (p, 0, (r, c), e, s)::tl ->
    List.iter
      (
        fun x ->
          if (List.exists
                (fun (r, c) ->
                   (x = (Array.get sudoArray (((r - 1) * sudokuRowSize) + (c - 1))))) e
             )
          then
            ()
          else
            (
              (Array.set sudoArray p x);
              solveIt tl;
              (Array.set sudoArray p 0)
            )
      ) s
  | (p, v, (r, c), e, s)::tl ->
    (Array.set sudoArray p v);
    solveIt tl;
    (Array.set sudoArray p 0)

let () = solveIt lst