4 Queens Drawback – GeeksforGeeks
[ad_1]
4 – Queens’ downside is to put 4 – queens on a 4 x 4 chessboard in such a fashion that no queens assault one another by being in the identical row, column, or diagonal.
We’ll search for the answer for n=4 on a 4 x 4 chessboard on this article.
Strategy:
Right here now we 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 take into account row 2. In row 2 we will place it in column 3 I.e at (2, 3) however then there shall 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 shall be left for putting Q4.
 So for Q2 we should take into account row 2. In row 2 we will place it in column 3 I.e at (2, 3) however then there shall be no possibility for putting Q3 in row 3.
 Then now we have to backtrack until ‘Q1’ and put it to (1, 2) as a substitute of (1, 1) after which all different queens may be positioned safely by shifting Q2 to the place (2, 4), Q3 to (3, 1), and Q4 to (4, 3).
Therefore we bought our resolution as (2, 4, 1, 3), that is the one potential resolution for the 4Queen Drawback. For one more resolution, we should backtrack to all potential partial options
 The opposite potential resolution for the 4 Queen downside is (3, 4, 1, 2)
Discovering options by means of State Area Tree:
State area tree may be drawn utilizing backtracking and by this, we can discover the all potential resolution for the 4 queen downside and never solely 4 queens by this we will discover all potential options to N queen downside
 The easy logic of producing the state area tree is to maintain exploring all potential options utilizing backtracking and cease exploring that resolution 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 situations 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 following row.
Now Let’s see the Implementation of this downside:
C

Resolution #1: * Q * * * * * Q Q * * * * * Q * Resolution #2: * * Q * Q * * * * * * Q * Q * * Complete options=2
Time complexity: O(N^{2})
Auxiliary Area: O(N)
[ad_2]