Time complexity of N Queens bruteforce algorithm

Question

I'm solving Big O runtimes but do not feel as though I understand the problem thoroughly enough to answer on my own.

I need to calculate the Big-O runtime for this queens 'bruteforce' function, but I'm not sure I have solved it correctly. I thought it could be simply O(n^2) but I am not sure and not confident enough with my current understanding to say that is the correct answer. I'm just looking for some guidance and correction.

def bruteforce(self, row):
    if row == self.n:
        return self.is_valid(row)

    for col in range(self.n):
        self.queens[row] = col
        if self.bruteforce(row + 1):
            return True
        self.queens[row] = -1

    return False

Answer 1

The N-Queen problem is a highly known problem for its time complexity.

---

Exact enumeration

According to wiki, "the 27×27 board is the highest-order board that has been completely enumerated".

n   fundamental all
1   1   1
2   0   0
3   0   0
4   1   2
5   2   10
6   1   4
7   6   40
8   12  92
9   46  352
10  92  724
11  341 2,680
12  1,787   14,200
13  9,233   73,712
14  45,752  365,596
15  285,053 2,279,184
16  1,846,955   14,772,512
17  11,977,939  95,815,104
18  83,263,591  666,090,624
19  621,012,754 4,968,057,848
20  4,878,666,808   39,029,188,884
21  39,333,324,973  314,666,222,712
22  336,376,244,042 2,691,008,701,644
23  3,029,242,658,210   24,233,937,684,440
24  28,439,272,956,934  227,514,171,973,736
25  275,986,683,743,434 2,207,893,435,808,352
26  2,789,712,466,510,289   22,317,699,616,364,044
27  29,363,495,934,315,694  234,907,967,154,122,528

---

Total Number of Actual Possibilities

The actual number of permutations of placing N Queens in the N rows (or columns, whichever you prefer), is N!:

• In the first row or column, you can place one queen in any cell you want, which is N cells.

• In the second row or column, you can place one queen in N - 1 cells, excluding the one you just placed in the first row or column.

• In the third row or column, you can do the same in the N - 2 cells.

In short:

row 1: N options or choices for placing a queen

row 2: N - 1 options or choices for placing a queen

row 3: N - 2 options or choices for placing a queen

.
.
.

row N: 1 option or choice for placing the last queen

Total number of possibilities: N * (N - 1) * (N - 2) * (N - 3) * ... * 1 = N!

---

Time Complexity

• The time complexity of the brute force N-Queen could be O(N ^ N) or O(N!), depending on the brute force implementations.

• In this specific implementation, since we did not add an if to check that if a queen is placed in the i row, therefore we can safely say that the time complexity is O(N ^ N), (as commented by no-comment and Ry-). This makes our approach a "complete" naive approach.

• If we had an if check, then the time complexity would be equal to the number of N! possibilities.

---

Brute Force Code

from math import factorial


class Solution:
    def __init__(self, n):
        self.n = n
        self.queens = [-1] * n
        self.val = 0
        self.bf = 0

    def is_valid(self):
        for i in range(self.n):
            for j in range(i):
                self.val += 1
                if self.queens[i] == self.queens[j] or abs(self.queens[i] - self.queens[j]) == i - j:
                    return False
        return True

    def bruteforce(self, row=0):
        self.bf += 1
        if row == self.n:
            return self.is_valid()

        for col in range(self.n):
            self.queens[row] = col
            if self.bruteforce(row + 1):
                return True
            self.queens[row] = -1

        return False

    def get_solution(self):
        if self.bruteforce():
            return self.queens
        else:
            return None

    def get_operations(self):
        return self.bf, self.val

    def get_factorial(self):
        return factorial(self.n)


Sol = Solution(8)
print(Sol.get_solution())
print(Sol.get_operations())
print(Sol.get_factorial())

Prints

[0, 4, 7, 5, 2, 6, 1, 3]
(1485549, 3707836)
40320

---

Backtracking

A more efficient way to solve the N Queen problem is backtracking:

def solution(n):
    def can_place_queen(row, col):
        for i in range(row):
            if board[i] == col or board[i] - i == col - row or board[i] + i == col + row:
                return False

        return True

    def _set_queen(n, row):
        if n == row:
            res.append(board[:])
            return

        for col in range(n):
            if can_place_queen(row, col):
                board[row] = col
                _set_queen(n, row + 1)
                board[row] = 0

    res = []
    board = [0] * n
    _set_queen(n, 0)

    return [[i + 1 for i in sol] for sol in res]


print(solution(6))

Prints

[[2, 4, 6, 1, 3, 5], [3, 6, 2, 5, 1, 4], [4, 1, 5, 2, 6, 3], [5, 3, 1, 6, 4, 2]]

---

Backtracking illustration:

Ref