Eight Queen Problem/Leonardong

No older revisions available

~cpp 
import math
class EightQueen:
    def __init__(self):
        self.board = None
        self.positions = []
    def makeChessBoard(self, aSize):
        self.board = []
        for i in range( aSize ):
            self.board.append([0]*aSize)
    def setQueen(self, aRow, aCol):
        self.board[aRow][aCol] = 1
        self.positions.append((aRow, aCol))
    def isPositionValid(self, aRow, aCol):
        for p in self.positions:
            if p[1] == aCol or p[0] == aRow or \
               math.fabs(aRow - p[0]) == math.fabs(aCol - p[1]):
                return False
        return True
    def popLastPosition(self):
        if len(self.positions) > 0:
            row, col = self.positions.pop()
            self.board[row][col] = 0
            return row, col
    def findNext(self, aRow, aCol):
        if aCol >= len(self.board):
            aRow, aCol = self.popLastPosition()
        elif self.isPositionValid(aRow, aCol):
            return aRow, aCol
        return self.findNext(aRow, aCol+1)
            
    
    def run(self, aSize):
        self.makeChessBoard(aSize)
        for row in range(aSize/2):
            col = 0
            while row < aSize:
                row, col = self.findNext(row, col)
                self.setQueen(row, col)
                row = row + 1
                col = 0
                if len(self.positions) >= aSize:
                    self.showBoard()
    
    def showBoard(self):
        print
        for b in self.board:
            print b
            
                
#########################################################################
            
import unittest

class EightQueenTestCase(unittest.TestCase):
    def defaultQueen(self):
        q = EightQueen()
        size = 8
        q.makeChessBoard(size)
        return q
##    def testMakeChessBoard(self):
##        q = self.defaultQueen()
##        self.assertEqual(len(q.board), size)
    def testSetQueen(self):
        q = self.defaultQueen()
        row, col = 0, 0
        q.setQueen(row, col)
        self.assertEqual(q.board[row][col], 1)
        self.assertEqual(len(q.positions), 1)
    def testIsPositionValid(self):
        q = self.defaultQueen()
        row, col = 3, 3
        q.setQueen(row, col)
        ## valid
        row, col = 1, 2
        vaild = q.isPositionValid(row, col)
        self.assertEqual(vaild, True)
        ## invalid
        row, col = 3, 7
        vaild = q.isPositionValid(row, col)
        self.assertEqual(vaild, False)
        row, col = 4, 3
        vaild = q.isPositionValid(row, col)
        self.assertEqual(vaild, False)
        row, col = 5, 5
        vaild = q.isPositionValid(row, col)
        self.assertEqual(vaild, False)
        row, col = 1, 1
        vaild = q.isPositionValid(row, col)
        self.assertEqual(vaild, False)
        row, col = 5, 1
        vaild = q.isPositionValid(row, col)
        self.assertEqual(vaild, False)

    def testPopLastPosition(self):
        q = self.defaultQueen()
        row, col = 0, 0
        q.setQueen(row, col)
        row, col = 1, 2
        q.setQueen(row, col)
        row, col = q.popLastPosition()
        self.assertEqual(len(q.positions), 1)
        self.assertEqual(row, 1)
        self.assertEqual(col, 2)        

    def testFindNext(self):
        q = self.defaultQueen()
        ## easily
        row, col = q.findNext(0, 0)
        self.assertEqual(row, 0)
        self.assertEqual(col, 0)        
        q.setQueen(row, col)
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 1)
        self.assertEqual(col, 2)        
        q.setQueen(row, col)
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 2)
        self.assertEqual(col, 4)
        q.setQueen(row, col)
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 3)
        self.assertEqual(col, 1)
        q.setQueen(row, col)        
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 4)
        self.assertEqual(col, 3)
        q.setQueen(row, col)
        ## go back
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 4)
        self.assertEqual(col, 7)
        q.setQueen(row, col)
        ## back again
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 3)
        self.assertEqual(col, 6)
        q.setQueen(row, col)
        ## go foward
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 4)
        self.assertEqual(col, 1)
        q.setQueen(row, col)
        row, col = q.findNext(row+1,0)
        self.assertEqual(row, 5)
        self.assertEqual(col, 3)
        q.setQueen(row, col)
        
    def testRun(self):
        q = EightQueen()
        size = 8
        q.run(8)
if __name__ == '__main__': 
    unittest.main()