Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Juliet

By: a guest on Jan 1st, 2010  |  syntax: OCaml  |  size: 1.83 KB  |  views: 381  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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. *)