9 ms·

Programming Interview Question: Eight Queens

54 points by bcjordan 13y ago

bcjordan 13y ago
> 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.
nilkn 13y ago
> 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.
- Codhisattva 13y ago
  Not lucky - the answer is inferable. Exhaustive search is just the primitive way.
  - VintageCool 13y ago
    Just place them like knights!
JSno 13y ago
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/Miscellaneous/N-Queens http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscel...
- thirsteh 13y ago
  Your indentation broke: 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
  - JoeAltmaier 13y ago
    Hm. And maybe that's why Haskell isn't catching on. That looks little better than terminal scripting languages. Its concise, sure. But maybe that's not as helpful as you might think, in communicating a problem solution.
    - thirsteh 13y ago
      Haskell is catching on. It's extremely popular in academia, and it's growing on e.g. Github: http://ec2-54-224-80-201.compute-1.amazonaws.com:8888/languages_visualization/71c6f3773a3cbe2aa440949bc906bd4d/index.html http://ec2-54-224-80-201.compute-1.amazonaws.com:8888/langua... But you're right, examples like this are extremely poor marketing for Haskell. It's really not how you'd write most Haskell programs. A lot of the Haskell code on sites like Rosetta Code is deliberately terse to show off. I changed the indentation a little bit, to make it more clear: 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 'queens' is essentially a for loop that concatenates the elements between 1..n that are safe, and 'safe' is a function that returns true if it's given an empty list, or if the input satisfies all of the predicates in the other list (notice the recursion that's possible because of laziness.) The function 'and' that it calls takes a list of bools and returns true if all of them are true. 'main' prints each list that results from running 'queens 8' There is some syntax and convention you have to learn, e.g. what the _ in mapM_ means, what a list comprehension is, or what : means, etc. but once you have it's a fairly elegant solution (compare to the code snippets from imperative languages.)
