U E D R , A S I H C RSS

Eight Queen Problem/강석천

BoardTestCase.py

~cpp 
import unittest
from Board import *

class BoardTestCase (unittest.TestCase):
    def setUp (self):
        self.bd = QueenBoard ()

    def tearDown (self):
        self.bd = None
        
    def testBoardEmpty (self):
        self.assertEquals (self.bd.GetData (2,2), 0)

    def testSetQueen (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.GetData (2,2) ,1)

    def testPrintBoard (self):
        self.bd.SetQueen (1,1)
        self.bd.SetQueen (2,2)
        self.bd.SetQueen (7,7)
        self.assertEquals (self.bd.PrintBoard (), '''00000000\n01000000\n00100000\n00000000\n00000000\n00000000\n00000000\n00000001\n''')
        
    def testIsSelftyZone (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.IsSelftyZone (3,3), 0)
        self.assertEquals (self.bd.IsSelftyZone (1,5), 1)

    def testFindQueenInSameVertical (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameVertical (2), 1)
        self.assertEquals (self.bd.FindQueenInSameVertical (3), 0)

    def testFindQueenInSameHorizonal (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameHorizonal (2), 1)
        self.assertEquals (self.bd.FindQueenInSameHorizonal (3), 0)

    def testFindQueenInSameCrossLeftTopToRightBottom (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftTopToRightBottom (3,3), 1)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftTopToRightBottom (1,1), 1)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftTopToRightBottom (4,1), 0)

    def testFindQueenInSameCrossLeftBottomToRightTop (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftBottomToRightTop (3,3), 0)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftBottomToRightTop (3,1), 1)
        self.assertEquals (self.bd.FindQueenInSameCrossLeftBottomToRightTop (1,3), 1)

    def testGetFirstCornerInCrossLeftTopToRightBottom (self):
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (3,3), (0,0))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (4,3), (1,0))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (1,5), (0,4))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftTopToRightBottom (0,0), (0,0))

    def testGetFirstCornerInCrossLeftBottomToRightTop (self):
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftBottomToRightTop (2,2), (0,4))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftBottomToRightTop (3,5), (1,7))
        self.assertEquals (self.bd.GetFirstCornerInCrossLeftBottomToRightTop (7,7), (7,7))

    def testIsAttackableOthers (self):
        self.bd.SetQueen (2,2)
        self.assertEquals (self.bd.IsAttackableOthers (3,3),1)
        self.bd.SetQueen (7,1)
        self.assertEquals (self.bd.IsAttackableOthers (7,1),0)
        self.assertEquals (self.bd.IsAttackableOthers (4,4),1)

    def testEightQueen (self):
        ## self.bd.EightQueen ()
        ## if all queen pass the function 'IsAttackableOthers'
        self.bd.EightQueen ()

    def testGetUnAttackablePositon (self):
        self.bd.SetQueen (0,0)
        self.assertEquals (self.bd.GetUnAttackablePosition (1), ((2,1),(3,1),(4,1),(5,1),(6,1),(7,1)))
        self.assertEquals (self.bd.GetUnAttackablePosition (2), ((1,2),(3,2),(4,2),(5,2),(6,2),(7,2)))

suite = unittest.makeSuite (BoardTestCase, "test")

runner = unittest.TextTestRunner ()
runner.run (suite)


Board.py

~cpp 
class QueenBoard:
    def __init__(self):
        self.boardArray = {}
        self.Empty ()
        self.Flag = 0
        self.Count = 0

    def Empty (self):
        for i in range (0,8):
            for j in range (0,8):
                self.boardArray[(i,j)] = 0

    def GetData (self, x, y):
        return self.boardArray[(y,x)]

    def SetData (self, x, y, data):
        self.boardArray[(y,x)] = data

    def SetQueen (self, x, y):
        self.boardArray[(y,x)] = 1

    def IsSelftyZone (self, x, y):
        # x, y position. check vertical, horizonal, two cross check.
        if self.FindQueenInSameVertical (x):
            return 0
        elif self.FindQueenInSameHorizonal (y):
            return 0
        elif self.FindQueenInSameCrossLeftTopToRightBottom (x,y):
            return 0
        elif self.FindQueenInSameCrossLeftBottomToRightTop (x,y):
            return 0
        else:
            return 1

    def FindQueenInSameVertical (self, x):
        for i in range (0,8):
            if self.GetData (x,i) == 1:
                return 1
        return 0
        

    def FindQueenInSameHorizonal (self, y):
        for i in range (0,8):
            if self.GetData (i,y) == 1:
                return 1
        return 0

    def FindQueenInSameCrossLeftTopToRightBottom (self, x,y):
        FirstCornerX, FirstCornerY = self.GetFirstCornerInCrossLeftTopToRightBottom (x,y)
        FindRange = 8 - max (FirstCornerX, FirstCornerY)
        for i in range (0,FindRange):
            if self.GetData (FirstCornerX + i, FirstCornerY + i) == 1:
                return 1

        return 0

    def FindQueenInSameCrossLeftBottomToRightTop (self, x,y):
        FirstCornerX, FirstCornerY = self.GetFirstCornerInCrossLeftBottomToRightTop (x,y)
        FindRange = FirstCornerY + 1 - FirstCornerX;

        for i in range (0,FindRange):
            if self.GetData (FirstCornerX + i, FirstCornerY - i) == 1:
                return 1
            
        return 0
        

    def GetFirstCornerInCrossLeftTopToRightBottom (self, x,y):
        CornerX = x - min (x,y)
        CornerY = y - min (x,y)
        return (CornerX, CornerY)

    def GetFirstCornerInCrossLeftBottomToRightTop (self, x,y):
        CornerX = x - min (x,abs(y-7))
        CornerY = y + min (x,abs(y-7))
        return (CornerX, CornerY)

    def PrintBoard (self):
        lines = ''
        for i in range (0,8):
            line = ''
            for j in range (0,8):
                line += "%d" % self.GetData (j,i)
            lines += "%s\n" % line

        return lines

    def IsAttackableOthers (self, x,y):
        TempData = self.GetData (x,y)
        self.SetData (x,y,0)
        if self.IsSelftyZone (x,y):
            Ret = 0
        else:
            Ret = 1
        self.SetData (x,y,TempData)

        return Ret

    def EightQueen (self):
        self.Flag = 0
        self.DefineQueen (0)

    def DefineQueen (self, Level):
        if Level == 8:
            self.Count = self.Count + 1
            print "%d. level : %d \n" % (self.Count, Level)
            print self.PrintBoard ()
            return 0
        
        PositionList = self.GetUnAttackablePosition (Level)

        for position in PositionList:
            self.SetQueen (position[0], position[1])
            Ret = self.DefineQueen (Level + 1)
            if not Ret:
                self.SetData (position[0],position[1], 0)

    def GetUnAttackablePosition (self, Level):
        UnAttackablePositionList = []
        for i in range (0,8):
            if not self.IsAttackableOthers (i, Level):
                UnAttackablePositionList.append ((i,Level))

        return tuple(UnAttackablePositionList)

    def main (self):
        self.EightQueen ()
        
if __name__ == '__main__':
    bd = QueenBoard ()
    bd.main ()
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0901 sec