## Tuesday, April 5, 2011

### The Eight-Queens Problem with Backtracking

This is the general idea and template code for backtracking to solve the eight-queens problem.
/**
*
* N Queens Problem:
* On the two dimension plane, each queen could be numbered from 1 to n.
* This means that no two queensmay lie on the same row, column or diagonal.
* Note that there must be exactly one queen per row for an n-queens solution.
* Thus, we could simplify this problem to a permutation of n elements.
* In other words, the n columns of a complete solution must form a permutation of n elements.
*
*/
#include<iostream>
#include<math.h>
using namespace std;
const int MMAX = 1000;
long count;

/**
* If this is a complete solution. The previous n elements satisfy the conditions.
*/
bool is_a_solution(long k, long n)
{
return (k == n);
}

/**Inc the counter.
*/
void process()
{
count++;
}

void construct_candidates(long *a, long k, long n, long *c, long &ncandidates)
{
long i, j;
bool legal_move; //If position is a candidate;
ncandidates = 0; // # of candidates;
for (i = 1; i <= n; i++) //For each row, n cols could be choosn.
{
legal_move = true;
for (j = 1; j < k; j++)
{
/**
* If they are in a diagnal row.
* jth row: queen(j, a[j]);
* kth row: queen(k, i)
*/
if (abs(k - j) == abs(i - a[j]))
legal_move = false;
else if (i == a[j])     //If they are in the same cols.
legal_move = false;
}
if (legal_move == true)
{
c[ncandidates] = i;
ncandidates = ncandidates + 1;
}
}
}

void backtrack(long *a, long k, long n)
{
long c[MMAX];
long ncandidates;
long i;
if (is_a_solution(k, n))
process();
else
{
k++;
construct_candidates(a, k, n, c, ncandidates);
for (i = 0; i < ncandidates; i++)
{
a[k] = c[i];    //Chech every candidate.
backtrack(a, k, n);
}
}
}

int main()
{
long a[MMAX], n;
while (cin >> n)
{
if (n == 0) break;
count = 0;
backtrack(a, 0, n);
cout << "n=" << n << " solution_count=" << count << endl;
}
return 0;
}