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