How to speed up backtracking algorithm?

Question

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?