| 385 |
ira |
1 |
#!/usr/bin/env python
|
|
|
2 |
|
|
|
3 |
__author__ = "Ira W. Snyder (devel@irasnyder.com)"
|
|
|
4 |
__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"
|
|
|
5 |
__license__ = "GNU GPL v2 (or, at your option, any later version)"
|
|
|
6 |
|
|
|
7 |
class PuzzlePiece (object):
|
|
|
8 |
|
|
|
9 |
EMPTY = 'E'
|
|
|
10 |
|
| 393 |
ira |
11 |
def __init__ (self, state, depth=0, goal=None):
|
|
|
12 |
if len(state) != 9:
|
|
|
13 |
raise ValueError
|
|
|
14 |
|
| 385 |
ira |
15 |
self.state = state
|
| 393 |
ira |
16 |
self.depth = depth
|
|
|
17 |
self.goal = goal
|
| 385 |
ira |
18 |
|
|
|
19 |
def __eq__ (self, rhs):
|
|
|
20 |
return self.state == rhs.state
|
|
|
21 |
|
|
|
22 |
def __repr__(self):
|
|
|
23 |
"""Print yourself"""
|
|
|
24 |
result = ''
|
|
|
25 |
for i in xrange(3):
|
|
|
26 |
result += '%s %s %s' % (self.state[3*i], self.state[3*i+1], self.state[3*i+2])
|
|
|
27 |
if i<2:
|
|
|
28 |
result += '\n'
|
|
|
29 |
|
|
|
30 |
return result
|
|
|
31 |
|
|
|
32 |
def get_children (self):
|
|
|
33 |
children = []
|
| 393 |
ira |
34 |
empty_pos = self.find_position (self.EMPTY)
|
| 385 |
ira |
35 |
|
|
|
36 |
# Get the correct moves for this position
|
|
|
37 |
fn = { 0 : (self.move_down, self.move_right),
|
|
|
38 |
1 : (self.move_down, self.move_left, self.move_right),
|
|
|
39 |
2 : (self.move_down, self.move_left),
|
|
|
40 |
3 : (self.move_down, self.move_right, self.move_up),
|
|
|
41 |
4 : (self.move_down, self.move_left, self.move_right, self.move_up),
|
|
|
42 |
5 : (self.move_down, self.move_left, self.move_up),
|
|
|
43 |
6 : (self.move_right, self.move_up),
|
|
|
44 |
7 : (self.move_left, self.move_right, self.move_up),
|
|
|
45 |
8 : (self.move_left, self.move_up) }[empty_pos]
|
|
|
46 |
|
|
|
47 |
# Call each of the proper functions
|
|
|
48 |
for f in fn:
|
| 393 |
ira |
49 |
children.append (PuzzlePiece (f (empty_pos), self.depth+1, self.goal))
|
| 385 |
ira |
50 |
|
|
|
51 |
# Return the created list
|
|
|
52 |
return children
|
|
|
53 |
|
| 393 |
ira |
54 |
def find_position (self, value):
|
| 385 |
ira |
55 |
for i in xrange (len (self.state)):
|
| 393 |
ira |
56 |
if self.state[i] == value:
|
| 385 |
ira |
57 |
return i
|
|
|
58 |
|
|
|
59 |
raise ValueError
|
|
|
60 |
|
|
|
61 |
def move_up (self, empty_pos):
|
|
|
62 |
copy = self.state[:]
|
|
|
63 |
copy[empty_pos] = copy[empty_pos - 3]
|
|
|
64 |
copy[empty_pos - 3] = self.EMPTY
|
|
|
65 |
return copy
|
|
|
66 |
|
|
|
67 |
def move_left (self, empty_pos):
|
|
|
68 |
copy = self.state[:]
|
|
|
69 |
copy[empty_pos] = copy[empty_pos - 1]
|
|
|
70 |
copy[empty_pos - 1] = self.EMPTY
|
|
|
71 |
return copy
|
|
|
72 |
|
|
|
73 |
def move_right (self, empty_pos):
|
|
|
74 |
copy = self.state[:]
|
|
|
75 |
copy[empty_pos] = copy[empty_pos + 1]
|
|
|
76 |
copy[empty_pos + 1] = self.EMPTY
|
|
|
77 |
return copy
|
|
|
78 |
|
|
|
79 |
def move_down (self, empty_pos):
|
|
|
80 |
copy = self.state[:]
|
|
|
81 |
copy[empty_pos] = copy[empty_pos + 3]
|
|
|
82 |
copy[empty_pos + 3] = self.EMPTY
|
|
|
83 |
return copy
|
|
|
84 |
|
| 393 |
ira |
85 |
def num_out_of_place (self):
|
|
|
86 |
"""Find the number of tiles that are out of place"""
|
|
|
87 |
count = 0
|
| 385 |
ira |
88 |
|
| 393 |
ira |
89 |
for i in xrange(len(self.state)):
|
|
|
90 |
if self.state[i] != self.goal.state[i]:
|
|
|
91 |
count += 1
|
| 385 |
ira |
92 |
|
| 393 |
ira |
93 |
return count
|
| 385 |
ira |
94 |
|
| 393 |
ira |
95 |
def total_distance_from_correct (self):
|
|
|
96 |
"""Find the total distance that every piece of myself is from
|
|
|
97 |
the goal configuration given."""
|
|
|
98 |
total = 0
|
|
|
99 |
|
|
|
100 |
for e in self.state:
|
|
|
101 |
mypos = self.find_position (e)
|
|
|
102 |
goalpos = self.goal.find_position (e)
|
|
|
103 |
|
|
|
104 |
total += self.distance_from_correct (mypos, goalpos)
|
|
|
105 |
|
|
|
106 |
return total
|
|
|
107 |
|
|
|
108 |
|
|
|
109 |
def distance_from_correct (self, mypos, goalpos):
|
|
|
110 |
"""Find a single piece's distance from the correct position."""
|
|
|
111 |
crmap={ 0 : (0, 0),
|
|
|
112 |
1 : (0, 1),
|
|
|
113 |
2 : (0, 2),
|
|
|
114 |
3 : (1, 0),
|
|
|
115 |
4 : (1, 1),
|
|
|
116 |
5 : (1, 2),
|
|
|
117 |
6 : (2, 0),
|
|
|
118 |
7 : (2, 1),
|
|
|
119 |
8 : (2, 2) }
|
|
|
120 |
|
|
|
121 |
myrow, mycol = crmap[mypos]
|
|
|
122 |
goalrow, goalcol = crmap[goalpos]
|
|
|
123 |
|
|
|
124 |
return (abs(myrow - goalrow) + abs(mycol - goalcol))
|
|
|
125 |
|
|
|
126 |
def main ():
|
|
|
127 |
initial = [1, 2, 3, 4, 5, 6, 7, 8, 'E']
|
|
|
128 |
g = PuzzlePiece ([1, 7, 3, 4, 5, 6, 2, 8, 'E'])
|
|
|
129 |
p = PuzzlePiece (initial, 0, g)
|
|
|
130 |
|
|
|
131 |
print 'out of place:', p.num_out_of_place ()
|
|
|
132 |
print 'dist:', p.total_distance_from_correct ()
|
|
|
133 |
|
|
|
134 |
if __name__ == '__main__':
|
|
|
135 |
main ()
|
|
|
136 |
|