**Task**:

- 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**:

- My recipe 578497 for JavaScript
- ...

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.

- Using

Tags: algorithms, queen