Algorithms – Solving N Queens Problem on X by Y Board

algorithmschesspuzzles

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 Answer

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

Related Topic