~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()