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'))
