## 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.

**Explore posts in the same categories:**C++

**Tags:** backtracking, C, c++, N queen

November 9, 2011 at 9:13 PM

Again, white spaces lost..

anyways better: https://gist.github.com/1351828

I love u github.. :)

March 6, 2013 at 5:35 AM

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