N Queens Using Bit

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number n, the size of a chess board.
2. You are required to place n number of queens in the n * n cells of board such that no queen can kill another.
Note - Queens kill at distance in all 8 directions
3. Complete the body of printNQueens function - without changing signature - to calculate and print all safe configurations of n-queens
Use sample input and output to get more idea.

Note -> The online judge can't force you to write the function recursively but that is what the spirit of question is.
Write recursive and not iterative logic. The purpose of the question is to aid learning recursion, branch and bound technique, bit manipulation
and not test you.
Input Format
A number n
Output Format
Safe configurations of queens as suggested in sample output
Question Video
Constraints
1 <= n <= 10
Sample Input
4
Sample Output
0-1, 1-3, 2-0, 3-2, .
0-2, 1-0, 2-3, 3-1, .


  • Editorial

    The problem here deals with solving NQueens problem using the concepts of bit manipulation. Earlier we have solved the NQueens problem using recursion and backtracking. This bit manipulation technique is just an optimization to the recursive solution so the NQueens Branch and Bound recursive solution is a pre-requisite to this problem.

    The N Queens problem deals with placing N Queens on a N*N board so that no two queens attack each other. A queen can attack in all 8 directions.

    For example N = 4

    _ _ Q _

    Q _ _ _

    _ _ _ Q

    _ Q _ _

    The above arrangement is a possible solution to the problem.

    In this solution, we will be working on space optimization for the branch and bound method. So instead of creating arrays for columns, diagonals, and antidiagonal here, we will be maintained integer values which will be the binary representation analogous to that of arrays created earlier. Here an unset bit will provide us the information that position is a safe position and a set bit will imply that we need not apply recursion here as that would lead to an attack by the queen.

    The rest implementation is solely based on branch and bound NQueens recursive solution.

    Time Complexity: O(N!)

    Each row has N positions to deal with which makes our recursive solution of the type: T(n) = n*T(n-1) + k

    Space Complexity: O(N*N)

    A board of size N*N is created to store the result.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name