Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# Juliet

By: a guest on Jan 1st, 2010  |  syntax: OCaml  |  size: 1.83 KB  |  views: 407  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. type Position = { r : int; c : int }
2.
3. let safe a b =
4.     match a, b with
5.     | { r = r1; c = c1 }, { r = r2; c = c2 } when
6.             r1 = r2 ||
7.             c1 = c2 ||
8.             abs((float c1 - float c2) / (float r1 - float r2)) = 1.0 -> false
9.     | _, _ -> true
10.
11. let queens size =
12.     let rec loop positions positionCount availableCols row =
13.         let totallySafe x = Seq.forall (fun y -> safe x y) positions
14.
15.         if positionCount = size then Some positions
16.         else
17.             seq { for col in availableCols do yield { r = row; c = col } }
18.             |> Seq.tryPick (fun testPosition ->
19.                     match totallySafe testPosition with
20.                     | true -> loop (testPosition::positions) (positionCount + 1) (Set.remove testPosition.c availableCols) (row + 1)
21.                     | false -> None
22.                 )
23.     loop [] 0 (set [1..size]) 1
24.
25. let test n =
26.     let s = System.Diagnostics.Stopwatch.StartNew()
27.     let items = queens n
28.     s.Stop()
29.
30.     match items with
31.     | Some(items) ->items |> Seq.iter (fun x -> printf "(%i, %i), " x.r x.c)
32.     | None -> printfn "No solutions"
33.
34.     printfn "\nTotal time: %fms" s.Elapsed.TotalMilliseconds
35.
36. (*
37. Here are my machine's specs:
38. - 4 GB memory
39. - 3.2ghz quad core, AMD Phenom II x4
40. - Windows Vista 32 bit
41.
42.
43. > test 8;;
44. (8, 4), (7, 2), (6, 7), (5, 3), (4, 6), (3, 8), (2, 5), (1, 1),
45. Total time: 4.638500ms
46. val it : unit = ()
47.
48. > test 13;;
49. (13, 7), (12, 11), (11, 8), (10, 6), (9, 4), (8, 13), (7, 10), (6, 12), (5, 9), (4, 2), (3, 5), (2, 3), (1, 1),
50. Total time: 3.650500ms
51. val it : unit = ()
52.
53. > test 20;;
54. (20, 11), (19, 6), (18, 14), (17, 7), (16, 10), (15, 8), (14, 19), (13, 16), (12, 9), (11, 17), (10, 20), (9, 18), (8, 12), (7, 15), (6, 13), (5, 4), (4, 2), (3, 5), (2, 3), (1, 1),
55. Total time: 1765.944600ms
56. val it : unit = ()
57. *)
clone this paste RAW Paste Data
Top