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?
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
- 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 𝑛.
- Otherwise, write separate lists of even and odd numbers (2, 4, 6, 8 – 1, 3, 5, 7).
- If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (3, 1, 7, 5).
- 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).
- Append odd list to the even list and place queens in the rows given by these numbers, from left to right [...].
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.