N queens, X by Y board decision problem interview question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

Adding to the other answers: creating a bi-dimensional array only complicates the code.

You just need a vector of size 8 for a regular chess board. Or 8+1 if like C 1st position is 0, only to simplify the code, and deal with 1-8 and not 0-7.

If you think about x being your position in the array, and y being the content of the position. e.g board[1] = 8 means the first queen is at [1,8].

In that way, you only need to check for columns validation.

At faculty time, I came across a very old book (60s?), about algorithms implemented in Dartmouth BASIC, that implemented the 8 queen problem using the less memory possible (being that old, it makes sense).

As far as I remember, it used the vector idea, and it essentially brute forced all positions in the board with two FOR cycles. For checking for position validity, it used a third loop, a WHILE cycle in each position go back in the vector, and check for an equal number, or for a formula using a tangent operation to check for diagonals.

Sadly, I lost track of that book...

Said algorithm found all the solutions for the n-queen problem.

Answer 6

If you just have to write an algorithm to determine whether such an arrangement exists, then look at the existing research:
Eight queens puzzle on Wikipedia.

You can trivially return false if N > min(X, Y).
After reading that page, you know to return true if N <= min(X, Y) and 2, 3 != min(X, Y).

Which leaves 2, 3 == min(X, Y) and N <= min(X, Y).

Well, if N < min(X, Y), finding a solution is trivial.
If N == min(X, Y), there's only a solution if max(X, Y) > N.

f(X, Y, N)
    if X < Y => f(Y, X, N)
    if Y > N => false
    => (Y < N) or (Y != 2 and Y != 3) or (X > N)

Answer 7

There is obviously no solution if N > min (X, Y). Otherwise, you can easily show that there is no solution for N = X = Y = 2, N = X = Y = 3. For all other cases there seems to be a solution. The number of solutions seems to go up as N grow.

You can find a solution through exhaustive search with backtracking: Put a queen in the first row, column 1. Put a queen in the second row, in the first column that the queen in row 1 cannot reach. Put a queen in the second row etc. If a queen cannot be put into row k, then you remove it and move the queen in row k-1 in the next unoccupied position.