2 people like it.

# Solving 8 queens problem with F#

Solve the 8 queens problem in F#, keeping available positions on the board as a list of X,Y coordinates.

 ``` 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: 42: 43: ``` ``````/// Generate all X,Y coordinates on the board /// (initially, all of them are available) let all = [ for x in 0 .. 7 do for y in 0 .. 7 do yield x, y ] /// Given available positions on the board, filter /// out those that are taken by a newly added queen /// at the position qx, qy let filterAvailable (qx, qy) available = available |> List.filter (fun (x, y) -> // horizontal & vertical x <> qx && y <> qy && // two diagonals (x-y) <> (qx-qy) && (7-x-y) <> (7-qx-qy)) /// Generate all solutions. Given already added queens /// and remaining available positions, we handle 3 cases: /// 1. we have 8 queens - yield their locations /// 2. we have no available places - nothing :( /// 3. we have available place let rec solve queens available = seq { match queens, available with | q, _ when List.length q = 8 -> yield queens | _, [] -> () | _, a::available -> // generate all solutions with queen at 'a' yield! solve (a::queens) (filterAvailable a available) // generate all solutions with nothing at 'a' yield! solve queens available } /// Nicely render the queen locations let render items = let arr = Array.init 8 (fun _ -> Array.create 8 " . ") for x, y in items do arr.[x].[y] <- " x " for a in arr do printfn "%s" (String.concat "" a) printfn "%s" (String.replicate 24 "-") // Print all solutions :-) solve [] all |> Seq.iter render ``````
val all : (int * int) list

Full name: Script.all

Generate all X,Y coordinates on the board
(initially, all of them are available)
val x : int
val y : int
val filterAvailable : qx:int * qy:int -> available:(int * int) list -> (int * int) list

Full name: Script.filterAvailable

Given available positions on the board, filter
out those that are taken by a newly added queen
at the position qx, qy
val qx : int
val qy : int
val available : (int * int) list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member GetSlice : startIndex:int option * endIndex:int option -> 'T list
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 filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val solve : queens:(int * int) list -> available:(int * int) list -> seq<(int * int) list>

Full name: Script.solve

and remaining available positions, we handle 3 cases:
1. we have 8 queens - yield their locations
2. we have no available places - nothing :(
3. we have available place
val queens : (int * int) list
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 q : (int * int) list
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val a : int * int
val render : items:seq<int * int> -> unit

Full name: Script.render

Nicely render the queen locations
val items : seq<int * int>
val arr : string [] []
module Array

from Microsoft.FSharp.Collections
val init : count:int -> initializer:(int -> 'T) -> 'T []

Full name: Microsoft.FSharp.Collections.Array.init
val create : count:int -> value:'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create
val a : string []
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

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

from Microsoft.FSharp.Core
val concat : sep:string -> strings:seq<string> -> string

Full name: Microsoft.FSharp.Core.String.concat
val replicate : count:int -> str:string -> string

Full name: Microsoft.FSharp.Core.String.replicate
module Seq

from Microsoft.FSharp.Collections
val iter : action:('T -> unit) -> source:seq<'T> -> unit

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