**Problem description:**

Place the maximum amount of Queens on an N by N chess board and print the possible arrangements

**Solution:**

We will be placing 1 queen at a time per row. We would start from the left most end of the row and move 1 step to the right if there is a collision. We keep doing this till we find a spot that does poses no collisions. If there is no such spot, then one of the previous queens must be moved elsewhere.

**Code:**

[code language="cpp"]

//NQueen problem

#include

using namespace std;

int N;

int Pos=0;

void NQueenDroid(int Board[100], int Remaining)

{

if(Remaining==0)

{

//found a solution

cout<<endl;

for(int i=0;i<N;i++) cout<<Board[i]<<" - ";

Pos++;

return;

}

int Cur= N-Remaining; //placement of current queen

for(int i=0;i<N;i++)

{

bool IsColliding= false;

for(int k=0;k<Cur;k++)

{

//Collision in columns

if(Board[k]==i) {IsColliding=true; break;}

if(abs(Board[k]-i)==abs(Cur-k))

{IsColliding=true; break;} //Collision in diagonals

}

if(IsColliding) continue;

Board[Cur]=i; //place queen

NQueenDroid(Board,Remaining-1);

}

}

int main()

{

N=0;

cout<<"Enter the board size :";

cin>>N;

int Board[100]={0};

NQueenDroid(Board,N);

//End of code

return 0;

}

[/code]

Why the Dynamic Programming tag?It's just the obvious backtracking solution.

ReplyDeleteThanks, updated.

ReplyDelete