The Eight Queens problem
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?
Richiban 