N-Queens Problem (Backtracking Method)

Determine number of ways to place n queens on an n x n chess board so that no queen threatens any other.

Number rows and columns of the board by 1...n. Use an array x[1...n], with x[i] containing the column number j of the queen in row i.

Obviously, in any solution to the n-Queens problem, there is exactly one queen in each column. So we will represent our possible solutions using an array x[1.. n], where x[i] indicates the square in column i that contains a queen, or 0 if no queen has yet been placed in column i. To find a solution, we will put queens on the board row by row, starting at the top.

A partial solution is an array x[1.. n] whose first r - 1 entries are positive and whose last n - r + 1 entries are all zeros, for some integer r. The following recursive algorithm recursively enumerates all complete n-Queens solutions that are consistent with a given partial solution. The input parameter r is the first empty row. Thus, to compute all n-Queens solutions with no restrictions, we would call NQueens(1, n).

---

Algorithm

---

This algorithm is called with parameters k=1 and n, i.e. NQueens(1, n).

Algorithm NQueens (k, n)
{
    for i:=1 to n do
        if Place(k,i) then
        {
            x[k]:=i;
            if (k=n) then 
                write (x[1:n])
            else
                NQueens(k+1, n);
        }
    return true;
}

The following function returns true if a queen can be placed at [k, i] position. Here, x[] is a global array whose first (k-1) values have been set. Abs(r) returns the absolute value of r.

Algorithm Place (k, i)
{
    for j:=1 to k-1 do
        if ((x[j]=i) or (Abs(x[j]-i)=Abs(j-k)))
            return false;
    return true;
}

---

Implementation of N-Queens Problem using C Programming Language

#include <stdio.h> #include <math.h> int x[16], count; void nqueen(int row, int n); int place(int row, int column); void print(int n); int main() { int n, i, j; printf("\nEnter number of Queens:"); scanf("%d", &n); nqueen(1, n); return 0; } void nqueen(int row,int n) { int column; for(column=1;column <= n;++column) { if(place(row,column)) { x[row]=column; if(row==n) print(n); else nqueen(row+1,n); } } } int place(int row,int column) { int i; for(i = 1; i <= row - 1; ++i) { if(x[i] == column) return 0; else if(abs(x[i]-column)==abs(i-row)) return 0; } return 1; } void print(int n) { int i, j; printf("\n %d:\n", ++count); for(i = 1; i <= n; ++i) printf("\t%d", i); for(i = 1; i <= n; ++i) { printf("\n%d", i); for(j = 1; j <= n; ++j) { if(x[i] == j) printf("\tQ"); else printf("\t-"); } } }

---

Happy Exploring!