## Tuesday, July 9, 2013

### N Queens problem

Well, I can't possibly have an 'algorithm of the day' thread without solving the all famous N QUEENs problem.

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, int Remaining)
{
if(Remaining==0)
{
//found a solution
cout&lt;&lt;endl;
for(int i=0;i&lt;N;i++) cout&lt;&lt;Board[i]&lt;&lt;" - ";
Pos++;
return;
}

int Cur= N-Remaining; //placement of current queen
for(int i=0;i&lt;N;i++)
{
bool IsColliding= false;
for(int k=0;k&lt;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&lt;&lt;"Enter the board size :";
cin&gt;&gt;N;
int Board={0};
NQueenDroid(Board,N);

//End of code
return 0;
}

[/code]

1. 2. 