U E D R , A S I H C RSS

Eight Queen Problem/김형용


from pprint import pprint
import unittest, random, pdb

map = [[0,0,0,0,0,0,0,0],
       [0,0,0,0,0,0,0,0],
       [0,0,0,0,0,0,0,0],
       [0,0,0,0,0,0,0,0],
       [0,0,0,0,0,0,0,0],
       [0,0,0,0,0,0,0,0],
       [0,0,0,0,0,0,0,0],
       [0,0,0,0,0,0,0,0],]

def makeRightDigTuple(aPosition):
    x=aPosition[0]; y=aPosition[1]
    result=[]
    i=0
    for num in range(x,-1,-1):
        if y+i > 7: break
        result.append((num, y+i))
        i+=1
    j=1
    for num in range(y-1,-1,-1):
        if x+j > 7: break
        result.append((x+j, num))
        j+=1
    result.sort()
    return result

def makeLeftDigTuple(aPosition):
    x=aPosition[0]; y=aPosition[1]
    result=[]
    i=0
    for num in range(x,8):
        if y+i > 7: break
        result.append((num, y+i))
        i+=1
    j=1
    for num in range(y-1,-1,-1):
        if x-j < 0: break
        result.append((x-j,num))
        j+=1
    result.sort()
    return result

class Queen:
    def __init__(self, name):
        self.name = name
        self.x = self.name-1
        self.y = 0
        self.setPosition(self.x, self.y)
    def setPosition(self, ax, ay):
        if (ax not in range(8)) or (ay not in range(8)):
            return "impossible"
        self.remove()
        self.x = ax
        self.y = ay
        map[self.x][self.y] = self.name
    def getPosition(self):
        return [self.x, self.y]
    def remove(self):
        map[self.x][self.y]=0

    def isInRow(self):
        for tempy in range(8):
            oldQueen = map[self.x][tempy]
            if oldQueen != 0 and oldQueen != self.name:
                return oldQueen
    def isInColumn(self):
        for tempx in range(8):
            oldQueen = map[tempx][self.y]
            if oldQueen != 0 and oldQueen != self.name:
                return oldQueen
    def isInRightDig(self):
        for tempx,tempy in makeRightDigTuple(self.getPosition()):
            oldQueen = map[tempx][tempy]
            if oldQueen !=0 and oldQueen != self.name:
                return oldQueen
    def isInLeftDig(self):
        for tempx,tempy in makeLeftDigTuple(self.getPosition()):
            oldQueen = map[tempx][tempy]
            if oldQueen !=0 and oldQueen != self.name:
                return oldQueen

    def isFight(self):
        return self.isInRow() or self.isInColumn() or \
                            self.isInRightDig() or self.isInLeftDig()

    def moveRight(self):
        mr = self.setPosition(self.x, self.y+1)
        if mr == "impossible":
            return "impossible"

def iterate(q, name):
    while 1:
        if q[name].isFight() is None and q[name].getPosition()[1] != 7:
            break
        a = q[name].moveRight()
        if a:
            q[name].remove()
            q = movePreviousQueen(q, name-1)
            q[name].setPosition(name-1, 0)
            continue

def movePreviousQueen(q, name):
    q[name].moveRight()
    if name == 1: return q
    iterate(q, name)
    return q

def makeQueensDontFight():
    q = {}
    for name in range(1,9):
        q[name] = Queen(name)
        iterate(q, name)
    return q

class TestEightQueenProblem(unittest.TestCase):
    def setUp(self):
        for i in range(8):
            for j in range(8):
                map[i][j]=0
    def tearDown(self):
        self.setUp()
    def testIntialPosition(self):
        q1 = Queen(1)
        q1.setPosition(0,0)
        self.assertEquals([0,0],q1.getPosition())
    def testRowCheck(self):
        q1=Queen(1);q2=Queen(2)
        q2.setPosition(0,1)
        self.assertEquals(1, q2.isInRow())
        q2.setPosition(1,0)
        self.assertEquals(None, q2.isInRow())
    def testColumnCheck(self):
        q1=Queen(1);q2=Queen(2)
        q2.setPosition(0,1)
        self.assertEquals(None, q2.isInColumn())
        q2.setPosition(1,0)
        self.assertEquals(1, q2.isInColumn())

    def testMakeRightDigTuple1(self):
        input = (1,2)
        expected = [(0,3),(1,2),(2,1),(3,0),]
        self.assertEquals(expected, makeRightDigTuple(input))
    def testMakeRightDigTuple2(self):
        input = (4,4)
        expected = [(1, 7), (2, 6), (3, 5), (4, 4),
                    (5, 3), (6, 2), (7, 1)]
        self.assertEquals(expected, makeRightDigTuple(input))
    def testMakeRightDigTuple3(self):
        input = (6,6)
        expected = [(5, 7), (6, 6), (7, 5)]
        self.assertEquals(expected, makeRightDigTuple(input))
    def testMakeLeftDigTuple1(self):
        input = (5,1)
        expected = [(4,0), (5,1), (6,2), (7,3)]
        self.assertEquals(expected, makeLeftDigTuple(input))
    def testMakeLeftDigTuple2(self):
        input = (1,5)
        expected = [(0, 4), (1, 5), (2, 6), (3, 7)]
        self.assertEquals(expected, makeLeftDigTuple(input))

    def testRightDigCheck(self):
        q1=Queen(1);q2=Queen(2)
        q1.setPosition(1,2)
        q2.setPosition(2,1)
        self.assertEquals(1, q2.isInRightDig())
        q2.setPosition(1,0)
        self.assertEquals(None, q2.isInRightDig())

    def testTotal(self):
        qDict = makeQueensDontFight()
        print ;pprint(map)
        for eachQueen in qDict.values():
            self.assertEquals(None, eachQueen.isFight())

if __name__=='__main__':
    unittest.main(argv=('','-v'))

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:11
Processing time 0.0109 sec