N queens, X by Y board decision problem interview question

I was asked the following question in an interview today and I've been thinking about it ever since. I was not able to answer it and haven't been able to find a solution online.

Given a chess board with dimensions X by Y and N queens, determine whether it is possible to arrange these queens on the board such that they cannot attack each other.

A 2 x 3 board with 2 queens does have a solution so the algorithm would return true:

``````Q . .
. . Q
``````

I'm looking for a programming approach to this puzzle, not just ways to solve it on paper, for example.

-
Best First Search is certainly an option, as are other search heuristics – Jason Sep 15 '11 at 1:43
nominated for one of the worst interview questions ever - unless the software they work on relies on backtracking solutions, in which case it's totally relevant – Steven A. Lowe Sep 15 '11 at 6:08
To be fair the interviewer said that this was simply an extra credit kind of thing. The rest of the interview was pretty legit IMO. I was just curious. – Interviewee Sep 15 '11 at 6:39

4 Answers

This isn't (IMO) a very interesting problem from a programming point of view. You could come up with a recursive algorithm that tries every arrangement, something like this:

``````bool try_queens(Board board, int n)
{
if (n == 0) {
// no queens left to place, so we're done
return true
}
// try each open position until we find one that works
for each position on the board {
if (is_empty(board, position) and not is_attacked(board, position)) {
place_queen(board, position)
if (try_queens(board, n-1)) {
return true
}
remove_queen(board, position)
}
}
// if we get this far, there's no available position
return false
}

main()
{
initialize board(X,Y)
return try_queens(board, N)
}
``````

If you think about the problem a bit, you'll realize that there's no way to fit N queens on a board where X < N or Y < N because that would require that at least two queens end up in the same rank or file, and they would therefore attack each other. If you read about the n-queens problem, you'll quickly learn that it's always possible to place N queens on a NxN board for N > 3. Now we know that the answer is NO for (X < N or Y < N) and YES for (X >= N and Y >= N, N > 3). All that's left are the special cases:

• N=1 (YES)
• N=2 (YES for X>=2 and Y>2 or vice versa)
• N=3 (YES for X>=3 and Y>3 or vice versa)

So now our nice recursive function becomes a simple function that just compares N to X and Y and returns a canned result. That's great from a performance point of view, since you can get an answer in constant time. It's not so great from a programming point of view because you realize, at this point, that the question is really more about how well you can solve puzzles than it is about your ability to write a recursive function.

(And boy oh boy, I really hope that I didn't make some dumb mistake in my smarty-pants answer. ;-)

-

If the interviewer had asked you to write the code for the problem, then I think that it is not fair. The algorithm requires work. However, if the idea was to show the interviewer the classes, methods or some concepts that you'd need to use or something similar, then it may be a fair question.

The problem is a classical Computer Science problem and is discussed in many such books. An excellent explanation, with animation and 12 different solutions together with some code could be found here:

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

Also code can be found here: http://www.codeproject.com/KB/java/EightQueen.aspx

Don't feel bad about this, as I said, it is not an easy one.

-

This is more of a comment really, but it doesn't fit in there ...

A chess board has 8x8 squares, no more no less (these questions always annoy me with that approach of a customized chess board).

But anyways, if you have an x*y chess board, and n queens and taking that the queen "takes" these fields

could you just create a two dimensional array and "flag" all fields that one queen attacks. Then place the other one (from the middle of the board), flag the remaining fields, and so on ... until you run either of fields or queens.

This is of course a very simplified approach, since if positioned in a bad manner, I gather the maximum number of queens would vary.

Hmm, just found this as well - 8 queens problem.

-
I proposed this exact algorithm at first but consider that you're not guaranteed that if you take this approach and you end up with no places to put your last Queen that you really have determined it's impossible. You've only eliminated that particular arrangement. This is basically an application of the nearest-neighbor heuristic. – Interviewee Sep 15 '11 at 1:42
@Interviewee - Yeah, I know. This is just something I thought of off the top of my head. As said, it's an interesting problem and could probably be improved, but in 4am (here) I'm just too lazy to think. Btw, how did the interview went? – Rook Sep 15 '11 at 2:48
@Interviewee, this is the right idea. The part that's missing is that if you discover there's no place for the last queen, you back up and try a different position for the second to last queen. If there's no place for that queen that allows placement of the last queen, you back up another level and try a different spot for the third to last queen, and so on. – Caleb Sep 15 '11 at 4:11
I like that your avatar is a chess piece :) – warren Sep 15 '11 at 6:45

Basically, the backtrack algorithm works like this:

1. Create an X by Y array. Set all squares to empty.

2. Set the queen count to zero.

3. Set your current position to (1,1)

4. See if you can place a queen in the current position.

5. If you can, set Array(X,Y) to queen, increment the queen count. If you placed all queen, stop, you have a solution.

6. If the current position is not (X,Y), increment the current position and go to step 4.

7. Find the queen in the last position (the one that comes last in the order you increment positions). Set the current position to the position of that queen, remove it, and decrement the queen count.

8. If the queen count is zero, stop, there is no solution.

9. Increment the current position.

10. Go to step 4.

-