"""
queens.py: Tabu search for the n-queens problem
The problem consists of finding the positions of n queens on an n x n
chess board, in such a way that none of them is able to capture any
other. The moves of a queen on a chess board are through horizontal
and vertical lines, and on diagonals. Therefore, there can not be
more than one queen on the same row, on the same column, or on the
same diagonal (either ascending or descending).
This file contains a set of functions to illustrate how to use tabu
search for solving this problem.
For having no rook attacks, there cannot be more that one queen on
each row, and no more that one queen on each column. In other words,
there must be exactly one queen on each row and on each column.
With this in mind, the position of the queens is hold in an array with
size n, with each element being a different integer from 0 to n-1. The
i-th element of the array corresponds to the queen of row i (starting
from row 0). The integer contained on the i-th element of the array
corresponds to the column on which the queen in row i is.
Solution construction is random (using a permutation), and the
neighborhood for local search consists of solutions with the column
of two queens exchanged.
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2007
"""
import random
def display(sol):
"""Nicely print the board with queens at positions given in sol"""
n = len(sol)
for i in range(0,n):
for j in range(0,n):
if sol[i] == j:
print 'o',
else:
print ".",
print
def diagonals(sol):
"""Determine number of queens on each diagonal of the board.
Returns a tuple with the number of queens on each of the upward
diagonals and downward diagonals, respectively
"""
n = len(sol) # size of the board
ndiag = 2*n-1 # number of diagonals in the board
# upward diagonals (index 0 corresponds to the diagonal on upper-left square)
diag_up = [0 for i in range(ndiag)]
# downward diagonals (index 0 corresponds to the diagonal on upper-right square)
diag_dn = [0 for i in range(ndiag)]
# count the number of times each diagonal is being attacked
for i in range(n):
# upward diagonal being attacked by
# the queen in row i (which is in column sol[i])
d = i + sol[i] # index of diagonal
diag_up[d] += 1
# downward diagonal being attacked by
# the queen in row i (which is in column sol[i])
d = (n-1) + sol[i] - i # index of diagonal
diag_dn[d] += 1
return diag_up, diag_dn
def collisions(diag):
"""Returns the total number of collisions on the diagonal."""
ncolls = 0
for i in diag:
if i>1: # i.e., more that one queen on this diag
ncolls += i-1
return ncolls
def exchange(i, j, sol, diag_up, diag_dn):
"""Exchange the queen of row i with that of row j; update diagonal info."""
n = len(sol)
# diagonals not attacked anymore
d = i + sol[i]; diag_up[d] -= 1
d = j + sol[j]; diag_up[d] -= 1
d = (n-1) - i + sol[i]; diag_dn[d] -= 1
d = (n-1) - j + sol[j]; diag_dn[d] -= 1
# exchange the positions 'i' and 'j'
sol[i], sol[j] = sol[j], sol[i]
# diagonals that started being attacked
d = i + sol[i]; diag_up[d] += 1
d = j + sol[j]; diag_up[d] += 1
d = (n-1) - i + sol[i]; diag_dn[d] += 1
d = (n-1) - j + sol[j]; diag_dn[d] += 1
def decrease(di,dj,ni,nj):
"""Compute collisions removed when queens are removed.
Parameters:
- di, dj -- diagonals where queens are currently placed
- ni, nj -- number of queens on these diagonals
"""
delta = 0
if ni >= 2: delta -= 1
if nj >= 2: delta -= 1
if di == dj and ni == 2: delta += 1 # discounted one in excess, replace it
return delta
def increase(di,dj,ni,nj):
"""Compute new collisions when queens are positioned.
Parameters:
- di, dj -- diagonals where queens will be placed
- ni, nj -- number of queens on these diagonals
"""
delta = 0
if ni >= 1: delta += 1
if nj >= 1: delta += 1
if di == dj and ni == 0: delta += 1 # on the same diagonal
return delta
def evaluate_move(i, j, sol, diag_up, diag_dn):
"""Evaluate exchange of queen of row i with that of row j."""
delta = 0
n = len(sol)
# diagonals not attacked anymore if move is accepted
upi = i + sol[i] # current upward diagonal of queen in row i
upj = j + sol[j] # j
delta += decrease(upi,upj,diag_up[upi],diag_up[upj])
dni = (n-1) + sol[i] - i # current downward diagonal of queen in row i
dnj = (n-1) + sol[j] - j # j
delta += decrease(dni,dnj,diag_dn[dni],diag_dn[dnj])
# diagonals that started being attacked
upi = i + sol[j] # new upward diagonal for queen in row i
upj = j + sol[i] # j
delta += increase(upi,upj,diag_up[upi],diag_up[upj])
dni = (n-1) + sol[j] - i # new downward diagonal of queen in row i
dnj = (n-1) + sol[i] - j # j
delta += increase(dni,dnj,diag_dn[dni],diag_dn[dnj])
return delta
def find_move(n_iter, tabu, best_colls, sol, diag_up, diag_dn, ncolls):
"""Return a tuple (i,j) with the best move.
Checks all possible moves from the current solution, and choose the one that:
* is not TABU, or
* is TABU but satisfies the aspiration criterion
The candidate list is composed of all the possibilities
of swapping two lines.
ParameterS:
"""
n = len(sol)
best_delta = n # value of best found move
for i in range(0,n-1):
for j in range(i+1,n):
delta = evaluate_move(i,j,sol,diag_up,diag_dn)
print "move %d-%d" % (i,j), "-> delta=%d;" % delta,
if tabu[i] >= n_iter:
print "move is tabu;",
if ncolls + delta < best_colls:
print "aspiration criterion is satisfied;",
print
if (tabu[i] < n_iter # move is not tabu,
or ncolls + delta < best_colls): # or satisfies aspiration criterion
if delta < best_delta:
best_delta = delta
best_i = i
best_j = j
return best_i, best_j, best_delta
def local_search(sol):
"""Local search: find local optimum starting from sol.
Returns number of collisions of the local optimum.
"""
n = len(sol)
diag_up,diag_dn = diagonals(sol)
print "\ninitial board"
display(sol)
ncolls = collisions(diag_up) + collisions(diag_dn)
print "collisions:", ncolls
n_iter = 0
while True:
n_iter += 1
print "\niteration", n_iter
improved = False
for i in range(0,n-1):
for j in range(i+1,n):
delta = evaluate_move(i,j,sol,diag_up,diag_dn)
if delta < 0:
print "improving move: change rows ", i, "and", j, ", delta", delta
improved = True
# execute the improvement: update the board
exchange(i, j, sol, diag_up, diag_dn)
ncolls += delta
# display current solution:
display(sol)
print "collisions:", ncolls
if not improved:
return ncolls
def tabu_search(tabulen, maxiter, sol):
"""Tabu search: find solution starting search from sol.
Parameters:
- tabulen: number of tabu iterations after a move is done
- maxiter - (absolute) maximum number of iterations
- sol - starting solution; later updated with the best found solution
Returns number of collisions of the local optimum.
"""
n = len(sol)
diag_up,diag_dn = diagonals(sol)
print "\ninitial board"
display(sol)
ncolls = collisions(diag_up) + collisions(diag_dn)
print "collisions:", ncolls
n_iter = 0 # iteration count
iter_best = 0 # iteration at which best solution was found
best = list(sol) # copy of the best solution found
best_colls = ncolls
# tabu information (iteration until which move from 'i' is forbidden):
tabu = [0 for i in range(n)]
while (n_iter < maxiter) and (best_colls != 0):
n_iter += 1
print "\niteration", n_iter
# determine the best move in the current neighborhood:
(i,j,delta) = find_move(n_iter, tabu, best_colls, sol, diag_up, diag_dn, ncolls)
print "best move is: change rows ", i, "and", j, ", delta", delta
# update the board, executing the best move:
exchange(i, j, sol, diag_up, diag_dn)
ncolls += delta
# update the tabu structure:
# moves involving i will be tabu for 'tabulen' iterations
tabu[i] = n_iter + tabulen
# check if we improved the best:
if ncolls < best_colls:
iter_best = n_iter
best = list(sol)
best_colls = ncolls
# display current solution:
display(sol)
print "collisions:", ncolls
# copy best solution found
sol = best
ncolls = best_colls
print
print "final solution (found at iteration", iter_best, ")"
print "final tabu list:"
print tabu
display(sol)
print "collisions:", ncolls
return ncolls
if __name__ == "__main__":
"""Tabu search for the N-Queens problem: sample usage."""
import sys
if len(sys.argv) == 1:
n = 8
elif len(sys.argv) == 2:
n = int(sys.argv[1])
elif len(sys.argv) == 3:
n = int(sys.argv[1])
rnd = int(sys.argv[2])
random.seed(rnd)
print "random seed:", rnd
else:
print "usage:", sys.argv[0], "[board_size [rnd_seed]]"
exit(-1)
print "*** graph partitioning problem ***"
print
#
# test the functions:
#
# create a random solution
print "instance randomly created"
print "board size:", n
sol = range(n) # set solution equal to [0,1,...,n-1]
random.shuffle(sol) # place it in a random order
print "initial solution (random):"
print "array:" , sol
display(sol)
up,dn = diagonals(sol)
print "queens on upward diagonals:", up
print "queens on downward diagonals:", dn
ncolls = collisions(up) + collisions(dn)
print "collisions:", ncolls
print "\n\n\nstarting local search"
ncolls = local_search(sol)
if ncolls != 0:
print "\n\n\nstarting tabu search"
tabulen = n/2
maxiter = 100000
ncolls = tabu_search(tabulen, maxiter, sol)
else:
print "local optimum has no collisions"
display(sol)
print "\nno further improvements are possible, not doing tabu search"
exit(0)