Skip to content

Instantly share code, notes, and snippets.

@motylwg
Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save motylwg/7701d56ded0582449d4d to your computer and use it in GitHub Desktop.
Save motylwg/7701d56ded0582449d4d to your computer and use it in GitHub Desktop.
N Queens in F#
type position = int * int
type board = position list
let queens n =
let isNotAttack (p1 : position) (p2 : position) =
fst p1 <> fst p2 && snd p1 <> snd p2 && abs (fst p1 - fst p2) <> abs (snd p1 - snd p2)
let isSafe (b : board) =
match b with
| [] -> true
| h :: tail -> List.forall (isNotAttack h) tail
let addQueen n (bs : board list) : board list =
[for b in bs do yield! [for col in 0 .. (n-1) do yield (b.Length, col) :: b]]
|> List.filter isSafe
List.fold (fun acc _ -> addQueen n acc) [[]] [0 .. (n-1)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment