A problem I was given requires us to solve using a backtracking style algorithm. I wrote one based upon a given solution to a similar problem, but I need it to be faster (run all test cases in under 3 seconds.)

The problem statement is as follows:

Given two numbers n and k, determine the number of ways one can put k bishops

on an n × n chessboard so that no two of them are in attacking positions.

The input file may contain multiple test cases. Each test case occupies a single line in

the input file and contains two integers n(1 ≤ n ≤ 8) and k(0 ≤ k ≤ n2).

A test case containing two zeros terminates the input.

Here is what I have so far:

```
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 8
long long solution_count;
void construct_candidates (int bishops [], int c, int n, int candidates [],
int * ncandidates)
{
bool legal_move;
int start = 0;
if (c)
start = bishops [c-1];
* ncandidates = 0;
for (int p = start; p <n * n; p ++)
{
legal_move = true;
for (int j = 0; j <c; j ++)
if (abs (bishops [j]/n-p/n) ==
abs (bishops [j]% n-p% n))
{
legal_move = false;
break;
}
if (legal_move == true)
candidates [(* ncandidates) ++] = p;
}
}
void backtracking (int bishops [], int c, int n, int k)
{
if (c == k)
solution_count ++;
else
{
int ncandidates;
int candidates [MAXN * MAXN];
construct_candidates (bishops, c, n, candidates, & ncandidates);
for (int i = 0; i <ncandidates; i ++)
{
bishops [c] = candidates [i];
backtracking (bishops, c + 1, n, k);
}
}
}
long long little_bishops_by_backtracking (int n, int k)
{
int bishops [2 * (MAXN-1) + 1];
solution_count = 0;
backtracking (bishops, 0, n, k);
return solution_count;
}
int main (int ac, char * av [])
{
int n, k;
while (cin >> n >> k, n || k)
cout << little_bishops_by_backtracking (n, k) << endl;
return 0;
}
```

Can anyone help me try to speed this up? Is there a better way to eliminate more candidate solutions faster?

Source: Windows Questions C++