The Eight Queens problem

Posted on Updated on

My colleague recently introduced me to the eight queens problem (you can read more about it over at Wikipedia). In summary, you have to be able to place eight queens down on a chess board without any of them attacking any other.

This sounds easy at first, but I found that taking a few guesses on a piece of paper yielded no results. Rather than simply solving the problem, I decided it would be more fun to write a program that would find all the solutions for me. I’d been looking for a nice little programming problem to teach myself F# for a while, so I thought I’d give this a go. Well, after a few false starts and a lot of F# Googling, here’s my solution:

open System
open System.Linq
open Microsoft.FSharp.Collections

type Square = Queen | Empty
    
type Board( squares: Square[,] ) =
    let boardSize = (int << sqrt << float) squares.Length
    
    member this.BoardSize = boardSize
    
    member this.Item
      with get(x, y) = squares.[x, y]
      and set(x, y) value = squares.[x, y] <- value
    
    override this.ToString() =
        [for i in (this.BoardSize - 1).. -1 ..0 do
            for j in 0..(this.BoardSize - 1) do
                yield match squares.[i, j] with 
                      | Square.Queen -> " X "
                      | _ -> " □ "
            yield Environment.NewLine]
        |> System.String.Concat

    new( boardSize : int ) =
        Board( Array2D.createBased 0 0 boardSize boardSize Square.Empty )

    member this.Copy() =
        Board( Array2D.copy squares )

let beingAttacked (x :int, y :int) (board : Board) : bool =
    let c = (y - x)
        
    [for i in 0..(board.BoardSize - 1) do
        yield board.[x, i]
        yield board.[i, y]
        if i + x < board.BoardSize && i + y < board.BoardSize then
            yield board.[x + i, y + i]
        if x - i >= 0              && y - i >= 0              then
            yield board.[x - i, y - i]
        if x + i < board.BoardSize && y - i >= 0              then 
            yield board.[x + i, y - i]
        if x - i >= 0              && i + y < board.BoardSize then 
            yield board.[x - i, y + i]]
        |> Seq.exists( fun sq -> sq = Square.Queen)

let rec placeQueen rowNum (board : Board) : Board list =
    if rowNum = board.BoardSize then
        [board]
    else
        let possibleMoves = 
            [0..(board.BoardSize - 1)]
            |> Seq.filter( fun colNum -> not (beingAttacked(rowNum, colNum) board) )
        
        [for nextMove in possibleMoves do
            let nextBoard = board.Copy()
            nextBoard.[rowNum, nextMove] <- Square.Queen
            
            yield! placeQueen (rowNum + 1) nextBoard]
            
let board = new Board(8)

let solutions = placeQueen 0 board

printfn "Found %i solutions" (solutions.Count())

for solution in solutions do
    printfn "%A" solution

It’s not a wonderfully elegant solution, but it works. Here’s one of the solutions it generated:

 □  □  □  ■  □  □  □  □ 
 □  ■  □  □  □  □  □  □ 
 □  □  □  □  □  □  ■  □ 
 □  □  ■  □  □  □  □  □ 
 □  □  □  □  □  ■  □  □ 
 □  □  □  □  □  □  □  ■ 
 □  □  □  □  ■  □  □  □ 
 ■  □  □  □  □  □  □  □

I made a type that represents a square (an enum with two members: ‘queen’ and ’empty’); a type that represents the board (containing a 2D array of ‘Squares’); one function that, given a board and the coordinates of a square will tell you whether that square is under attack or not; and lastly a function that will take an empty board and place the queens on it. One of the cool things about this solution is it will work for any size board (for an n x n board it assumes you are placing n queens). Here’s an example on a 4 x 4 board:

Found 2 solutions
 □  □  ■  □ 
 ■  □  □  □ 
 □  □  □  ■ 
 □  ■  □  □ 

 □  ■  □  □ 
 □  □  □  ■ 
 ■  □  □  □ 
 □  □  ■  □ 

I learned a lot about F# along the way. I learned that I really like:

Significant whitespace
This just seems sensible to me. I already had some experience with Coffeescript and a little Python, so it wasn’t much of a learning curve for me, but this is probably more complex code that I’ve written here than in either of those other languages.
Type inference
I guess it’s one of F#’s headline features, but the sheer power of the type inference is mind-blowing sometimes. Being able to write a method and not have to give the types of its parameters even: that’s pretty cool. F# can infer types from usage as well as declaration.
Lists and list expressions
The way F# handles lists and loop-and-yield expressions is a joy to work with. It reminds me of when Microsoft first released Linq and the way I was so impressed.
Piping
All languages should have piping. Period.

Things I’m not so sure on:

Syntax
Although F# has some pretty cool syntax, it’s got some idiosyncrasies that I find a little unfathomable. Example: methods need a self-identifier. Why? What’s wrong with having “this” as a language keyword?
Having to pipe things to “ignore”
This isn’t technically necessary, except I was writing this program in LinqPad, which seems to have “treat warnings as errors” turned on, and therefore wouldn’t compile my program unless I piped unused return values to ignore
Lack of a traditional “return”
This I’m sure is something that is entirely deliberate, as halting execution of your method somewhere in the middle isn’t very functional. It just caught me out a few times (as I’m still learning) and I had to go back and rewrite my function in a different way. A better way, really. This is just something that I need to get used to.

Let me know if you have any suggestions for a problem to give back to my colleague (preferably of similar difficulty), as he’s trying to learn F# too. How could you improve on my solution?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s