juranek

gistfile1.txt

import time

OCCUPIED = 1     # oznaka da se polje koristi
FREE     = 0     # oznaka da je polje prazno
OUTPUT   = True  # zastavica za oznaku dal je ispis omogucen

# vracanje kontenjera(ploce) bez vrijednosti
def remove(container, value):
    container.remove(value)
    return container

# klasa koja oznacava ponasanje same kraljice i pozicije na trenutnoj sahovskoj ploci
class Queen:
    def __init__(self, width = 8):
        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        = []

    # pokrece sam algoritam pretrage sa nekim dodatnim parametrima
    def run(self):
        self.calculate(row = 0, columnRange = list(range(self.width)))

    # pokrece potragu za ostalim mogucim rjesenjima
    def calculate(self, row, columnRange):
        for column in columnRange:
            # poregledava na diagolani '\', moguce pozicije, ovisi o trenutnom redu i stupcu
            ixDiag1 = row + column

            if self.diagonals1[ixDiag1] == OCCUPIED:
                continue

            # poredava na gijagonali '/' ovici o trenutnom redu i stupcu
            ixDiag2 = self.width - 1 - row + column

            # is one of the relating diagonals OCCUPIED by a queen
            # pregledava sve one diagonale na koje moze doc, a koje su zauzete kraljicom
            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

            if row == self.lastRow:
                # all queens have been placed - remembering solution!
                self.solutions.append(self.columns[0:])
            else:
                # trying to place next queen...
                self.calculate(row + 1, remove(columnRange[0:], column))

            # Freeing column and diagonals depending on current row and column
            self.diagonals1[ixDiag1] = FREE
            self.diagonals2[ixDiag2] = FREE

def jura():
    instance = Queen(8)
    print("Sahovska ploca (%dx%d)" % (instance.width, instance.width))
    Start = time.time()
    instance.run()

    print("... potroseno vrijeme za izvrsavanje algoritma:  %f secs" % (time.time() - Start))
    print("... sa %d rjesenja." % (len(instance.solutions)))

    x = [["x" for i in range(8)] for j in range(8)]
    if OUTPUT:
        # ispis svih rjesenja
        br = 0
        for solution in instance.solutions:
            line = ""
            br += 1
            x = [["x" for i in range(8)] for j in range(8)]
            for ix in range(len(solution)):
                line += "(%d,%d)" % (ix+1, solution[ix]+1)
                x[ix][solution[ix]] = "Q"
            print("Rjesenje broj: %d" % br)
            print(line)
            for i in range(8):
                for j in range(8):
                    print x[i][j],
                print
            print " "
            del x

if __name__ == '__main__':
    jura()