4 Queens Drawback – GeeksforGeeks

4 – Queens’ drawback is to put 4 – queens on a 4 x 4 chessboard in such a way that no queens assault one another by being in the identical row, column, or diagonal. 

We are going to search for the answer for n=4 on a 4 x 4 chessboard on this article.

A 4*4 Chess Board

Method:

Right here we now have to put 4 queens say Q1, Q2, Q3, Q4  on the 4 x 4 chessboard such that no 2 queens assault one another. 

• Let’s suppose we’re placing our first queen Q1 at place (1, 1) now for  Q2 we will’t put it in 1 row( as a result of they may battle ). 
  • So for Q2 we should think about row 2. In row 2 we will place it in column 3 I.e at (2, 3) however then there will probably be no possibility for putting Q3 in row 3. 
    • So we backtrack one step and place Q2 at (2, 4) then we discover the place for putting  Q3 is (3, 2) however by this, no possibility will probably be left for putting Q4.
• Then we now have to backtrack until ‘Q1’ and put it to (1, 2) as a substitute of (1, 1) after which all different queens could be positioned safely by transferring Q2 to the place (2, 4), Q3  to (3, 1), and Q4 to (4, 3).

Therefore we acquired our answer as (2, 4, 1, 3), that is the one doable answer for the 4-Queen Drawback. For one more answer, we should backtrack to all doable partial options

 

• The opposite doable answer for the 4 Queen drawback is (3, 4, 1, 2)

 

Discovering options by State Area Tree:

State area tree could be drawn utilizing backtracking and by this, we will discover the all doable answer for the 4 queen drawback and never solely 4 queens by this we will discover all doable options to N queen drawback

State Area Tree of 4 Queen Drawback

• The easy logic of producing the state area tree is to maintain exploring all doable options utilizing backtracking and cease exploring that answer the place ever two queens are attacking one another.

For all of the positions(columns) within the present row:

• Test for all of the earlier rows is there a queen or not?
• Test for all of the earlier diagonal columns is there a queen or not?
• If any of those circumstances are true, then backtrack to the earlier row and transfer the earlier queen 1 step ahead.
• In any other case, put the present queen within the place and transfer to the subsequent row.

Now Let’s see the Implementation of this drawback:

Resolution #1:
*    Q    *    *    
*    *    *    Q    
Q    *    *    *    
*    *    Q    *    


Resolution #2:
*    *    Q    *    
Q    *    *    *    
*    *    *    Q    
*    Q    *    *    

Complete options=2

Time complexity: O(N²)
Auxiliary Area: O(N)