N Queen

#Day 11

Today I am going to explain n queen problem which is based on backtracking. N-queen problem is to set n queens on a board of chess of size n*n such that no queen can attack each other.

For those who don’t know how queen works in chess-

The queen can attack anyone which is diagonally,horizontally or vertically placed to the queen.

One such combination on 4*4 board, where no queen can attack each other is  (queen is represented by x)

nq1-1

To solve this problem we will use backtracking. We will start from the first row, place the queen in the very first box available to us.

Then we move to next row start from the 0th index and check if the current queen is compatible with the previously placed queens. If the queen is compatible to all the previous queens we head to next row otherwise, we increase the column of the current queen. If we can not increase the current queen’s column(the current column is the last one on the board). Then we move one row backward and increase the column of that queen and continue with the same algorithm.

If the queen is compatible to all the previous queens we head to next row otherwise, we increase the column of the current queen. If we can not increase the current queen’s column(the current column is the last one on the board). Then we move one row backward and increase the column of that queen and continue with the same algorithm.

If we reach to last row and queen is compatible then we return the current board. If we reach to last column of row 0 after backtracking then there is no such combination which satisfies the problem.

To check the compatibility of the queen with another queen the following rule can be used

  • If rows of both queens are same
  • If column of both queens are same
  • Differences of row and column of both the  queens are same
  • Differences of column and row of both the  queens are same

If any of the above conditions is satisfied then queens are not compatible.

def is_compatible(pos_to_compare,pos_to_be_compared_with):
    if pos_to_be_compared_with[0]==pos_to_compare[0]:
        return False
    if pos_to_be_compared_with[1]==pos_to_compare[1]:
        return False
    if pos_to_compare[0]+pos_to_compare[1]==pos_to_be_compared_with[0]+pos_to_be_compared_with[1]:
        return False
    if pos_to_compare[0]-pos_to_compare[1]==pos_to_be_compared_with[0]-pos_to_be_compared_with[1]:
        return False
    return True

Let’s understand the above problem with an example-

nq2

We chose the first row and the first column for the starting row queen. Then we chose the first column in the next row

nq3

Now these queens are not compatible so we choose the next column in the same row.

nq4

Above board satisfies the conditions hence we head to next row and choose the first column.

nq5

Now this board doesn’t satisfy the condition so we choose the next column in this row.

nq6

Again this doesn’t satisfy so move to next column until we either satisfy the condition or reach the end of row.

nq8

We have reached the row of the current row and still the conditions are not satisfied so we move back one row and choose the next column for that.

nq9

Then again we choose the next row starting with first column again.

nq10

The process continue until we reach the combination which satisfy the conditions otherwise we don’t have any move left.

For the above board we get the final board as

nq1-1

Data Structure For the Problem

Data structure which should be used in this problem is stack. Using stack we can pop the last item if we can’t move forward in the row.

Time Complexity 

The time complexity for this problem is exponential.

Source Code

Source code for this problem can be found here.

Advertisements

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