N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

8-queens

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

A follow-up question: Now, instead outputting board configurations, return the total number of distinct solutions.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Well, this is a classic problem, isn’t it? However, all I know is that it’s classic and I’ve never really read about any article of NQueens, except for the title NQueens. So lucky for me, I got the chance to solve it with no prior knowledge.

Q: What is the unknown?

A: All possible board configurations that satisfy the requirements.

Q: What are the data?

A: An N x N chess board (or just an N x N matrix).

Q: What are the constraints?

A: No two queens on the board can attack each other. In other words, no two queens can be on the same row, column or cross.

Q: Good. Since you’ve never seen this question before, what’s your initial thought about this question? Anything’s fine.

A: I don’t have anything fancy, but possibly a naive way of solving it: for example, I could put a Queen in an available cell (no other Queens can attack) on the chess board. Then cross out all other cells this Queen can attack. Then on the second row, I place another Queen in an available cell and then cross out cells she can attack. On the next row I do the same thing until we place all N Queens on the chess board.

Q: What if on a certain row, there is nowhere you can place a new Queen?

A:  Hmm, that means the placement of the Queen on the previous row was a bad move.

Q: So what should you do about it?

A: Well, undo it then. Undo the cross out of board cells caused by that bad move. Get the queen up and place it somewhere else on that row, if there are any available cells left.

Q: What if there are no available cells neither?

A: Hmm, then the bad move’s previous move was bad. We have to do the same thing for it as above.

Q: Good. Now, can you summarize your thought and maybe find out the pattern in it?

A: I place a Queen in an available cell on a row, and cross out cells she can attack. Then on the next row, again I place a Queen in an available cell and cross out cells she can attack. If I cannot place any Queen, that means the previous move was bad and we undo that move and its cross-out, then place that Queen in another available cell. If that’s not possible, then the previous previous move was bad and we should….  OK I get it. This has something to do with recursion, doesn’t it? And in fact, even if we find a solution, we still need to undo previous move and its cross-out since we are looking for all possible solutions, not just one. Other moves may also lead to solutions. 

Q: Good catch. Now can you think of an abstract version of your thoughts? Possibly some pseudo code?

A: OK. So if we are dealing with recursion, we should always think about base case and recursive case. The base case should be that N queens are all on the board. Maybe we should keep track of how many Queens on the board? Or on the second thought, maybe not. Based on my thoughts above, since we are moving to the next row if and only if we can place a Queen on the current row, a solution is found if we are on row N (row index from 0 to N-1). This is the time we stop recursion and return the current board configuration.

// suppose we call this function solveNQueens

// base case
if (rowInd == N) {
    SaveTheBoard(board);
    return;
}

OK, moving on to the recursive case. I don’t want to repeat myself again so let’s look at some pseudo codes.

// since we want all possible solution, we should check all possible cells. Therefore we use the loop. Say we are on row K.
for(int i = 0; i < N; i++){
    if (isAvailable(board[K][i])){
         placeTheQueen(board, K, i);
         crossOutCells(board, K, i);
         solveNQueens(board, K + 1, N);
         undoPlaceAndCrossOut(board, K, N); // always undo
    }
}

Q: Good. Just one question before we move on to real code. How do you plan to do the cross out and undoCrossOut?

A: Oh I could create a boolean matrix[N][N] and if a cell is crossed out, set the corresponding cell to true. In undoCrossOut just set it to false.

Q: Hmm, not quite. Think about this: A cell C2 on the second row is set to true (crossed out by a Queen on the first row). You place a Queen on the second row somewhere and C2 gets crossed out again (set to true). Later you find that your move on the second row isn’t ideal. You undo the move and C2 is set to false. That doesn’t seem right. Since it can be attacked by the Queen on the first row.

A: Hmm, then I guess I can use an integer matrix then. Every time a cell gets crossed out, we increase the value in the corresponding cell. As long as the value in a cell is greater than 0, it is not available.

Q: Sounds good. Now go on to do some real coding.

Code on github:

Now for the follow up question, it is actually simpler. We don’t even need the board. All we need is just a counter and we increase the counter only in the base case. But sure to return the counter. (The code below mentions a mistake I made about Integer type)

Enhanced by Zemanta
Advertisements
N-Queens

One thought on “N-Queens

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s