4 people like it.

# N-Queens

Code to solve the N-Queens problem.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: ``` ``````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)) ``````
val solve : next_f:('a -> #seq<'a>) -> done_f:('a -> bool) -> initial:'a -> seq<'a>

Full name: Script.solve
val next_f : ('a -> #seq<'a>)
val done_f : ('a -> bool)
val initial : 'a
val go : ('a -> seq<'a>)
val state : 'a
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val state' : 'a
val n_queens : n:int -> seq<(int * int) list>

Full name: Script.n_queens
val n : int
val all_rows : Set<int>
Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
interface IComparable
interface IEnumerable
interface IEnumerable<'T>
interface ICollection<'T>
new : elements:seq<'T> -> Set<'T>
member Add : value:'T -> Set<'T>
member Contains : value:'T -> bool
override Equals : obj -> bool
member IsProperSubsetOf : otherSet:Set<'T> -> bool
member IsProperSupersetOf : otherSet:Set<'T> -> bool
...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>
val ofList : elements:'T list -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.ofList
val next_f : ((int * int) list -> Set<(int * int) list>)
val queens : (int * int) list
val column : int
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold
val possible : Set<int>
val row : int
val col : int
val distance : int
val difference : set1:Set<'T> -> set2:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.difference
val map : mapping:('T -> 'U) -> set:Set<'T> -> Set<'U> (requires comparison and comparison)

Full name: Microsoft.FSharp.Collections.Set.map
val done_f : ('a list -> bool)
val queens : 'a list
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
module Seq

from Microsoft.FSharp.Collections
val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length
val head : source:seq<'T> -> 'T