Skip to main content

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[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]

Comments

Post a Comment

Popular posts from this blog

GraphQL

GraphQL



What is GraphQL

It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think of it is an as a complimentary of REST/RPC.

Now head here and read the original graphQL documentation. It will take 2-3 hours tops but is a worthy read. This will help you build some impressions on it and help contrast against mine below:


Why use GraphQL

Core advantage

Instead of defining custom backend rpc/rest endpoints for every data-shape, graphql allows you to build a more general endpoint which give frontend/mobile engineers freedom and query and play with the data. It might be less efficient, add a bit more complexity (need for things like data-loader), harder to standardize and control client-contracts for. What it looses in complexity and control, it gains in flexibility and freedom - provided your data model is worth of a graphql-ish query How to tell if my data-model graphql-ish?Are there complex relationships between your models? Is there a need …

About me

Hi,

I'm currently working as a software developer in the logistics industry in San Francisco. 
My aim is to impact billions of people's live for the better and make the world a better place.

Cheers,
Vignesh



Backend - Tech refresher 2019

Hello there

As a software engineer, it is important to keep updating your skillsets by learning the latest programming-elements (includes paradigms, patterns, languages, tools and frameworks). This becomes a bit easy if you already working on the cutting edge of something. Even then, it is possible to go too deep and loose breadth.

I've taken upon myself to do a tech refresher every year. The intent is to read, experiment and understand these elements by spending anywhere between 4 days to 4 weeks. The ultimate goal is: "do I know most that I need to know to build a planet-scale backend tech-stack ground up"

I'll write up my learnings in posts to help myself (and maybe others) refer it.

Here is the initial list I'm thinking about:


RedisMySQL, GraphQLAurora, Mesos, KubernetesCadence, SWSCassandra, MangoDB, NoSQL, MySQL, Spanner, S<, DynDBELKFlink, Storm, Samza, SparkHadoop HDFS, Yarn, MapReduceHive, HBaseKafka, ZookeeperNW: http, Tcp, thrift, grpc, yarpc, Terraform,…