Programming Interview Question: Eight Queens

One more reason why this is terrible question: many people solved it in the past as part of a programming course, many didn't. If you want to test which school they went to you can look at the resume. If you want to see how they handle writing solvers for simple games/puzzles under pressure of the interview come up with one that is guaranteed (or almost) to be new for the interviewee.

> 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

It can actually be done fairly quickly if you really only ask for 8x8 instead of a general NxN solver, and the person realizes one key thing: computers have gotten ridiculously fast, so that if you just bang out the first dumb thing that comes to mind, you can probably be done and have the answers before the people with the clever, general, efficient solutions get their solutions coded or even designed.

For instance, this brute force, ridiculously ugly, un-clever, only-works-for-8x8 solution took about 5 minutes or so to write, with half that spent deciding how to number the diagonals and looking at a couple of squares on a chessboard to see how rank/file maps to my diagonal numbering:

   #include <stdio.h>

   int main(void)
   {
       unsigned long pos;

       for (pos = 0; pos <= 077777777; ++pos)
       {
           unsigned long tmppos = pos;
           unsigned long taken = 0;
           int rank;
           int file;

           for (file = 0; file < 8; ++file)
           {
               unsigned long mask;

               rank = tmppos & 07;

               mask = (1L << file) |       /* file */
                       (1L << (rank + 8)) |    /* rank */
                       (1L << (23 + file - rank))  /* diagonal */
                       | (1L << (45 - file - rank)); /* other diagonal */
               if (taken & mask)
                   goto fail;
               taken |= mask;
               tmppos >>= 3;
           }
           printf("%lo\n", pos);
   fail:   ;
       }
       return 0;
   }

It takes under 0.5 seconds on my 2009 Mac Pro when compiled without optimization, and about half that with optimization.

(To be completely honest, I rarely write C nowadays, so although it only took a few minutes to write, the damn thing took half an hour to debug. I wrote "1 <<" instead of "1L <<" because I thought for some reason that int was 64 bit nowadays).

Never had a job where programming chess boards was a requirement. So unless you have one don't ask this. It's not a programming question it's a puzzle.

I did this in about 20 minutes in Python in an interview.

The trick to solving things fast is to use the structure of the problem to make your problem solving procedure less general. That is, you do premature optimization, except instead of trading readability for runtime speed, your are trading readability for program length.

With real problems, there is a similar tradeoff, so I think this is a useful skill to demonstrate. But it does take practice to find the tradeoff that works best for interview questions, which is not the same as for real life coding.

In my solution, I use mutable state to reduce the amount of code. board is mutated to avoid the boilerplate of copying objects. valid is mutated as a kind of optimization, but the real reason is it makes the program simpler.

  def complete_board(board, l):
    """If possible, completes a board (whose first l rows
    have been filled with 1 queen per row).  Returns
    true if this is possible, false otherwise

    board is a list of ints representing the position
    (0-based) of each queen"""

    N = len(board)

    if l == N:
      return True

    # determine the valid positions for a queen in the r'th row
    valid = [True] * N
    for row, col in enumerate(board[:l]):
      valid[col] = False
      s = l - row
      if col + s < N:
        valid[col + s] = False
      if col - s >= 0:
        valid[col - s] = False

    for col, v in enumerate(valid):
      if v:
        board[l] = col
        if complete_board(board, l + 1):
          return True
    return False

This question seems totally unreasonable for the length of any technical interview I have taken or conducted. Most interviews run under an hour and focus on multiple topics. Its rare you can focus on one question more than 10 minutes. The rule of thumb I use is that if I'm picking a question as an interviewer, I make sure I can answer that question in 1/3 the time I plan to give to the candidate. Given the pressure that they are under, I expect to owe that that much.

I don't think it would be too difficult to find a candidate who could at least talk through or whiteboard out an imperative solution to this. If a candidate couldn't come up with at least an outline of a solution, I probably wouldn't want to hire them.

This particular problem lends itself really well to functional or constraint logic solutions, though (e.g. http://www.cs.nott.ac.uk/~rxq/files/8nQueenModel.pdf) -- I'd give bonus points to a candidate who could identify that this problem is well suited to one of those toolsets instead of immediately whipping out ruby, python, or js.

> 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.

This is a great point that I realized that when I sat down to write up a solution myself. The video-explanation-version of coding it up for the CFI course ended up being 60 minutes long.

Suspect when it does get asked in an interview context they might only want to see some of your problem solving process and algorithm devising, not a full code-up.

This programming problem was what actually got me interested in compilers in the first place.

When I was 16 and learning how to program in Java, there was an online competition for high schoolers, and this was one of the introductory programming questions. Your program had to execute in under a time limit (5 seconds, N=13), and I had come up with the best solution I could and was still at 7 seconds. It took me the rest of the month spending hours a day reading on speed optimizations in order to cut down every unnecessary instruction, and remove every intermediate variable. Eventually, the program executed in 4.9 seconds.

While quite interesting, the problem only took an afternoon to implement the algorithm. What differentiated my chops from my competitors was that I could improve my program beyond the first implementation.

it is sort of confusing... do you really consider it a hard problem? I am first year maths student at Uni Warsaw and we literally had this problem in the first month, and solution was found by most people in just a few minutes. It sometimes amazes me how people here at HN find some hard for me problems easy and vice versa

> 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).

