import sys import os import time OCCUPIED = 1 # field is in use FREE = 0 # field is not used OUTPUT = False # enable/disable of printing the solutions class Queen: def __init__(self, width): self.width = width self.lastRow = self.width-1 # locked columns self.columns = self.width * [-1] # locked diagonals numberOfDiagonals = 2 * self.width - 1 self.diagonals1 = numberOfDiagonals * [0] self.diagonals2 = numberOfDiagonals * [0] # list of solutions self.solutions = set() # starts the search with initial parameters and organizing # to search the half only def run(self): for column in range(self.width // 2 + self.width % 2): ixDiag1 = column ixDiag2 = self.lastRow + column # occupying column and diagonals depending on current row and column self.columns[column] = 0 self.diagonals1[ixDiag1] = OCCUPIED self.diagonals2[ixDiag2] = OCCUPIED self.calculate(1, [k for k in range(self.width) if not k == column]) # Freeing column and diagonals depending on current row and column self.diagonals1[ixDiag1] = FREE self.diagonals2[ixDiag2] = FREE # searches for all possible solutions def calculate(self, row, columnRange): for column in columnRange: # relating diagonale '\' depending on current row and column ixDiag1 = row + column if self.diagonals1[ixDiag1] == OCCUPIED: continue # relating diagonale '/' depending on current row and column ixDiag2 = self.lastRow - row + column # is one of the relating diagonals OCCUPIED by a queen? if self.diagonals2[ixDiag2] == OCCUPIED: continue # occupying column and diagonals depending on current row and column self.columns[column] = row self.diagonals1[ixDiag1] = OCCUPIED self.diagonals2[ixDiag2] = OCCUPIED # all queens have been placed? if row == self.lastRow: solutionA = self.columns[0:] self.solutions.add(tuple(solutionA)) # mirrored left <-> right solutionB = tuple(reversed(solutionA)) self.solutions.add(solutionB) # mirrored top <-> bottom self.solutions.add(tuple(map(lambda n: self.lastRow - n, solutionA))) # mirrored top <-> bottom and left <-> right self.solutions.add(tuple(map(lambda n: self.lastRow - n, solutionB))) else: # trying to place next queen... self.calculate(row + 1, [k for k in columnRange if k != column]) # Freeing column and diagonals depending on current row and column self.diagonals1[ixDiag1] = FREE self.diagonals2[ixDiag2] = FREE # printing all solutions where n queens are placed on a nxn board # without threaten another one. def printAllSolutions(self): for solution in sorted(self.solutions): line = "" for ix in range(len(solution)): line += "(%d,%d)" % (ix+1, solution[ix]+1) print(line) def main(): width = 8 # default if len(sys.argv) == 2: width = int(sys.argv[1]) instance = Queen(width) print("Running %s with %s - version %s" % (sys.argv[0], sys.executable, sys.version)) print("Queen raster (%dx%d)" % (instance.width, instance.width)) Start = time.time() instance.run() print("...calculation took %f seconds" % (time.time() - Start)) print("...with %d solutions" % (len(instance.solutions))) if OUTPUT: instance.printAllSolutions() if __name__ == '__main__': main()