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 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 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

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

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

Raw view Test code New version

More information

Link:	http://fssnip.net/7PT
Posted:	8 years ago
Author:	Tomas Petricek
Tags:	puzzle , queens