I got it on my second try, though maybe I just got lucky.

Back in grad school, I took a configurable computing course where we were to solve the N-Queens problem on an FPGA. My short write-ups are here: http://people.cs.vt.edu/~scschnei/ece5530/

This was a computer engineering course, and I was a computer science student with no background in Verilog or VHDL. I think it took me about 30 hours to get a working solution. However, my solution is very limited, and shows how unfamiliar I was with thinking in hardware terms; other students in the course produced solutions which did not have my limitations, and they did it with much less effort. When I mentioned that to another student in the course, he looked surprised. When I mentioned I was a CS student with no prior experience with FPGAs, Verilog or VHDL, he said, oh, that's pretty good!

Here is a solution I wrote when I was an undergrad TA that uses only bit arrays and can check for a valid solution using bitwise logic operations. That said what a horrible interview question. The hard part about the problem is figuring out how to convert a x/y position on the board to a diagonal dx/dy coordinate. Once you figure that out the coding is simple but I remember it taking me a day of mulling over in the back of my head before the solution came to me in my sleep.

http://therandombit.blogspot.com/2008/09/n-queens-implmented...

Everyone seems to forget that there are explicit solutions for the N queens problem.

http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_so...

If I got that question, I'd probably spend most of my time worrying about whether or not I should count solutions that are rotations/reflections of other solutions as unique.

A quick solution involves starting at a corner, and placing each queen one horizontal and two vertical (a constrained knight's move, basically) away from the previous one. This works for an 8x8 board, but does not generalize to an NxN board (it is easy to see that this won't work when N is divisible by 3). Determining which N's it exactly works for is a math, not a programming puzzle, however. :)

If I took this as a "Question to prepare yourself for an interview" and not a "Question you might be asked during an interview" I think it's great.

As prep it's a concise problem you can do on your own time to get your brain working over basic things that you may not have been thinking about lately.

As a question to actually give someone (or receive) during an interview? Seems way to long.

This just boils down to populating an 8 element array with all the numbers from 0 - 7, where abs(x[n] - x[m] != abs(n - m))

I really don't understand writing a program to solve this problem. Granted I play chess casually but I had a solution before I even finished reading the problem.

I think it's an interesting puzzle, but I don't think that makes it a good interview question.

I love the Haskell version of this because non-deterministic computation via (depth-first) search is embodied by the list monad!

The preliminaries are that we represent a board position containing N queens on an NxN board by a list of row positions in each of N columns.

    newtype Board = Board [Int] deriving ( Eq, Show )
    emptySolution = Board []

Then, given any particular NxN board with M queens in first M columns that is a solution to M-queens, we can generate the list of possible new boards with (M+1) queens. We try all possible row positions for the new column excepting the rows where queens already exist.

    attempts :: Int -> Board -> [Board]
    attempts n (Board queens) = 
      map (\r -> Board (r : queens)) ([0 .. n - 1] \\ queens)

And we prune out the ones where the new queen has a diagonal conflict.

    valid :: Board -> Bool
    valid (Board []) = True
    valid (Board (q:cols)) = 
      and $ map (\(n, c) -> abs (q - c) /= n) (zip [1..] cols)

      -- this is a bit clever, as we walk back through
      -- the previous columns, if the absolute difference
      -- between the row position of the new queen and
      -- an old queen is ever the count of the column 
      -- we're in, then it must be in a diagonal line
      -- from the new queen

All of the above is pretty standard, but the fun part is using the list monad to structure a search. Each bind (<-) in do-notation can be thought of as non-deterministically setting a particular choice from the right side to the name on the left

    queens :: Int -> [Board]
    queens n = search n [emptySolution] where
      search 0 boards = boards -- no more queens to add
      search k boards = do
        board <- search (k - 1) boards -- find a smaller solution
        filter valid (attempts board)  -- try all possible extensions,
                                       -- remove the bad ones

    >>> length (queens 8)
    92

Finally, the pattern of `search` is really common, it's just iterating the generation of attempted solutions. We can write it with the built-in function `Control.Monad.foldM` or another common utility combinator, `iterateM`

    iterateM :: Monad m => (a -> m a) -> a -> [m a]
    iterateM f x = iterate (f =<<) (return x)

    queens n = iterateM (filter valid . attempts n) emptySolution !! n

Finally, it's worth noting that there's nothing special about the list monad's implementation. It's easy to rewrite it without using the typeclass.

    -- this is the list monad definition
    instance Monad [] where
      return a = [a]
      xs >>= f = concat (map f xs)

    iterateList :: (a -> [a]) -> a -> [[a]]
    iterateList f x = iterate (concat . map f) [x]

I am very interested in finding out Emily's approach on this.

haskell solution:

import Control.Monad

queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n] safe x [] n = True safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]

main = mapM_ print $ queens 8

---- http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscel...

I could solve it AND write it in a readable fashion. Your code is unreadable, you'd fail my test.

What the actual fuck ((if b[r]?[c] then c else -1) for c in [0..n-1]).filter (c) -> c >= 0

I am aware of what the line is doing, I just have no idea what b & c are. Best guess; Board & Column.

My brother had created fastest solution ( both in time and space complexity ) for this problem.