let solve next_f done_f initial =
let rec go state =
seq {
if done_f state then
yield state
else
for state' in next_f state do
yield! go state'
}
go initial
let n_queens n =
let all_rows = Set.ofList [1..n]
let next_f queens =
let column = List.length queens + 1
queens
|> List.fold (fun possible (row, col) ->
let distance = column - col
// Remove the current row, and diagonals from the
// possible set. The diagonals are just previous
// row +/- the column difference. This is safe here,
// because even if row - distance is negative, we are
// removing it from another set. No array access is
// involved.
Set.difference possible
(Set.ofList [row; row + distance;
row - distance])) all_rows
|> Set.map (fun (row) ->
(row, column)::queens)
let done_f queens =
List.length queens = n
solve next_f done_f []
printfn "number of 8 queens: %A" (Seq.length (n_queens 8))
printfn "number of 9 queens: %A" (Seq.length (n_queens 9))
printfn "number of 10 queens: %A" (Seq.length (n_queens 10))
printfn "A solution to 20 queens: %A" (Seq.head (n_queens 20))