Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 = ()
- *)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement