// python script to solve the 8 queens problem
def allowedMoves(usedCol, usedDiagL, usedDiagR):
allowed = ~(usedCol | usedDiagL | usedDiagR)
for col in (1,2,4,8,16,32,64,128):
if col & allowed:
yield usedCol | col, (usedDiagL | col) << 1, (usedDiagR | col) >> 1
def eightQueensSolutions():
for q0 in allowedMoves(0, 0, 0):
for q1 in allowedMoves(*q0):
for q2 in allowedMoves(*q1):
for q3 in allowedMoves(*q2):
for q4 in allowedMoves(*q3):
for q5 in allowedMoves(*q4):
for q6 in allowedMoves(*q5):
for q7 in allowedMoves(*q6):
yield (0,0,0),q0,q1,q2,q3,q4,q5,q6,q7
def solve8queens():
''' Solves the problem of placing 8 queens on a chess board with no queen
under attack. Queens are placed row by row, with the respective columns
encoded by setting bit after bit in the qN variables for fast generation
of allowed moves. The printboard() function decodes these to show the
final board.
My goal was a fast program that is easy to read. The code is a concise
combination of a generator for allowed moves and a deeply nested loop to
traverse the search tree. Most assignments are accomplished by function
calls and loops. Speed is achieved by not using recursion, by limiting
data carried through the search to three integers, and through testing
for allowed moves by a single bitwise operation. For diagonal attacks,
two integers (usedDiagL and usedDiagR) keep track of queens placed, and
are shifted left or right bitwise as the search proceeds from row to
row. On my machine, it takes 7 ms to find all 92 solutions.
Because the number of queens to be placed is hardcoded (by the giant
nested loop), there is no need to have branching code deciding whether
the final queen was just placed (in which case you have a solution).
It is not possible to parameterize the dimensions of the chess board
using this approach in a way that would keep the program lean and mean.
'''
solutions = [i for i in eightQueensSolutions()]
for s in solutions:
print ''
printboard(s)
print len(solutions), "solutions found"
def printboard(s):
b = '_Q'
for i,j in zip(s[:-1],s[1:]):
n = i[0] ^ j[0]
print " ".join([b[(n >> y) & 1] for y in range(8-1, -1, -1)])
if __name__ == "__main__": solve8queens()
