0
$\begingroup$

N-Queens problem - maximum number of function calls.

We say, that a backtracking algorithm (code below) 'checks' a setup of N queens, when the function isFree(n-1, y) is called for $0\leq y < n$ (so we check a possibility of placing n-th queen to already set n-1 queens). Justify that for $n\geq 4$ algorithm checks no more than $(\frac{n}{2}+1)\cdot n!$ different setups of n queens on the board. We may assume that there exists a solution for $n\geq 4$.

int queens()
{
    int k; // column
    b[0] = 0; // put a queen in the left-bottom corner
    k = 1; // move to column number 1
    while (k < n && k >= 0)
    {
        do // looking for a "free" square in column k, going up b[k]
        {b[k]++;}
        while(b[k] < n && !isFree(k,b[k]));

        if (b[k] < n) k++; // free square found
        else {b[k] = -1; k--;} // none free squares, move back to earlier column
    }

    return k; // if k=n solution found, k=-1 if there is no solution
}

At the first look, the exercise looked pretty simple to me and my solution was based on the time complexity and the symmetry of chessboard.

As we proved on the lecture, algorithm works in $O(n\cdot n!)$. I noticed that if there exists a solution for N-Queens problem, there has to be a symmetric solution, just as we "flip" the board. Using an assumption that for $n\geq 4$ the problem has a solution, it is enough to check solutions only up to $(\frac{n}{2}+1)$-th grid, because it is the middle of the board. That means: for even $n$ we check solutions up to the $(\frac{n}{2})$-th grid and for odd $n$ up to $(\frac{n}{2}+1)$-th. Then, we know that we will have a solution before we cross the middle of the board.

What I think about my answer is that it is pretty understandable and correct, as we have the time complexity and I can base my answer on it, lowering the number of solutions we have to check.

How else could I justify that the algorithm works no more than $(\frac{n}{2}+1)\cdot n!$ times, having in mind that my explanation was "not good enough" (as my teacher said)?

$\endgroup$
  • $\begingroup$ "That means: for even $n$ we check solutions up to the $(\frac{n}{2})$-th grid and for odd $n$ up to $(\frac{n}{2}+1)$-th." Have you actually implemented that logic? Please tell us how. $\endgroup$ – Apass.Jack Jan 11 at 1:02
  • $\begingroup$ When you take a look at solutions for n = 4, it will be "1302" (each number means a row in a column) and if you would start the algorithm from the top row, it would find "2031", which would still mean it did not cross the middle grid. Similarly for n = 5, but then the middle is the 3rd row. $\endgroup$ – whiskeyo Jan 11 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.