1 """EightQueenProblem solution and UnitTest by yong27
2 """
3
4 from pprint import pprint
5 import unittest, random, pdb
6
7 map = [[0,0,0,0,0,0,0,0],
8 [0,0,0,0,0,0,0,0],
9 [0,0,0,0,0,0,0,0],
10 [0,0,0,0,0,0,0,0],
11 [0,0,0,0,0,0,0,0],
12 [0,0,0,0,0,0,0,0],
13 [0,0,0,0,0,0,0,0],
14 [0,0,0,0,0,0,0,0],]
15
16 def makeRightDigTuple(aPosition):
17 x=aPosition[0]; y=aPosition[1]
18 result=[]
19 i=0
20 for num in range(x,-1,-1):
21 if y+i > 7: break
22 result.append((num, y+i))
23 i+=1
24 j=1
25 for num in range(y-1,-1,-1):
26 if x+j > 7: break
27 result.append((x+j, num))
28 j+=1
29 result.sort()
30 return result
31
32 def makeLeftDigTuple(aPosition):
33 x=aPosition[0]; y=aPosition[1]
34 result=[]
35 i=0
36 for num in range(x,8):
37 if y+i > 7: break
38 result.append((num, y+i))
39 i+=1
40 j=1
41 for num in range(y-1,-1,-1):
42 if x-j < 0: break
43 result.append((x-j,num))
44 j+=1
45 result.sort()
46 return result
47
48 class Queen:
49 def __init__(self, name):
50 self.name = name
51 self.x = self.name-1
52 self.y = 0
53 self.setPosition(self.x, self.y)
54 def setPosition(self, ax, ay):
55 if (ax not in range(8)) or (ay not in range(8)):
56 return "impossible"
57 self.remove()
58 self.x = ax
59 self.y = ay
60 map[self.x][self.y] = self.name
61 def getPosition(self):
62 return [self.x, self.y]
63 def remove(self):
64 map[self.x][self.y]=0
65
66 def isInRow(self):
67 for tempy in range(8):
68 oldQueen = map[self.x][tempy]
69 if oldQueen != 0 and oldQueen != self.name:
70 return oldQueen
71 def isInColumn(self):
72 for tempx in range(8):
73 oldQueen = map[tempx][self.y]
74 if oldQueen != 0 and oldQueen != self.name:
75 return oldQueen
76 def isInRightDig(self):
77 for tempx,tempy in makeRightDigTuple(self.getPosition()):
78 oldQueen = map[tempx][tempy]
79 if oldQueen !=0 and oldQueen != self.name:
80 return oldQueen
81 def isInLeftDig(self):
82 for tempx,tempy in makeLeftDigTuple(self.getPosition()):
83 oldQueen = map[tempx][tempy]
84 if oldQueen !=0 and oldQueen != self.name:
85 return oldQueen
86
87 def isFight(self):
88 return self.isInRow() or self.isInColumn() or \
89 self.isInRightDig() or self.isInLeftDig()
90
91 def moveRight(self):
92 mr = self.setPosition(self.x, self.y+1)
93 if mr == "impossible":
94 return "impossible"
95
96 def iterate(q, name):
97 while 1:
98 if q[name].isFight() is None and q[name].getPosition()[1] != 7:
99 break
100 a = q[name].moveRight()
101 if a:
102 q[name].remove()
103 q = movePreviousQueen(q, name-1)
104 q[name].setPosition(name-1, 0)
105 continue
106
107 def movePreviousQueen(q, name):
108 q[name].moveRight()
109 if name == 1: return q
110 iterate(q, name)
111 return q
112
113 def makeQueensDontFight():
114 q = {}
115 for name in range(1,9):
116 q[name] = Queen(name)
117 iterate(q, name)
118 return q
119
120 class TestEightQueenProblem(unittest.TestCase):
121 def setUp(self):
122 for i in range(8):
123 for j in range(8):
124 map[i][j]=0
125 def tearDown(self):
126 self.setUp()
127 def testIntialPosition(self):
128 q1 = Queen(1)
129 q1.setPosition(0,0)
130 self.assertEquals([0,0],q1.getPosition())
131 def testRowCheck(self):
132 q1=Queen(1);q2=Queen(2)
133 q2.setPosition(0,1)
134 self.assertEquals(1, q2.isInRow())
135 q2.setPosition(1,0)
136 self.assertEquals(None, q2.isInRow())
137 def testColumnCheck(self):
138 q1=Queen(1);q2=Queen(2)
139 q2.setPosition(0,1)
140 self.assertEquals(None, q2.isInColumn())
141 q2.setPosition(1,0)
142 self.assertEquals(1, q2.isInColumn())
143
144 def testMakeRightDigTuple1(self):
145 input = (1,2)
146 expected = [(0,3),(1,2),(2,1),(3,0),]
147 self.assertEquals(expected, makeRightDigTuple(input))
148 def testMakeRightDigTuple2(self):
149 input = (4,4)
150 expected = [(1, 7), (2, 6), (3, 5), (4, 4),
151 (5, 3), (6, 2), (7, 1)]
152 self.assertEquals(expected, makeRightDigTuple(input))
153 def testMakeRightDigTuple3(self):
154 input = (6,6)
155 expected = [(5, 7), (6, 6), (7, 5)]
156 self.assertEquals(expected, makeRightDigTuple(input))
157 def testMakeLeftDigTuple1(self):
158 input = (5,1)
159 expected = [(4,0), (5,1), (6,2), (7,3)]
160 self.assertEquals(expected, makeLeftDigTuple(input))
161 def testMakeLeftDigTuple2(self):
162 input = (1,5)
163 expected = [(0, 4), (1, 5), (2, 6), (3, 7)]
164 self.assertEquals(expected, makeLeftDigTuple(input))
165
166 def testRightDigCheck(self):
167 q1=Queen(1);q2=Queen(2)
168 q1.setPosition(1,2)
169 q2.setPosition(2,1)
170 self.assertEquals(1, q2.isInRightDig())
171 q2.setPosition(1,0)
172 self.assertEquals(None, q2.isInRightDig())
173
174 def testTotal(self):
175 qDict = makeQueensDontFight()
176 print ;pprint(map)
177 for eachQueen in qDict.values():
178 self.assertEquals(None, eachQueen.isFight())
179
180 if __name__=='__main__':
181 unittest.main(argv=('','-v'))
BioHackersNet