DEC 1, 2013

# Programming Interview Question: Eight Queens

This week's Coding for Interviews question is the Eight Queens Puzzle, where the challenge is to find all the ways to place 8 queens on an 8x8 chess board, such that none of them are in a position to kill each other in the next move. You can see how tricky this can be if you try to do it by hand (unless you're Emilie, who found a solution in just a few minutes).

Here's my CoffeeScript solution. It's a depth-first search of board states (placing a queen in the next available position in the next unoccupied row for each new state), and it returns an array of "solutions". Each solution is an array of indices representing the column in each row where a queen is to be placed (so `[1, 3]` represents queens at `(row 0, column 1)` and `(row 1, column 3)`):

``````getPlacements = (n) ->
fill = (b, r, c) ->
valid = (row, col) -> 0 <= row < n and 0 <= col < n
newBoard = (row[..] for row in b)
newBoard[r] = (no for _ in [0..n-1])
row[c] = no for row in newBoard
for i in [0..n-1]
newBoard[r+i][c+i] = no if valid r+i, c+i
newBoard[r-i][c+i] = no if valid r-i, c+i
newBoard[r+i][c-i] = no if valid r+i, c-i
newBoard[r-i][c-i] = no if valid r-i, c-i
newBoard

openPositions = (b, r) ->
((if b[r]?[c] then c else -1) for c in [0..n-1]).filter (c) -> c >= 0

result = []
queue = [[[], ((yes for _ in [0..n-1]) for _ in [0..n-1])]]

while queue.length
[placement, board] = queue.pop()
result.push placement if placement.length is n
for c in openPositions(board, placement.length).reverse()
newPlacement = placement[..]
newPlacement.push c
queue.push [newPlacement, fill(board, placement.length, c)]
result
``````

Just like last time, I spent a few hours refining my answer, so it's probably a lot more polished and succinct than one I'd come up with in an interview environment. The basic strategy is the same either way, though: explore all of the possible "next moves" until you hit a point where there are no safe places for the next queen or you've placed all N queens.

I also wrote a handy little printing function for calculating the solutions to an NxN board with N queens and printing them to a console in a readable format:

``````printPlacements = (n) ->
placements = getPlacements n
console.log ((((if p?[r] == c then 'X' else '-') \
for c in [0..n-1]).join '' \
for r in [0..n-1]).join '\n' \
for p in placements).join '\n\n'
console.log "\nFound #{placements.length} solutions"
``````

The (snipped) output looks something like this:

``````...

-------X
--X-----
X-------
-----X--
-X------
----X---
------X-
---X----

-------X
---X----
X-------
--X-----
-----X--
-X------
------X-
----X---

Found 92 solutions
``````

And finally, a visualization of what the search actually looks like (slowed down about 10,000 times):

I do have to say that as someone who sometimes conducts technical interviews, I'm not sure I would actually give this question to an interviewee, unless I was leaving him or her alone to work for a couple of hours, because of how long it would probably take to reach an answer.

Doing the problem on a whiteboard would definitely help, because it would remove all of the tedious debugging, but even then the only candidates who would finish in a reasonable amount of time would be the ones who were already familiar with searching algorithms. That said, it's definitely a fun puzzle to solve, it would make a great homework problem in an algorithms class, and I had a lot of fun solving it myself.

Cheers!