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 Head : '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

Full name: Microsoft.FSharp.Collections.Seq.head

Raw view Test code New version

More information

Link:	http://fssnip.net/6n
Posted:	12 years ago
Author:	dave jones
Tags:	puzzle