-
Notifications
You must be signed in to change notification settings - Fork 0
/
cube_puzzle.py
125 lines (103 loc) · 3.8 KB
/
cube_puzzle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import queue
class Pos:
def __init__(self,name):
self.name = name
self.normalForward = []
self.invertForward = []
self.normalReverse = []
self.invertReverse = []
self.normalRotate = []
self.invertRotate = []
def addConnection(self, other, dir = 1, inv = False):
if (dir == 1) and not inv:
self.normalForward.append(other)
elif (dir == 1) and inv:
self.invertForward.append(other)
elif (dir == -1) and not inv:
self.normalReverse.append(other)
elif (dir == -1) and inv:
self.invertReverse.append(other)
def addRotation(self, other, inv = False):
if inv:
self.invertRotate.append(other)
else:
self.normalRotate.append(other)
def __repr__(self):
return self.name
class Gear:
def __init__(self, corner, dir, pos, history):
self.corner = corner
self.dir = dir
self.pos = pos
self.history = history
def getPossiblePos(self):
NF = [Gear((self.corner + self.dir)%5, self.dir, pos, self.history + [pos.name]) for pos in self.pos.normalForward]
IF = [Gear((self.corner + self.dir)%5, (-1) * self.dir, pos, self.history + [pos.name]) for pos in self.pos.invertForward]
NR = [Gear((self.corner - self.dir)%5, self.dir, pos, self.history + [pos.name]) for pos in self.pos.normalReverse]
IR = [Gear((self.corner - self.dir)%5, (-1) * self.dir, pos, self.history + [pos.name]) for pos in self.pos.invertReverse]
R = [Gear(self.corner, self.dir, pos, self.history + [pos.name]) for pos in self.pos.normalRotate]
RR = [Gear(self.corner, (-1) * self.dir, pos, self.history + [pos.name]) for pos in self.pos.invertRotate]
return sum([NF, IF, NR, IR, R, RR], [])
def isWinningState(self):
return (self.corner == 0) and (self.dir == 1) and (self.pos == top)
def isWinningStateAlt(self):
return (self.corner == 1) and (self.dir == -1) and (self.pos == back)
def checkState(self):
#print("checking state {name}".format(name=self.pos.name))
if self.isWinningState():
print(self.history)
return True
return False
def __repr__(self):
return self.pos.name
# face direction top, forward, right
top = Pos('top')
bot = Pos('bot')
left = Pos('left')
right = Pos('right')
front = Pos('front')
back = Pos('back')
topR = Pos('topR')
botR = Pos('botR')
leftR = Pos('leftR')
rightR = Pos('rightR')
frontR = Pos('frontR')
backR = Pos('backR')
top.addRotation(topR)
topR.addRotation(top)
bot.addRotation(botR, inv=True)
botR.addRotation(bot, inv=True)
left.addRotation(leftR, inv=True)
leftR.addRotation(left, inv=True)
right.addRotation(rightR)
rightR.addRotation(right)
front.addRotation(frontR)
frontR.addRotation(front)
back.addRotation(backR, inv=True)
backR.addRotation(back, inv=True)
topR.addConnection(right, dir=1, inv=True)
topR.addConnection(left, dir=-1)
bot.addConnection(front, dir=-1, inv=True)
bot.addConnection(back, dir=1)
botR.addConnection(right, dir=1)
left.addConnection(topR, dir=1)
leftR.addConnection(backR, dir=1)
leftR.addConnection(frontR, dir=-1, inv=True)
right.addConnection(topR, dir=1, inv=True)
right.addConnection(botR, dir=-1)
rightR.addConnection(backR, dir=1, inv=True)
front.addConnection(bot, dir=-1, inv=True)
frontR.addConnection(leftR, dir=-1, inv=True)
back.addConnection(bot, dir=-1)
backR.addConnection(leftR, dir=-1)
backR.addConnection(rightR, dir=1, inv=True)
p = Gear(0, 1, front, [])
frontier = queue.Queue()
frontier.put(p)
while not p.checkState():
#print(frontier.queue)
for state in p.getPossiblePos():
frontier.put(state)
if len(state.history) >= 15:
raise StandardError("Maximum search depth exceeded")
p = frontier.get()