- 13y ago
zackbrown 13y ago
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 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.
- bluecalm 13y ago
  I'd give bonus points for pointing out some implementation decisions: -when searching is it better to use copy-make or move/undo approach ? (copy make is faster on modern pc's, at least for things like 8Q's, it's also much easier to implement as you don't need any code for undoing moves) -what is the best way to check if given move (placing the queen) is valid ? (you need three 0-1 arrays for rows and diagonals in both direction this a neat trick, very difficult to come up with but which speeds the whole thing immensely) -how do you break out of the recursion if the task is changed to find one solution ? I know all those things because I am a hobbyist who wrote a lot of solvers and dabbled into chess programming. I am probably in top 0.1% of people if I get question like this. I am incompetent when it comes to things needed in most commercial applications as I've never worked on big commercial projects. This question filters for people like me. I can't imagine how this a good thing for anything practical (unless the task is to produce the best chess program or something).
  - kenjackson 13y ago
    What is copy/make vs move/undo? I'm not familiar with that terminology...
    - bluecalm 13y ago
      When you search you have a choice of: 1)having only one board and make/undo moves on it. So every time you put a new queen on the board you add it to the representation of the board and every time you go back in recursion you need to do an undo before exiting the function (so you new branch won't have queens placed on the board from previous branch) 2)storing as many boards as many steps deep in the recursion you are (max 8 in 8 queens problem) so every time you go deeper into recursion you create new board then you copy current state there and then you make a move (place a queen) on this new board; this way when you go back in recursion you do nothing as this new board is taken care of by stack pointer going back. The cost of copy make is memory (you need memory for new board representation for every step deeper into recursion) but it's usually not much of a problem. The benefit is that you don't need to code undo logic (which in case of some games is quite complicated) and undo is much faster which usually outweights costs of copying the memory. Some top chess programs are move/undo and some are copy/make, chess board representation usually takes about 200 bytes and variations may go as deep as 100 half moves which means you may need like 20kb additional memory for every thread doing searching. In case of 8 queens it's of course trivial though. Some more information (for chess, so way more advanced): https://chessprogramming.wikispaces.com/Copy-Make https://chessprogramming.wikispaces.com/Copy-Make https://chessprogramming.wikispaces.com/Make+Move https://chessprogramming.wikispaces.com/Make+Move https://chessprogramming.wikispaces.com/Unmake+Move https://chessprogramming.wikispaces.com/Unmake+Move
pkaye 13y ago
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.
- kbenson 13y ago
  From the article: 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. So it appears they are aware of that problem. I'm of the opinion that some "non-classical" problem is probably a better indication of skill and reasoning. Work through a known problem you had at work (which the candidate is hopefully not too familiar with, otherwise abort and try another), and see how they reason out the problem, then ask for some code that might fix it.
- dblotsky 13y ago
  Agreed. However simplified variants on problems like these are actually really effective interview questions. A few years ago, I was asked to solve the N-Rook-Kings (pieces that attack like kings and rooks at the same time) problem, for 1 < N < 16, in half an hour. The catch was that I had to only count the solutions, not find them. The very inexperienced engineer that I was, wrote a highly-optimized (bit boards) solution that could solve N=12 in 6 seconds. But I got this solution after the fact, and it took me hours to write it. A more qualified software engineer would have found a proper combinatorial solution in minutes. In general, giving an actual NP-Complete problem in an interview question and expecting a good solution is unrealistic. However hiding an easy problem in a hard-looking one seems pretty effective.
yetanotherphd 13y ago
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
bluecalm 13y ago
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.
- nu2ycombinator 13y ago
  This is best comment to tell about the current state of some of the programming interview questions.
  - deleted 13y ago
    [deleted]
coldcode 13y ago
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.
- filkatron 13y ago
  I totally agree with you. I'm taking a discrete mathematics course on college and we were asked to solve this.
- VLM 13y ago
  That's the unfortunate part of it. You could have an interesting conversation about strategy. Its an interesting puzzle because the ultimate crude brute force implementation, if my math estimates are correct, is a "couple day" project for a "several hundred" sized parallel cluster, but a slightly smarter algo would be much quicker. There's only 64!/56! possible board configs for 8 pieces ignoring symmetry speedups, and a couple 1E9/second class machines would only take a couple hundred machine*days. The funniest thing about puzzle interviews as an observer is I can't stop thinking ... "and if he gets the job he's going to spend 12 hour days writing a boring frameworked CRUD app" ... "this poor noob probably thinks real on the job programming is like solving chessboard puzzles all day long LOL". The unfortunate part about the abstract puzzle fad is almost no one is paid to solve abstract puzzles but no one is tested on real puzzles. "Yes I know quite well traveling salesman is infeasible for 48 states, I'm asking you to solve it for 5 sites because we only have 5 warehouses" etc.
  - MartinCron 13y ago
    The unfortunate part about the abstract puzzle fad is almost no one is paid to solve abstract puzzles but no one is tested on real puzzles. Once you're discussing real things, they aren't puzzles anymore. One of my favorite things to do in interviews is to just actually have a discussion, as peers, about a real-world technical problem with multiple potential tradeoffs and no one right answer.
  - Crito 13y ago
    Because there is such a straightforward though intractable brute force solution, but several straightforward improvements that can be made on it, I think this is actually a fairly reasonable interview question. If they can't get the naive brute force solution in a few minutes, that indicates something pretty bad. If they treat it as a permutation question and get the n! brute force answer, that is much better (and is still something that can be done in about the same amount of time. If you treat the problem as numbered permutations then checking for diagonals even becomes non-tedious, making it easier to write out on a whiteboard than the naive brute force solution). If they get a proper solution in only a few minutes, you know that they either have their act together, or that they have seen the problem before and remember the solution. That in itself is a good indicator, though if they get a proper solution right away there should be some follow-up questions to get a handle on how exactly they were able to solve it that quickly.
deleted 13y ago
[deleted]
deleted 13y ago
[deleted]
scott_s 13y ago
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/ 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!
mike_mg 13y ago
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
- camus2 13y ago
  Frankly i've been programming for a few years i would not be able to solve the problem in 20 mins. Maybe in 3/4 hours but 20 mins no way. I could come with an idea to solve it though. But that's a very good exercice. > I am first year maths student at Uni Warsaw then Math is your major discipline. Please write down how you would express the solution in a pure mathematical form.
  - mike_mg 13y ago
    Yeah that's a cool exercise and I try to do a lot of these! I guess expressing it mathematically purely is already done in the code of the original solution, because in a way program == proof. If you have some time, here's a great read on this: http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/DonaldKnuth.pdf http://www.maa.org/sites/default/files/pdf/upload_library/22...
- mnbvcxza 13y ago
  Could you code a solution for the Boggle problem in 45 minutes?
  - mike_mg 13y ago
    Given function that checks if given string is a word accepted by the game or a sorted good words list, I think I would be able to. It's a very similar algorithm to queens problem. I'll try doing this and tell you!
- JoeAltmaier 13y ago
  Its one step above fizz-buzz. And it requires algorithmic thinking. So not hard, just a gateway problem.
atmosx 13y ago
I am very interested in finding out Emily's approach on this.
- Jtsummers 13y ago
  How I'd approach it by hand, demonstrated on a 4x4 grid (other than 1x1, smallest grid with a solution). I'll go column by column, noting symmetry that also means I only need to check half the rows for the first queen, and with symmetry and the squares she eliminates I'll have fewer options to consider on each subsequent column. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ | | | | X | +---+---+---+---+ First queen placed, add the second we only have two options so I'll try the top one. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ Oops, gotta move the second queen: +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ Uh oh, can't place the 4th. Moving the first queen since we've exhausted all placements of the 3rd and 2nd queen with the 1st in the upper corner. +---+---+---+---+ | | X | | | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | Q | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ I placed the remainder at once because there was only one legal placement in each column. Extending this approach to 8x8 isn't difficult if the challenge is merely to find a solution. EDIT: I found it in 3 attempts on the 8x8. Going to the column with the most constraints (fewest options) to minimize my branching.
  - Crito 13y ago
    How I'd do it by hand: Each row must have a queen, and each row must have the queen in a different position. Therefore there are 8 rows and we just need to find a correct permutation of them. Number each row 0 through 7. Generate permutations of these numbers. To check for diagonal collisions between permutation indices x and y: abs(perm[x]-perm[y]) == abs(x-y) (In other words, if rows 2 and 4 cannot be two places apart, rows 6 and 7 cannot be one place apart.) Check for diagonal collisions as you're writing out possible valid permutations by hand. Doesn't take long to generate solutions since you don't have to actually draw or mentally picture a board to work out diagonal collisions. You just need to keep 8 single digit numbers in your head.
LukeWalsh 13y ago
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.
- gamegoblin 13y ago
  Agreed. Knight's tour is much more of a "programming" sort of chess problem.
tiedye 13y ago
Everyone seems to forget that there are explicit solutions for the N queens problem. http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_so...
tzs 13y ago
> 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).
- ucarion 13y ago
  Not sure if you're aware of this, but the technique of representing a chess board as a 64-bit bitmap is in fact the method used by pretty much all chess engines these days. These 64-bit unsigned long longs are known as "bitboards". https://chessprogramming.wikispaces.com/Bitboards https://chessprogramming.wikispaces.com/Bitboards
thelucky41 13y ago
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.
deleted 13y ago
[deleted]
bloaf 13y ago
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.
columbo 13y ago
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.
- vosper 13y ago
  I work with someone whose go-to question is the 8 Queens problem. I think it's an interesting exercise, but like you said it's quite long - can easily consume most of the interview. It's also very poorly aligned with the kind of work we do and code we write (for example, I can't think of a single place in our code using recursion) and so I'm not a fan of it as part of an interview. Edit: typo
  - pmiller2 13y ago
    So, how do the candidates that pass this colleague's interview do in the actual job?
mnbvcxza 13y ago
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))
- JoeAltmaier 13y ago
  Right! I did that solution in response to a Byte magazine contest years ago. It ran in 20 minutes in Basic on an HP2000. The tricky part is permuting the array. I used a recursive swap routine, swapping to the right and testing if the array were valid to the left of i then recursing i+1. If it fails you don't have to recurse, you can pop, trimming the search tree drastically. There were 8 or 9 solutions if I remember right, less if you eliminate rotations and mirrors. {edit: 12 solutions}
tel 13y ago
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]
pmorici 13y ago
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-with-bits.html http://therandombit.blogspot.com/2008/09/n-queens-implmented...
seivan 13y ago
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.
- deleted 13y ago
  [deleted]
thedigitalengel 13y ago
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. :)
deleted 13y ago
[deleted]
kofq 13y ago
My brother had created fastest solution ( both in time and space complexity ) for this problem.

54 points by bcjordan 13y ago

nilkn 13y ago

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

Codhisattva 13y ago
Not lucky - the answer is inferable. Exhaustive search is just the primitive way.
- VintageCool 13y ago
  Just place them like knights!

JSno 13y ago

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/Miscellaneous/N-Queens http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscel...

thirsteh 13y ago
Your indentation broke: 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
- JoeAltmaier 13y ago
  Hm. And maybe that's why Haskell isn't catching on. That looks little better than terminal scripting languages. Its concise, sure. But maybe that's not as helpful as you might think, in communicating a problem solution.
  - thirsteh 13y ago
    Haskell is catching on. It's extremely popular in academia, and it's growing on e.g. Github: http://ec2-54-224-80-201.compute-1.amazonaws.com:8888/languages_visualization/71c6f3773a3cbe2aa440949bc906bd4d/index.html http://ec2-54-224-80-201.compute-1.amazonaws.com:8888/langua... But you're right, examples like this are extremely poor marketing for Haskell. It's really not how you'd write most Haskell programs. A lot of the Haskell code on sites like Rosetta Code is deliberately terse to show off. I changed the indentation a little bit, to make it more clear: 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 'queens' is essentially a for loop that concatenates the elements between 1..n that are safe, and 'safe' is a function that returns true if it's given an empty list, or if the input satisfies all of the predicates in the other list (notice the recursion that's possible because of laziness.) The function 'and' that it calls takes a list of bools and returns true if all of them are true. 'main' prints each list that results from running 'queens 8' There is some syntax and convention you have to learn, e.g. what the _ in mapM_ means, what a list comprehension is, or what : means, etc. but once you have it's a fairly elegant solution (compare to the code snippets from imperative languages.)
13y ago

zackbrown 13y ago

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

