Welcome, guest | Sign In | My Account | Store | Cart

• Think of a chess field 8x8.
• Place 8 queens in a way that no one threaten another one.

Intention:

• Writing an algorithm to provide all solutions
• Adjusting the algorithm in a way that it can handle chess fields by other sizes n x n.

Changes:

• Revision 5:
• can run providing "n" via command line parameter and
• run half of board adding the other solutions by mirroring (12x12 takes 4 seconds instead of 8 on my slow notebook)
• ...

Other languages:

Python, 106 lines
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 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()
• If you would like avoiding the output of the solution then change the value of variable OUTPUT.
• It's a solution with recursion.
• For good background information and inspiration:

Further Notes:

• I have been trying to use a dictionary instead of a list; intention was to avoid the correction of the value for a diagonal (as done for ixDiag2) and to allocate as much space as needed only (avoid numberOfDiagonals). It's slower.
• Another intention has been to use a cell class which has the pre-calculated values so I need not calculate the positions while running the algorithm. The algorithm is then very small and readable but it's two times slower.
• One of my last changes have been:
• Using self.lastRow instead of self.with-1
• Using reduced columnRange on each next row; that's why I'm also using run now for starting the calculation. Positive effect: I don't need the one check for the locked columns and I can remove the reset for a locked column.
 Created by Thomas Lehmann on Sat, 23 Oct 2010 (MIT)