U E D R , A S I H C RSS

Eight Queen Problem2/이강성

from Numeric import *

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

    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
            self.queens.append( (x, y) )
            res = self.decidePositions(count-1)
            self.mark(self.board, x, y, -1) # unmarking
            if res:
                if count == 1:
                    print self.queens
                    self.solutions.append(self.queens[:])
                    self.queens.pop()
            else:
                self.queens.pop()
        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 'Total solutions=', len(e.solutions)
    print e.solutions
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0064 sec