Eight Queens Problem
Eight Queens Problem
Join the DZone community and get the full member experience.Join For Free
// 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 ^ j print " ".join([b[(n >> y) & 1] for y in range(8-1, -1, -1)]) if __name__ == "__main__": solve8queens()
Opinions expressed by DZone contributors are their own.