N – QUEEN Backtracking problem solved


This all started when I started doubting my coding and downloaded the code from geeksforgeeks for this N-Queen problem. I told one of my friends that I am gonna read it and understand. Then he told me that the problem is quite easy to code, just see the wiki (actually he and me were interested more in the animation on that page ;)

Anyhow the wiki pages : Eight Queen , Backtracking were not of much use as they were not giving good pseudo code. But this here, see it and try to think, what all can I need for the N – Queen problem..

Enough of waiting now, here is the C++ code for the problem I wrote.

#include<iostream>
using namespace std;

/** this is the size of chess board */
#define N 8

/** Given a completed board, this prints it to the stdout */
void print_solution(int state[N][N])
{
int i,j;
for(i=0; i<N; ++i)
{
for(j=0; j<N; ++j)
cout<<state[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}

/** return true if placing a queen on [row][col] is acceptable
else return false */
bool accept(int state[N][N], int row, int col)
{
int i,j;

/* check the column */
for (i=0; i<N; ++i)
{
if (state[row][i])
return false;
}

/* check the row */
for (i=0; i<N; ++i)
{
if (state[i][col])
return false;
}

/* check the upper left diagnol */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (state[i][j])
return false;
}

/* check the lower left diagnol */
for (i = row, j = col; i < N && j >= 0; ++i, --j)
{
if (state[i][j])
return false;
}

/* check the upper right diagnol */
for (i = row, j = col; i >= 0 && j < N; i--, ++j)
{
if (state[i][j])
return false;
}

/* check the lower right diagnol */
for (i = row, j = col; i < N && j < N; ++i, ++j)
{
if (state[i][j])
return false;
}

/* return true if all tests passed */
return true;
}

void solve_state(int state[N][N], int row)
{
int i;

/* if all queens have been placed at non conflicting positions */
if (row == N)
{
print_solution(state);
return;
}

/* Place queens on all positions in a given row and
check if the state is acceptable
Continue the process till all possibilities found */
for(i=0; i<N; ++i)
{
if(accept(state, row, i))
{
state[row][i] = 1;
solve_state(state, row+1);
}
state[row][i] = 0;
}
}

int main()
{
/* initialise the board */
int state[N][N] = {0};

solve_state (state, 0);

return 0;
}

This code can be easily converted to C, just make amendments to bool values. Rest of the program deals with the board matrix, so C won’t have problems.

Result: Backtracking is pretty easy if you get the idea.

About these ads
Explore posts in the same categories: C++

Tags: , , ,

You can comment below, or link to this permanent URL from your own site.

2 Comments on “N – QUEEN Backtracking problem solved”

  1. techmyway Says:

    Again, white spaces lost..
    anyways better: https://gist.github.com/1351828
    I love u github.. :)


  2. […] I found a code example here: N-QUEEN Backtracking problem solved […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: