Commits

hogekura  committed 5fb64a2

sudokuを追加

  • Participants
  • Parent commits 225d803

Comments (0)

Files changed (2)

 BYTE_ENABLED = true
-NATIVE_ENABLED = false
+NATIVE_ENABLED = true 
 USE_OCAMLFIND = true
 
 .SUBDIRS: src

File src/problems.ml

      sub2 >>= fun s2 ->
      [Node ('x', s2, s1); Node ('x', s1, s2)])
 ;;
+
+(* sudoku solver *)
+let try_fill board ~x ~y ~n f = begin
+  board.(y).(x) <- n;
+  f ();
+  board.(y).(x) <- 0;
+end
+;;
+
+let solved board =
+  Array.for_all board ~f:(fun row ->
+    Array.for_all row ~f:(fun x -> x <> 0))
+;;
+
+
+let print_board board =
+  Array.iter board ~f:(fun row ->
+    Array.iter row ~f:(fun x -> Printf.printf "%d " x);
+    print_string "\n")
+;;
+
+let fill board ~x ~y =
+  let size = Array.length board in
+  let res = ref [] in
+  if board.(y).(x) = 0 then begin
+    for n = 1 to size do
+      let ok = ref true in
+      begin
+        try
+          for x = 0 to size - 1 do
+            if board.(y).(x) = n then raise Exit
+          done;
+          for y = 0 to size - 1 do
+            if board.(y).(x) = n then raise Exit
+          done;
+          let area_x, area_y = x / 3, y / 3 in
+          for x = 0 to 2 do
+            for y = 0 to 2 do
+              if board.(area_y * 3 + y).(area_x * 3 + x) = n then raise Exit
+            done
+          done;
+        with
+        | Exit -> ok := false;
+      end;
+      if !ok then res := n :: !res
+    done;
+  end;
+  !res
+;;
+
+let n = ref 0;;
+let print board  =
+  incr n;
+  if !n mod 10000 = 0 then (print_board board; print_string "\n"; flush stdout)
+;;
+
+let rec sudoku board =
+  print board;
+  let size = Array.length board in
+  if solved board then
+    raise Exit
+  else begin
+    let answers = ref [] in
+    for y = 0 to (size - 1) do
+      for x = 0 to (size - 1) do
+        let nums = fill board ~x ~y in
+        if nums <> [] then (answers := (x, y, nums) :: !answers)
+      done
+    done;
+    List.sort ~cmp:(fun (_, _, x) (_, _, y) -> compare (List.length x) (List.length y)) !answers |>
+        List.iter ~f:(fun (x, y, nums) -> List.iter nums ~f:(fun n ->
+          try_fill board ~x ~y ~n (fun () -> sudoku board)))
+  end
+;;
+
+let board =
+    [|
+      [|0; 0; 4;  8; 0; 0;  0; 1; 7|];
+      [|6; 7; 0;  9; 0; 0;  0; 0; 0|];
+      [|5; 0; 8;  0; 3; 0;  0; 0; 4|];
+
+      [|3; 0; 0;  7; 4; 0;  1; 0; 0|];
+      [|0; 6; 9;  0; 0; 0;  7; 8; 0|];
+      [|0; 0; 1;  0; 6; 9;  0; 0; 5|];
+
+      [|1; 0; 0;  0; 8; 0;  3; 0; 6|];
+      [|0; 0; 0;  0; 0; 6;  0; 9; 1|];
+      [|2; 4; 0;  0; 0; 1;  5; 0; 0|];
+    |] ;;
+
+let get_board () =
+  let board = Array.make_matrix ~dimx:9 ~dimy:9 0 in
+  for i = 0 to 8 do
+    for j = 0 to 8 do
+      Scanf.scanf "%d " (fun x -> board.(i).(j) <- x)
+    done
+  done;
+  board
+;;
+
+let test board =
+  let newboard = Array.map board ~f:(fun row -> Array.copy row) in
+  try
+    sudoku newboard;
+    print_endline "not solved"
+  with
+  | _ -> print_board newboard
+;;
+
+let () = test (get_board ()) ;;