N-queen problem

Here is the solution for N-queen problem. N-queen problem is the classic example of backtracking algorithm. The problem statement is as follows :-
Given an N*N chessboard, place N queens on the chessboard such that no queen is attacking any other queen.
e.g. Here is a one such arrangement for N=8.





This is how the problem is solved using c program.
We will have an array of n integers say Chess[N]. Now Chess[i] saves the column position of a queen which is in row i. We start with Chess[0] =0, i.e. by considering zeroth position for queen in row zero. Next we consider position of queen in column 1. We will start by putting values of Chess[1] from 0 and check if it is proper position. If it is not proper position we will increment Chess[1] by 1 and check again. Continue this till we get proper position for Chess[1]. Next we will move to Chess[2] and so on. At any time we will have to check position of ith row only with respect to 0 to i-1th row.

In the program instead of array we have used the String of length N. The ith character denotes the position of queen in row i. With this the only changes we need from super solution is to change check and print. 'print' will display the solutions in the entire N * N chessboard. Check(n) will check whether queen at row n is attacking any queen from row 0 to n-1.

Download the program from here :-
http://rapidshare.com/files/151974397/Nqueen.cpp.html

The ourput when NUMBER is 4 is as shown :-

x  Q  x  x
x  x  x  Q
Q  x  x  x
x  x  Q  x

x  x  Q  x
Q  x  x  x
x  x  x  Q
x  Q  x  x

Number of solutions 2