Implementing a Python algorithm for solving the n-queens problem efficiently

Question

I am working on a project that requires me to solve the n-queens problem efficiently using Python. I have already implemented a basic recursive algorithm to generate all possible solutions, but I am looking for ways to optimize the code to handle larger values of n (i.e., n >= 20) without causing a stack overflow or taking an unreasonable amount of time to run.

My current algorithm works by generating all possible permutations of the n queens on an n x n chessboard and then checking each permutation to see if it is a valid solution. However, this approach quickly becomes computationally expensive for larger values of n.

I have read about techniques such as backtracking, pruning, and bit manipulation that can be used to optimize this problem, but I am not sure how to implement them in Python. Can someone provide an efficient algorithm for solving the n-queens problem in Python, along with a detailed explanation of how it works and why it is efficient? Also, how can I handle cases where n is very large, such as n = 100 or more?

Answer 1

Wikipedia's article on Eight queens puzzle gives a greedy algorithm for any (greater than 3):

If the goal is to find a single solution, one can show solutions exist for all ≥ 4 with no search whatsoever. These solutions exhibit stair-stepped patterns.

[...]

One approach is

1. If the remainder from dividing by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd numbers not greater than .
2. Otherwise, write separate lists of even and odd numbers (2, 4, 6, 8 – 1, 3, 5, 7).
3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (3, 1, 7, 5).
4. If the remainder is 3, move 2 to the end of even list and 1, 3 to the end of odd list (4, 6, 8, 2 – 5, 7, 9, 1, 3).
5. Append odd list to the even list and place queens in the rows given by these numbers, from left to right [...].

Implementation

Here is an implementation in Python of the above algorithm. It first defines some constants depending on mod 6, and then constructs the solution from ranges whose boundaries are derived from these constants. The solution is run for several values of , and each is verified with a naive check:

def nQueens(n):
    if n > 3:  # Otherwise no solution possible
        a, b, c = ((1,0,0), (1,0,0), (1,6,4), (3,4,0))[(n % 6) % 4]
        return [*range(a, n, 2), *range(a - 2, 0, -2), *range(c - 2, -1, -2), 
                *range(b, n, 2), *range(c, b, 2)]

def assertQueensDontAttack(n, solution):
    if len(solution) != n:
        raise ValueError("number of queens is wrong")
    if len(set(solution)) != n:
        raise ValueError("multiple queens on same row")
    if list(sorted(solution)) != list(range(n)):
        raise ValueError("row(s) out of range")
    if len(set((i + j for j, i in enumerate(solution)))) != n:
        ValueError("multiple queens on same backward diagonal (\\)")
    if len(set((i - j for j, i in enumerate(solution)))) != n:
        ValueError("multiple queens on same forward diagonal (/)")

for n in range(4, 40):
    solution = nQueens(n)
    print(solution)
    assertQueensDontAttack(n, solution)
    
print("all tests passed")

This outputs:

[1, 3, 0, 2]
[1, 3, 0, 2, 4]
[1, 3, 5, 0, 2, 4]
[1, 3, 5, 0, 2, 4, 6]
[1, 3, 5, 7, 2, 0, 6, 4]
[3, 5, 7, 1, 4, 6, 8, 0, 2]
[1, 3, 5, 7, 9, 0, 2, 4, 6, 8]
[1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10]
[1, 3, 5, 7, 9, 11, 0, 2, 4, 6, 8, 10]
[1, 3, 5, 7, 9, 11, 0, 2, 4, 6, 8, 10, 12]
[1, 3, 5, 7, 9, 11, 13, 2, 0, 6, 8, 10, 12, 4]
[3, 5, 7, 9, 11, 13, 1, 4, 6, 8, 10, 12, 14, 0, 2]
[1, 3, 5, 7, 9, 11, 13, 15, 0, 2, 4, 6, 8, 10, 12, 14]
[1, 3, 5, 7, 9, 11, 13, 15, 0, 2, 4, 6, 8, 10, 12, 14, 16]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 0, 2, 4, 6, 8, 10, 12, 14, 16]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 0, 6, 8, 10, 12, 14, 16, 18, 4]
[3, 5, 7, 9, 11, 13, 15, 17, 19, 1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 0, 2]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 0, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 4]
[3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 0, 2]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 2, 0, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 4]
[3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 0, 2]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 2, 0, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 4]
[3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 0, 2]
all tests passed

NB: a number at index means there is a queen at (, ), and these coordinates are 0-indexed.