#### How to speed up backtracking algorithm?

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++