4 Queens Problem without Backtracking (Brute Force Approach)

Figure 1: 4 queen problem solved

What is 4 queen problem?

Assume a chessboard of 4x4 i.e. 16 blocks, now we have to place 4 queens on chessboard in such a manner that they don’t capture each other.

How can they capture each other?

1. If they lie in same row or column, they can capture each other.
2. Diagonally lying queens can capture each other. (one queen can capture other queen if it lies in main diagonal or off diagonal)

Task?

Place queens in a manner that they can’t capture each other and return positions.

How to code?

NOTE: Code will be written in C++ but you can write the idea in any language.

Firstly, we must write a small block of code that can check if there is conflict between two positions or not. This code will help us in writing major code/ main code as whenever we will place new queen, we will check if it’s position conflicts with previously placed queens or not? Let’s write code for conflict() first.

bool conflict(int i,int j){
    if((j-i)%4==0) // same column
        return 1;
    if(j-i == 3)   // off diagonal
        return 1;
    if(j-i == 5)   // main diagonal
        return 1;
    return 0;
}

Now the above code returns 0 if there is no conflict and returns 1 if there is conflict. Here, there is no need to check for same row as we will take care of that in main code.

The main code is given below.

int main() {
 int x,y,z,w;
 for(int q1=1;q1<=4;q1++){
     x = q1;
     for(int q2=5;q2<=8;q2++){
         if(!conflict(x,q2)){
             y = q2;
             for(int q3=9;q3<=12;q3++){
                 if(!conflict(x,q3) && !conflict(y,q3)){
                     z = q3;
                     for(int q4=14;q4<=16;q4++){
                         if(!conflict(x,q4) && !conflict(y,q4) && !conflict(z,q4))
                         {
                             w = q4;
                             cout<<x<<" "<<y<<" "<<z<<" "<<w;
                             return 0;
                         }
                     }
                 }
             }
         }
     }
 }
 return 0;
}

Here, we will iteratively place the queens one by one and keep on checking if newly placed queen has position conflicting with previous ones, if there is conflict then we change it’s position and if not, we proceed to place next queen and now this becomes newly placed queen and all others are previously placed, this goes on and on till we find solution.

Complete code is shown below

#include <iostream>
using namespace std;
bool conflict(int i,int j){
    if((j-i)%4==0)
        return 1;
    if(j-i == 3)
        return 1;
    if(j-i == 5)
        return 1;
    return 0;
}
int main() {
 int x,y,z,w;
 for(int q1=1;q1<=4;q1++){
     x = q1;
     for(int q2=5;q2<=8;q2++){
         if(!conflict(x,q2)){
             y = q2;
             for(int q3=9;q3<=12;q3++){
                 if(!conflict(x,q3) && !conflict(y,q3)){
                     z = q3;
                     for(int q4=14;q4<=16;q4++){
                         if(!conflict(x,q4) && !conflict(y,q4) && !conflict(z,q4))
                         {
                             w = q4;
                             cout<<x<<" "<<y<<" "<<z<<" "<<w;
                             return 0;
                         }
                     }
                 }
             }
         }
     }
 }
 return 0;
}

The output for the code is:

2 8 9 15

Here 2,8,9,15 signify the positions on chessboard where queen must be placed and answer for same is shown in figure above (Figure 1). I have taken positions from 1 to 16.

View the code from here: https://ideone.com/H9DXNx

Same idea can be extended for 6-queens problem as well!

#include <iostream>
using namespace std;
 
bool conflict(int i,int j){
    if((j-i)%6==0)
        return 1;
    if(j-i == 5)
        return 1;
    if(j-i == 7)
        return 1;
    return 0;
}
 
int main() {
 int x,y,z,w,p,q;
 for(int q1=1;q1<=6;q1++){
     x = q1;
     for(int q2=7;q2<=12;q2++){
         if(!conflict(x,q2)){
             y = q2;
             for(int q3=13;q3<=18;q3++){
                 if(!conflict(x,q3) && !conflict(y,q3)){
                     z = q3;
                     for(int q4=19;q4<=24;q4++){
                         if(!conflict(x,q4) && !conflict(y,q4) && !conflict(z,q4))
                         {
                             w = q4;
                             for(int q5=25;q5<=30;q5++){
                                 if(!conflict(x,q5) && !conflict(y,q5) && !conflict(z,q5) && !conflict(w,q5)){
                                     p = q5;
                                     for(int q6=31;q6<=36;q6++){
                                         if(!conflict(x,q6) && !conflict(y,q6) && !conflict(z,q6) && !conflict(w,q6) && !conflict(p,q6)){
                                             q = q6;
                                             cout<<x<<" "<<y<<" "<<z<<" "<<w<<" "<<p<<" "<<q;
                                             return 0;
                                         }
                                     }
                                 }
                             }
                         }
                     }
                 }
             }
         }
     }
 }
 return 0;
}

Thanks for reading!! Feedback is always welcomed :)