type Position = { r : int; c : int }
let safe a b =
match a, b with
| { r = r1; c = c1 }, { r = r2; c = c2 } when
r1 = r2 ||
c1 = c2 ||
abs((float c1 - float c2) / (float r1 - float r2)) = 1.0 -> false
| _, _ -> true
let queens size =
let rec loop positions positionCount availableCols row =
let totallySafe x = Seq.forall (fun y -> safe x y) positions
if positionCount = size then Some positions
else
seq { for col in availableCols do yield { r = row; c = col } }
|> Seq.tryPick (fun testPosition ->
match totallySafe testPosition with
| true -> loop (testPosition::positions) (positionCount + 1) (Set.remove testPosition.c availableCols) (row + 1)
| false -> None
)
loop [] 0 (set [1..size]) 1
let test n =
let s = System.Diagnostics.Stopwatch.StartNew()
let items = queens n
s.Stop()
match items with
| Some(items) ->items |> Seq.iter (fun x -> printf "(%i, %i), " x.r x.c)
| None -> printfn "No solutions"
printfn "\nTotal time: %fms" s.Elapsed.TotalMilliseconds
(*
Here are my machine's specs:
- 4 GB memory
- 3.2ghz quad core, AMD Phenom II x4
- Windows Vista 32 bit
> test 8;;
(8, 4), (7, 2), (6, 7), (5, 3), (4, 6), (3, 8), (2, 5), (1, 1),
Total time: 4.638500ms
val it : unit = ()
> test 13;;
(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),
Total time: 3.650500ms
val it : unit = ()
> test 20;;
(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),
Total time: 1765.944600ms
val it : unit = ()
*)