N-Queens problem is another classical combinatorial problem, proposed by German chess enthusiast Max Bezzel in 1848. The problem follows the rules of chess, to place n queens on an n x n chessboard so that no two queens can attack each other. That is, no two queens on the chessboard are in the same row, column, or diagonal.
The problem can be easily solved by recursion. Since no two queens can be placed on the same row, the problem can be divided into n subproblems for each of the (n - r) rows, where r stands for the number of rows that are filled with queens. The algorithm starts from the first row. For each column in the row, try to place the queen while not violating the rules. The next move can be viewed as another n-queens problem for the rest of the rows. The implementation detail is displayed below:
def queens(Q, r, s):
"""
Q is the array of length n that represents the chessboard:
each element of index i represent the position of the queen on
ith row.
r is an integer representing the fulfilled rows, initialized with 0.
"""
n = len(Q)
P = []
for q in Q:
P.append(q)
for i in range(n): # columns
legal = True
for j in range(r): # filled rows
if i == Q[j]:
legal = False
# Get rid of diagonal cases
if i == Q[j] - r + j or i == Q[j] + r - j:
legal = False
if legal:
P[r] = i
queens(P, r + 1, s)
if r == n - 1: # only when the board is completely filled
s.append(P)
Note that each position is marked with a "legal" flag and the problem is only passed into subproblems if the current position of the queen is legal. This specific function passes down set variable s, which contains all possible queen positions for the chessboard. For the Master Theorem evaluation of time complexity, this algorithm has n subproblems, where each subproblem has size of (n - 1), and extra work is n2, results in
which evaluates to be O(n!).
Currently, there are ample well-designed algorithms that achieve much lower time and space complexity, as shown in following table from Google's N-Queens solver:
Since each row can only be filled with one queen, it is also possible to directly use permutation to help to solve the problem: with random permutations, check if there are violations on the board. If not, return or append the result.
def comparison_perm_queen_search(n):
t = 1
Q = range(n)
while t > 0:
random.shuffle(Q)
t = 0
for i in range(n):
for j in range(i + 1, n):
if Q[i] + i == Q[j] + j or Q[i] - i == Q[j] - j: # on diagonal
t += 1
return Q
A smarter way to use permutation is described by this paper, which is published in the 1990's by the University of Utah. The difference is that in the case of rule violations, it checks whether swapping the position of queens for conflicting rows reduces the number of violations in total; if so, then make the swap. This is a gradient based heuristic search, which achieves O(n3) time complexity.
def fast_queen_search(n):
"""
A faster gradient heuristic search for N-queens problem;
Only returns one solution.
"""
t, c = 1, 1
Q = range(n)
while c > 0:
random.shuffle(Q)
c, t = 0, 0
for i in range(n):
for j in range(i + 1, n):
if Q[i] + i == Q[j] + j or Q[i] - i == Q[j] - j: # on diagonal
t += 1
if t > 0:
for i in range(n):
for j in range(i + 1, n):
P = []
for q in Q:
P.append(q)
if need_swap(Q, i, j, t):
s = Q[i]
Q[i] = Q[j]
Q[j] = s
c += 1
return Q
def need_swap(P, i, j, x):
"""
Check if swap Qi and Qj reduces total number of collision; if
it does then swap Qi and Qj.
"""
t = 0
c = P[i]
P[i] = P[j]
P[j] = c
for i in range(len(P)):
for j in range(i + 1, len(P)):
if P[i] + i == P[j] + j or P[i] - i == P[j] - j:
t += 1
if t < x:
return True
else:
return False
To make the efficiency clear, I tried all three algorithms and plotted the result on log scale running time, where the x-axis represents the size of the chessboard, from 4 to only 13, since the brute-force recursion cannot finish in reasonable time above 13.
