I'm tryng to implement Sosic and Gu algorithm for the n-queens problem-which presents a phase of initialization called initial_search().
The algorithm starts by assigning queens to random positions on the chessboard within a limited number of attempts (controlled by the loop with int(3.08 * n) iterations). For each queen placement attempt, it checks if there are any immediate collisions with previously placed queens using the partial_collision function. If a collision is detected, the algorithm retries the placement with a different random position until a valid placement is found. This step aims to distribute queens across the board while minimizing initial collisions. I'm finding problems with the implementation of partial_collision(): in the article they say it should cost O(1) however i can't find a way to use the diagonal arrays to check only the columns on the left (in fact the function total_collision() is O(1)).
import random
def queen_search(queens):
while True:
nd, pd = initialize_diagonal_arrays(len(queens))
k = initial_search(queens, nd, pd)
if len(queens) > 200:
final_search(queens, k, nd, pd)
break
else:
final_search_reduced(queens, k, nd, pd)
if board_collision(queens) == 0:
break
def initial_search(queens, nd, pd):
n = len(queens)
queens[:] = list(range(n))
update_diagonal_arrays(queens, nd, pd)
j = 0
# place queens without collisions
for i in range(int(3.08 * n)):
if j == n:
break
m = random.randint(j, n - 1)
swap(queens, j, m, nd, pd)
if partial_collision(queens, j) == 0:
j += 1
else:
swap(queens, j, m, nd, pd)
# place queens with possible collisions
for i in range(j, n):
m = random.randint(i, n - 1)
swap(queens, i, m, nd, pd)
# return the number of queens with possible collisions
return n - j
def final_search(queens, k, nd, pd):
n = len(queens)
it = 0
for i in range(n - k, n):
if total_collisions(queens, i, nd, pd) > 0:
while it < 7000:
j = random.randint(0, n - 1)
swap(queens, i, j, nd, pd)
b = (total_collisions(queens, i, nd, pd) > 0) or (total_collisions(queens, j, nd, pd) > 0)
if b:
swap(queens, i, j, nd, pd)
it += 1
else:
break
def final_search_reduced(queens, k, nd, pd):
n = len(queens)
for i in range(n - k, n):
if total_collisions(queens, i, nd, pd) > 0:
for j in range(n):
swap(queens, i, j, nd, pd)
b = (total_collisions(queens, i, nd, pd) > 0) or (total_collisions(queens, j, nd, pd) > 0)
if b:
swap(queens, i, j, nd, pd)
else:
break
# auxiliary functions
def initialize_diagonal_arrays(n):
neg_diagonal = [0] * (2 * n - 1)
pos_diagonal = [0] * (2 * n - 1)
return neg_diagonal, pos_diagonal
def update_diagonal_arrays(queens, neg_diagonal, pos_diagonal):
n = len(queens)
for i in range(len(queens)):
neg_diagonal[i + queens[i]] += 1
pos_diagonal[i - queens[i] + n - 1] += 1
def swap(queens, a, b, neg_diagonal, pos_diagonal):
original_a, original_b = queens[a], queens[b]
queens[a], queens[b] = queens[b], queens[a]
neg_diagonal[a + original_a] -= 1
neg_diagonal[b + original_b] -= 1
pos_diagonal[a - original_a + len(queens) - 1] -= 1
pos_diagonal[b - original_b + len(queens) - 1] -= 1
neg_diagonal[a + queens[a]] += 1
neg_diagonal[b + queens[b]] += 1
pos_diagonal[a - queens[a] + len(queens) - 1] += 1
pos_diagonal[b - queens[b] + len(queens) - 1] += 1
def partial_collision(queens, i):
return sum(1 for j in range(i) if (i - j) == abs(queens[i] - queens[j]))
def total_collisions(queens, i, neg_diagonal, pos_diagonal):
n = len(queens)
return neg_diagonal[i + queens[i]] + pos_diagonal[i - queens[i] + n - 1] - 2 # Exclude self-collision
def board_collision(queens):
return sum(partial_collision(queens, i) for i in range(len(queens)))
You don't need a separate partial_collision implementation, as you can rely on total_collisions. The latter will look at the occupation on the diagonals, and that works also when you have not placed all queens yet.
In board_collisions I would even look directly at your diagonal counters to see if any of them is greater than 1.