Recipe 577438 revision 5

Diff to Previous Revision

--- revision 4 2013-03-20 19:01:07
+++ revision 5 2013-05-10 03:44:56
@@ -1,16 +1,13 @@
+import sys
+import os
 import time
 
 OCCUPIED = 1     # field is in use
 FREE     = 0     # field is not used
-OUTPUT   = True  # enable/disable of printing the solutions
-
-# returning a container without the given value
-def remove(container, value):
-    container.remove(value)
-    return container
+OUTPUT   = False # enable/disable of printing the solutions
 
 class Queen:
-    def __init__(self, width = 8):
+    def __init__(self, width):
         self.width            = width
         self.lastRow          = self.width-1
         # locked columns
@@ -20,11 +17,24 @@
         self.diagonals1       = numberOfDiagonals * [0]
         self.diagonals2       = numberOfDiagonals * [0]
         # list of solutions
-        self.solutions        = []
+        self.solutions        = set()
 
-    # starts the search with initial parameters
+    # starts the search with initial parameters and organizing
+    # to search the half only
     def run(self):
-        self.calculate(row = 0, columnRange = list(range(self.width)))
+        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):
@@ -36,7 +46,7 @@
                 continue
 
             # relating diagonale '/' depending on current row and column
-            ixDiag2 = self.width - 1 - row + column
+            ixDiag2 = self.lastRow - row + column
 
             # is one of the relating diagonals OCCUPIED by a queen?
             if self.diagonals2[ixDiag2] == OCCUPIED:
@@ -47,33 +57,50 @@
             self.diagonals1[ixDiag1] = OCCUPIED
             self.diagonals2[ixDiag2] = OCCUPIED
 
+            # all queens have been placed?
             if row == self.lastRow:
-                # all queens have been placed - remembering solution!
-                self.solutions.append(self.columns[0:])
+                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, remove(columnRange[0:], column))
+                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
 
-def main():
-    instance = Queen(8)
-    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:
-        # output of all solutions
-        for solution in instance.solutions:
+    # 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()