bluecalm 13y ago
I'd give bonus points for pointing out some implementation decisions: -when searching is it better to use copy-make or move/undo approach ? (copy make is faster on modern pc's, at least for things like 8Q's, it's also much easier to implement as you don't need any code for undoing moves) -what is the best way to check if given move (placing the queen) is valid ? (you need three 0-1 arrays for rows and diagonals in both direction this a neat trick, very difficult to come up with but which speeds the whole thing immensely) -how do you break out of the recursion if the task is changed to find one solution ? I know all those things because I am a hobbyist who wrote a lot of solvers and dabbled into chess programming. I am probably in top 0.1% of people if I get question like this. I am incompetent when it comes to things needed in most commercial applications as I've never worked on big commercial projects. This question filters for people like me. I can't imagine how this a good thing for anything practical (unless the task is to produce the best chess program or something).
- kenjackson 13y ago
  What is copy/make vs move/undo? I'm not familiar with that terminology...
  - bluecalm 13y ago
    When you search you have a choice of: 1)having only one board and make/undo moves on it. So every time you put a new queen on the board you add it to the representation of the board and every time you go back in recursion you need to do an undo before exiting the function (so you new branch won't have queens placed on the board from previous branch) 2)storing as many boards as many steps deep in the recursion you are (max 8 in 8 queens problem) so every time you go deeper into recursion you create new board then you copy current state there and then you make a move (place a queen) on this new board; this way when you go back in recursion you do nothing as this new board is taken care of by stack pointer going back. The cost of copy make is memory (you need memory for new board representation for every step deeper into recursion) but it's usually not much of a problem. The benefit is that you don't need to code undo logic (which in case of some games is quite complicated) and undo is much faster which usually outweights costs of copying the memory. Some top chess programs are move/undo and some are copy/make, chess board representation usually takes about 200 bytes and variations may go as deep as 100 half moves which means you may need like 20kb additional memory for every thread doing searching. In case of 8 queens it's of course trivial though. Some more information (for chess, so way more advanced): https://chessprogramming.wikispaces.com/Copy-Make https://chessprogramming.wikispaces.com/Copy-Make https://chessprogramming.wikispaces.com/Make+Move https://chessprogramming.wikispaces.com/Make+Move https://chessprogramming.wikispaces.com/Unmake+Move https://chessprogramming.wikispaces.com/Unmake+Move

pkaye 13y ago

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.

kbenson 13y ago
From the article: 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. So it appears they are aware of that problem. I'm of the opinion that some "non-classical" problem is probably a better indication of skill and reasoning. Work through a known problem you had at work (which the candidate is hopefully not too familiar with, otherwise abort and try another), and see how they reason out the problem, then ask for some code that might fix it.
dblotsky 13y ago
Agreed. However simplified variants on problems like these are actually really effective interview questions. A few years ago, I was asked to solve the N-Rook-Kings (pieces that attack like kings and rooks at the same time) problem, for 1 < N < 16, in half an hour. The catch was that I had to only count the solutions, not find them. The very inexperienced engineer that I was, wrote a highly-optimized (bit boards) solution that could solve N=12 in 6 seconds. But I got this solution after the fact, and it took me hours to write it. A more qualified software engineer would have found a proper combinatorial solution in minutes. In general, giving an actual NP-Complete problem in an interview question and expecting a good solution is unrealistic. However hiding an easy problem in a hard-looking one seems pretty effective.

yetanotherphd 13y ago

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

bluecalm 13y ago

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.

nu2ycombinator 13y ago
This is best comment to tell about the current state of some of the programming interview questions.
- deleted 13y ago
  [deleted]

coldcode 13y ago

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.

filkatron 13y ago
I totally agree with you. I'm taking a discrete mathematics course on college and we were asked to solve this.
VLM 13y ago
That's the unfortunate part of it. You could have an interesting conversation about strategy. Its an interesting puzzle because the ultimate crude brute force implementation, if my math estimates are correct, is a "couple day" project for a "several hundred" sized parallel cluster, but a slightly smarter algo would be much quicker. There's only 64!/56! possible board configs for 8 pieces ignoring symmetry speedups, and a couple 1E9/second class machines would only take a couple hundred machine*days. The funniest thing about puzzle interviews as an observer is I can't stop thinking ... "and if he gets the job he's going to spend 12 hour days writing a boring frameworked CRUD app" ... "this poor noob probably thinks real on the job programming is like solving chessboard puzzles all day long LOL". The unfortunate part about the abstract puzzle fad is almost no one is paid to solve abstract puzzles but no one is tested on real puzzles. "Yes I know quite well traveling salesman is infeasible for 48 states, I'm asking you to solve it for 5 sites because we only have 5 warehouses" etc.
- MartinCron 13y ago
  The unfortunate part about the abstract puzzle fad is almost no one is paid to solve abstract puzzles but no one is tested on real puzzles. Once you're discussing real things, they aren't puzzles anymore. One of my favorite things to do in interviews is to just actually have a discussion, as peers, about a real-world technical problem with multiple potential tradeoffs and no one right answer.
- Crito 13y ago
  Because there is such a straightforward though intractable brute force solution, but several straightforward improvements that can be made on it, I think this is actually a fairly reasonable interview question. If they can't get the naive brute force solution in a few minutes, that indicates something pretty bad. If they treat it as a permutation question and get the n! brute force answer, that is much better (and is still something that can be done in about the same amount of time. If you treat the problem as numbered permutations then checking for diagonals even becomes non-tedious, making it easier to write out on a whiteboard than the naive brute force solution). If they get a proper solution in only a few minutes, you know that they either have their act together, or that they have seen the problem before and remember the solution. That in itself is a good indicator, though if they get a proper solution right away there should be some follow-up questions to get a handle on how exactly they were able to solve it that quickly.

deleted 13y ago

[deleted]

deleted 13y ago

[deleted]

scott_s 13y ago

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/ 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!

mike_mg 13y ago

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

camus2 13y ago
Frankly i've been programming for a few years i would not be able to solve the problem in 20 mins. Maybe in 3/4 hours but 20 mins no way. I could come with an idea to solve it though. But that's a very good exercice. > I am first year maths student at Uni Warsaw then Math is your major discipline. Please write down how you would express the solution in a pure mathematical form.
- mike_mg 13y ago
  Yeah that's a cool exercise and I try to do a lot of these! I guess expressing it mathematically purely is already done in the code of the original solution, because in a way program == proof. If you have some time, here's a great read on this: http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/DonaldKnuth.pdf http://www.maa.org/sites/default/files/pdf/upload_library/22...
mnbvcxza 13y ago
Could you code a solution for the Boggle problem in 45 minutes?
- mike_mg 13y ago
  Given function that checks if given string is a word accepted by the game or a sorted good words list, I think I would be able to. It's a very similar algorithm to queens problem. I'll try doing this and tell you!
JoeAltmaier 13y ago
Its one step above fizz-buzz. And it requires algorithmic thinking. So not hard, just a gateway problem.

atmosx 13y ago

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

Jtsummers 13y ago
How I'd approach it by hand, demonstrated on a 4x4 grid (other than 1x1, smallest grid with a solution). I'll go column by column, noting symmetry that also means I only need to check half the rows for the first queen, and with symmetry and the squares she eliminates I'll have fewer options to consider on each subsequent column. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ | | | | X | +---+---+---+---+ First queen placed, add the second we only have two options so I'll try the top one. +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ Oops, gotta move the second queen: +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | | | X | X | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ Uh oh, can't place the 4th. Moving the first queen since we've exhausted all placements of the 3rd and 2nd queen with the 1st in the upper corner. +---+---+---+---+ | | X | | | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | | | +---+---+---+---+ | | | X | | +---+---+---+---+ +---+---+---+---+ | | X | Q | X | +---+---+---+---+ | Q | X | X | X | +---+---+---+---+ | | X | X | Q | +---+---+---+---+ | | Q | X | X | +---+---+---+---+ I placed the remainder at once because there was only one legal placement in each column. Extending this approach to 8x8 isn't difficult if the challenge is merely to find a solution. EDIT: I found it in 3 attempts on the 8x8. Going to the column with the most constraints (fewest options) to minimize my branching.
- Crito 13y ago
  How I'd do it by hand: Each row must have a queen, and each row must have the queen in a different position. Therefore there are 8 rows and we just need to find a correct permutation of them. Number each row 0 through 7. Generate permutations of these numbers. To check for diagonal collisions between permutation indices x and y: abs(perm[x]-perm[y]) == abs(x-y) (In other words, if rows 2 and 4 cannot be two places apart, rows 6 and 7 cannot be one place apart.) Check for diagonal collisions as you're writing out possible valid permutations by hand. Doesn't take long to generate solutions since you don't have to actually draw or mentally picture a board to work out diagonal collisions. You just need to keep 8 single digit numbers in your head.

LukeWalsh 13y ago

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.

gamegoblin 13y ago
Agreed. Knight's tour is much more of a "programming" sort of chess problem.

tiedye 13y ago

Everyone seems to forget that there are explicit solutions for the N queens problem. http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions http://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_so...

tzs 13y ago

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

ucarion 13y ago
Not sure if you're aware of this, but the technique of representing a chess board as a 64-bit bitmap is in fact the method used by pretty much all chess engines these days. These 64-bit unsigned long longs are known as "bitboards". https://chessprogramming.wikispaces.com/Bitboards https://chessprogramming.wikispaces.com/Bitboards

thelucky41 13y ago

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.

deleted 13y ago

[deleted]

bloaf 13y ago

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.

columbo 13y ago

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.

vosper 13y ago
I work with someone whose go-to question is the 8 Queens problem. I think it's an interesting exercise, but like you said it's quite long - can easily consume most of the interview. It's also very poorly aligned with the kind of work we do and code we write (for example, I can't think of a single place in our code using recursion) and so I'm not a fan of it as part of an interview. Edit: typo
- pmiller2 13y ago
  So, how do the candidates that pass this colleague's interview do in the actual job?

mnbvcxza 13y ago

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

JoeAltmaier 13y ago
Right! I did that solution in response to a Byte magazine contest years ago. It ran in 20 minutes in Basic on an HP2000. The tricky part is permuting the array. I used a recursive swap routine, swapping to the right and testing if the array were valid to the left of i then recursing i+1. If it fails you don't have to recurse, you can pop, trimming the search tree drastically. There were 8 or 9 solutions if I remember right, less if you eliminate rotations and mirrors. {edit: 12 solutions}

tel 13y ago

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]

pmorici 13y ago

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-with-bits.html http://therandombit.blogspot.com/2008/09/n-queens-implmented...

seivan 13y ago

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.

deleted 13y ago
[deleted]

thedigitalengel 13y ago

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

deleted 13y ago

[deleted]

kofq 13y ago

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