from Numeric import *

class EightQueen:
    def __init__(self, size=8):
        self.board = zeros((size, size))
        self.sizeX, self.sizeY = self.board.shape
        self.queens = []

    def decidePositions(self, count=8):
        if count == 0:
            return 1
        x = self.sizeX - count
        for y in range(self.sizeY):
            if self.board[x][y] != 0:
                continue
            self.mark(self.board, x, y, 1)  # marking
            res = self.decidePositions(count-1)
            self.mark(self.board, x, y, -1) # unmarking
            if res:
                self.queens.append( (x, y) )
                return 1
        return 0

    def mark(self, board, startX, startY, count):
        board[startX][startY] += count
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]:
            x, y = startX+dx, startY+dy
            while 0 <= x < self.sizeX and 0 <= y < self.sizeY:
                board[x][y] += count
                x += dx
                y += dy

if __name__ == '__main__':
    e = EightQueen()
    e.decidePositions()
    print e.queens
Retrieved from http://wiki.zeropage.org/wiki.php/EightQueenProblem/이강성
last modified 2021-02-07 05:23:11