

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


 
let rec iterate f value = seq { 
    yield value
    yield! iterate f (f value) }
 
let up i = i + 1
let right i = i
let down i = i - 1
 
let noCollisionGivenDir solution number dir =
    Seq.forall2 (<>) solution (Seq.skip 1 (iterate dir number))
 
let goodAddition solution number =
    List.forall (noCollisionGivenDir solution number) [ up; right; down ]
 
let rec extendSolution n ps =
    [0..n - 1]
    |> List.filter (goodAddition ps)
    |> List.map (fun num -> num :: ps)
 
let allSolutions n =
    iterate (List.collect (extendSolution n)) [[]]
 
// Print one solution for the 8x8 case
let printOneSolution () =
    allSolutions 8
    |> Seq.item 8
    |> Seq.head
    |> List.iter (fun rowIndex ->
        printf "|"
        [0..8] |> List.iter (fun i -> printf (if i = rowIndex then "X|" else " |"))
        printfn "")
 
// Print number of solution for the other cases
let printNumberOfSolutions () =
    printfn "Size\tNr of solutions"
    [1..11]
    |> List.map ((fun i -> Seq.item i (allSolutions i)) >> List.length)
    |> List.iteri (fun i cnt -> printfn "%d\t%d" (i+1) cnt)
 
printOneSolution()
 
printNumberOfSolutions()
 