8-Queens in 8 Lines

Brushing up on “whiteboard coding” for internal interviews… Inspired by Hal Ableson’s streams-based solution to this old classic in the SICP lectures, here’s a pretty concise n-Queens solution:

let rec Solutions n board size = seq { // board is (x,y) tuple list of queens 

    let safe board (x,y) = // is particular square safe on given board
        List.forall (fun (a,b) -> (x<>a)&&(y<>b)&&(abs(x-a)<>abs(y-b))) board
    let squares size = seq { // all squares on size x size board
        for y in [0..size-1] do for x in [0..size-1] do yield (x,y) }
    if n <= 0 then yield board else // no more queens to add, solved!
        for p in Seq.filter (safe board) (squares size) do
            yield! Solutions (n-1) (p::board) size } // add queen & recurse

// 8 queens, starting from empty 8x8 board, first 10 solutions
Solutions 8 [] 8 |> Seq.take 10 |> Seq.iter (printfn "Solution: %A")

Comments

• Anonymous
  October 06, 2010
  The comment has been removed