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 8×8 board, first 10 solutions
Solutions 8 [] 8 |> Seq.take 10 |> Seq.iter (printfn “Solution: %A”)

Comments (1)

  1. AshleyF says:

    Holy smokes! I was peeking at other solutions and stumbled onto this 4-line solution in Miranda!

    queens 0 = [[]]

    queens (n+1) = [q:b | b <- queens n; q <- [0..7]; safe q b]

    safe q b = and [ ~checks q b i | i <- [0..#b-1] ]

    checks q b i = q = b!i / abs (q – b!i) = i+1

    Taken from this paper BTW: http://www.cs.kent.ac.uk/…/overview.pdf