Ridhwansyah [dot] Com

SOLVING N – QUEENS PROBLEM IN DESIGN AND ANALYSIS OF ALGORITHM USING BACKTRACKING METHOD:

 

            This is an article explains about solving the n- queens problem in design and analysis of algorithms using backtracking method.

 

Concept of Backtracking Method:

             In the backtracking method, we need to solve the problem by systematic process until we get the solution. In the 3rd or 4th step if we find difficult to get the solution or there is no way to get the solution means  we need to move to the previous step and make changes over there to get a feasible solution in the next step this is called backtracking.

 

 

Concept of N- Queens Problem:

 

            The concept of N queens problem is that we need to place N queens in N x N matrix where in which the following conditions should apply.

 

No two queens should be placed in the same row
No two queens should be placed in the same column
No two queens should be placed in the same diagonal

 

Example here we are going to solve the 4 queen’s problem:

 

Here we have Q1, Q2, Q3, and Q4.

 

The Q1 should be place in row /column1

 

The Q2 should be place in row/column 2

 

The Q3 should be place in row/column 3

 

The Q4 should be place in row/column 4

 

Consider the matrix

                  c1        c2        c3        c4

r1

 

r2

 

r3

 

r4

Now place Q1 in row1/column1 so,

 

                  c1        c2        c3        c4

r1               Q1

 

r2

 

r3

 

r4

 

Now Q2 should be placed in row2/column2, if we place in c2xr2 the queens will be crossed because they are in the same diagonal. Therefore, the Q2 should be placed in c3xr2

 

                  c1        c2        c3        c4

r1               Q1

 

r2                                       Q2

 

r3

 

r4

 

Now place Q3 in row3/column3, if we place in c3xr3 the queens meet each other because they are in the same diagonal. Therefore, there is no solution the place the Q3 in the 3rd row/column.

 

                  c1        c2        c3        c4

r1               Q1

 

r2                                       Q2

 

r3

 

r4

 

So, back track again, place the Q1 some where in the row, so move the Queen Q1 to c3xr1 and also move the position of Q2 so that these two queens should not affect the Q3.

 

So place Q1 in r1xc3

 

Place Q2 in r2xc1

 

 

 

                  c1        c2        c3        c4

r1                                       Q1

 

r2               Q2

 

r3

 

r4

 

Now place Q3 in row3/column3. We cannot place in either r3xc1 or r3xc2 or r3xc3 because the queens will meet each other. So place the queen in Q3 in r3xc4.

 

                  c1        c2        c3        c4

r1                                       Q1

 

r2               Q2

 

r3                                                   Q3

 

r4

 

 

Now place Q4 in row4/column4. we cannot place Q4 in c1 or c3 or c4 so only solution is to place the Q4 in c2xr4.

 

                  c1        c2        c3        c4

r1                                       Q1

 

r2               Q2

 

r3                                                   Q3

 

r4                           Q4

 

 

Now we got the solution in which we place the entire queen in 4×4 matrixes were in which no two queens meet each other.

 

 

Are many products offering don’t make you easier to pick one as your weight loss pill? Perhaps you already made a decision that this is the last review you read, but lucky you because we will give the accurate solution. Here are the nine, the top weight loss products: 1. Apidexin, it can lose up to 400% more weight; 2. Phenphedrine, the high performance of fat burning formula; 3. Lipovox, weight loss and healthy skin; 4. Testoripped, the fat burner for men; 5. Dieters Cheating Caps, fat and carbs blockers; 6. 7 Day Detox; 7. SomnaSlim PM, you wll lose your weight in your sleep; 8. 72 Hour Diet Pill; 9. Colonoxy.