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

Eight queen problem (Python recipe) by Thomas Lehmann
ActiveState Code (http://code.activestate.com/recipes/577438/)

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:

Python, 106 lines
Download
  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()

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.
Tags: algorithms, queen