Why is the complexity of this solution to the n queens so big?

Question

I am trying to solve the n queens problem using a matrix to represent the chessboard. This is my first solution:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 13

void printTable(int table[N][N], int size)
{
    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            printf("%d ", table[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

bool isSafe(int table[N][N], int row, int column, int size)
{
    // check the main diagonal
    // we add +1 because otherwise we would be comparind against the base
    // element on that line
    for(int i = row + 1, j = column + 1; i < size && j < size; i++, j++)
    {
        if(table[i][j] == 1)
            return false;
    }

    // check the secondary diagonal
    for(int i = row + 1, j = column - 1; i < size && j >= 0; i++, j--)
    {
        if(table[i][j] == 1)
            return false;
    }

    // check the column
    for(int i = row + 1, j = column; i < size; i++)
    {
        if(table[i][j] == 1)
            return false;
    }

    return true;
}

bool isSafeTable(int table[N][N], int size)
{
    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            if(table[i][j] == 1)
            {
                if(!isSafe(table, i, j, size))
                {
                    return false;
                }
            }
        }
    }
    return true;
}

void getQueens(int table[N][N], int size, int queens, int row)
{
    if(queens == size)
    {
        if(isSafeTable(table, size))
        {
            printTable(table, size);
        }
        return;
    }

    for(int i = 0; i < size; i++)
    {
        table[row][i] = 1;
        if(isSafeTable(table, size))
        {
            getQueens(table, size, queens + 1, row + 1);
        }
        table[row][i] = 0;
    }
}

int main()
{
    int table[N][N] =
    {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    getQueens(table, 4, 0, 0);

    return 0;
}

As you can see, I am using a big array of arrays of ints to represent the chessboard. The size of the matrix is 13 x 13. In order to solve the problem with less than 13 queens I work on a subset of that big matrix.

As you can see, I am using the function isSafeTable at each step to check if the chessboard has a valid configuration. If it has, I switch to the next row. If it doesn't, I backtrack.

However, this function isSafeTable has a complexity of O(n^3) (since it calls the isSafe at each iteration). Thus I thought that it will be a wiser decision to mark the used elements and just check if that space is available instead of checking the whole chessboard.

So, I came up with this solution:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 13

void printTable(int table[N][N], int size)
{
    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            printf("%2d ", table[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void _markWith(int table[N][N], int size, int row, int column, int element,
    int specialCharacter)
{
    for(int i = 0; i < size - row; i++)
    {
        int tmp = element;
        // using the specialCharacter we can mark the queens with a different
        // character depeneding on the calling function.
        if(i == 0)
            element = specialCharacter;

        // mark the left diagonal
        if(column - i >= 0)
            table[row + i][column - i] = element;

        // mark the right diagonal
        if(column + i < size)
            table[row + i][column + i] = element;

        // mark the column
        table[row + i][column] = element;

        element = tmp;
    }
}

// This is just a wrapper used to avoid duplicating the code for marking and
// unmarking a table.
void mark(int table[N][N], int size, int row, int column)
{
    _markWith(table, size, row, column, -1, 8);
}

// See the documentation for `mark`.
void unmark(int table[N][N], int size, int row, int column)
{
    _markWith(table, size, row, column, 0, 0);
}

void getQueens(int table[N][N], int size, int queens, int row)
{
    if(queens == size)
    {
        printTable(table, size);
        return;
    }

    for(int i = 0; i < size; i++)
    {
        if(table[row][i] == 0)
        {
            // This function call will result in pruning the column and the
            // diagonals of this element. It actually replaces the 0s with -1s.
            mark(table, size, row, i);

            getQueens(table, size, queens + 1, row + 1  );

            // Now replace the -1s with 0s.
            unmark(table, size, row, i);
        }

    }
}


int main()
{
    int table[N][N] =
    {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    getQueens(table, 11, 0, 0);

    return 0;
}

The functions mark and unmark are used to set the diagonals and the columns of an element to -1. Also, the element (the queen) is marked with an 8 (I thought it will be easier for the human eye to identify the queens this way when printing the matrix).

The function _markWith is used just to avoid rewriting the same code in mark and unmark.

The complexity of these functions is O(n), so the program should move a little bit faster, but it doesn't. The first solution is actually faster than the second one.

Here are some statistics in function of n:

Time taken by both solutions depending on n:

n |  first solution | second solution    
--+-----------------+-----------------    
4 | 0.001s          |  0.002s    
--+-----------------+-----------------    
5 | 0.002s          |  0.001s    
--+-----------------+-----------------    
6 | 0.001s          |  0.002s    
--+-----------------+-----------------    
7 | 0.004s          |  0.003s    
--+-----------------+-----------------    
8 | 0.006s          |  0.011s    
--+-----------------+-----------------    
9 | 0.025s          |  0.133s    
--+-----------------+-----------------    
10| 0.093s          |  3.032s    
--+-----------------+-----------------    
11| 0.581s          |  1m 24.210s

The difference is not that visible for small values of n, but for bigger ones is quite obvious.

Here is the number of recursive calls that each function does depending on n:

n |  first solution | second solution    
--+-----------------+-----------------    
4 | 16              |  16    
--+-----------------+-----------------    
5 | 53              |  65    
--+-----------------+-----------------    
6 | 152             |  514    
--+-----------------+-----------------    
7 | 551             |  7085    
--+-----------------+-----------------    
8 | 2 056           |  129 175    
--+-----------------+-----------------    
9 | 8 393           |  2 810 090    
--+-----------------+-----------------    
10| 35 538          |  70 159 513    
--+-----------------+-----------------    
11| 16 695          |  1 962 694 935

As you can see, the number of recursive calls increases exponentially in the second solution. So the functions mark and unmark are not responsible for the slow way the program moves.

I have spent this day trying to find why the second solution does so many recursive calls compared to to the first one, but I was not able to came up with an answer.

Can you help me?

Answer 1

The second solution is wrong. It outputs more solutions than normal. For example, for N = 5, it outputs (among others):

 8  0  0  0  0
-1 -1  0  0  8
-1  0  8 -1 -1
 8 -1 -1 -1 -1
-1 -1 -1  8 -1

 0  0  0  8  0
 0  8 -1 -1 -1
-1 -1 -1 -1  8
 8 -1  0 -1 -1
-1 -1 -1  8 -1

The reason is your marking code:

if(table[row][i] == 0)
{
      // This function call will result in pruning the column and the
      // diagonals of this element. It actually replaces the 0s with -1s.
      mark(table, size, row, i);

      getQueens(table, size, queens + 1, row + 1  );

      // Now replace the -1s with 0s.
      unmark(table, size, row, i);
}

Think about what happens to a cell attacked by two queens: you will mark it when placing the first queen, make a recursive call (or more, doesn't matter), mark it again, then unmark it when returning from the second recursive call. Then you will forget that the queen placed during the first recursive call is still attacking it.

Note that in each of the wrong solutions above, one of the queens that is wrongly placed is attacked by two others, and it was also placed before the two others that are attacking it.

Obviously, this leads the algorithm to find more solutions, hence more recursive calls.

The classic solution

The proper way to solve the problem is by using the algorithm to generate permutations. Let:

col[i] = the column of the queen placed on row i

Then you need to generate valid permutations in the col array. I'll leave the necessary conditions as an exercise.

Of course, you might also be able to fix your approach by incrementing and decrementing a counter instead of using just 1/0.