Anonymous user
15 puzzle solver: Difference between revisions
A star version
(Added run time to Python example) |
(A star version) |
||
Line 2,422:
Right, Right, Right, Up, Left, Down, Left, Up, Up, Left, Down, Right, Up, Right, Down, Down, Down, Left, Up, Up, Left, Up, Right, Right, Right, Down, Left, Down, Down, Right, Up, Left, Down, Left, Up, Up, Right, Down, Down, Left, Up, Left, Up, Right, Right, Up, Left, Down, Right, Right, Down, Down
52 872794
</pre>
A* version
<lang Python>
"""
Python example for this Rosetta Code task:
http://rosettacode.org/wiki/15_puzzle_solver
Using A* Algorithm from Wikkipedia:
https://en.wikipedia.org/wiki/A*_search_algorithm
Need to use heuristic that guarantees a shortest path
solution.
"""
import heapq
import copy
# Hopefully this is larger than any fscore or gscore
integer_infinity = 1000000000
class Position(object):
"""Position class represents one position of a 15 puzzle"""
def __init__(self, tiles):
"""
Takes a tuple of tuples representing the tiles on a 4x4 puzzle board
numbering 1-15 with 0 representing an empty square. For example:
(( 1, 2, 3, 4),
( 5, 6, 7, 8),
( 9, 10, 11, 12),
(13, 14, 15, 0))
Converts list of lists representation into tuple of tuples.
"""
if type(tiles) == type(list()):
t = tiles
self.tiles = ((t[0][0], t[0][1], t[0][2], t[0][3]),
(t[1][0], t[1][1], t[1][2], t[1][3]),
(t[2][0], t[2][1], t[2][2], t[2][3]),
(t[3][0], t[3][1], t[3][2], t[3][3]))
else:
self.tiles = tiles
# fields for A* algorithm
self.fscore = integer_infinity
self.gscore = integer_infinity
self.cameFrom = None
def copy_tiles(self):
""" returns list of lists version """
t = self.tiles
return [[t[0][0], t[0][1], t[0][2], t[0][3]],
[t[1][0], t[1][1], t[1][2], t[1][3]],
[t[2][0], t[2][1], t[2][2], t[2][3]],
[t[3][0], t[3][1], t[3][2], t[3][3]]]
def neighbors(self):
"""
returns a list of neighbors
returns a list position objects with their
directiontomoveto set to the direction that the
empty square moved.
tiles is 4x4 tuple of tuples with
0,0 as top left.
tiles[y][x]
"""
# find 0 - blank square
x0 = None
y0 = None
for i in range(4):
for j in range(4):
if self.tiles[i][j] == 0:
y0 = i
x0 = j
if x0 == None or y0 == None:
return []
neighbor_list = []
# move 0 to the right
if x0 < 3:
new_tiles = self.copy_tiles()
temp = new_tiles[y0][x0+1]
new_tiles[y0][x0+1] = 0
new_tiles[y0][x0] = temp
new_pos = new_position(new_tiles)
neighbor_list.append(new_pos)
# move 0 to the left
if x0 > 0:
new_tiles = self.copy_tiles()
temp = new_tiles[y0][x0-1]
new_tiles[y0][x0-1] = 0
new_tiles[y0][x0] = temp
new_pos = new_position(new_tiles)
neighbor_list.append(new_pos)
# move 0 up
if y0 > 0:
new_tiles = self.copy_tiles()
temp = new_tiles[y0-1][x0]
new_tiles[y0-1][x0] = 0
new_tiles[y0][x0] = temp
new_pos = new_position(new_tiles)
neighbor_list.append(new_pos)
# move 0 down
if y0 < 3:
new_tiles = self.copy_tiles()
temp = new_tiles[y0+1][x0]
new_tiles[y0+1][x0] = 0
new_tiles[y0][x0] = temp
new_pos = new_position(new_tiles)
neighbor_list.append(new_pos)
return neighbor_list
def __repr__(self):
# printable version of self
return str(self.tiles[0])+'\n'+str(self.tiles[1])+'\n'+str(self.tiles[2])+'\n'+str(self.tiles[3])+'\n'
# takes tuple of tuples tiles as key, Position object for that tiles as value
all_positions = dict()
def new_position(tiles):
""" returns a new position or looks up existing one """
global all_positions
if type(tiles) == type(list()):
t = tiles
tuptiles = ((t[0][0], t[0][1], t[0][2], t[0][3]),
(t[1][0], t[1][1], t[1][2], t[1][3]),
(t[2][0], t[2][1], t[2][2], t[2][3]),
(t[3][0], t[3][1], t[3][2], t[3][3]))
else:
tuptiles = tiles
if tuptiles in all_positions:
return all_positions[tuptiles]
else:
new_pos = Position(tiles)
all_positions[tuptiles] = new_pos
return new_pos
def reconstruct_path(current):
"""
Uses the cameFrom members to follow the chain of moves backwards
and then reverses the list to get the path in the correct order.
"""
total_path = [current]
while current.cameFrom != None:
current = current.cameFrom
total_path.append(current)
total_path.reverse()
return total_path
class PriorityQueue(object):
"""
Priority queue using heapq.
elements of queue are (fscore,tiles) for each position.
If element is removed from queue and fscore doesn't match
then that element is discarded.
"""
def __init__(self, object_list):
"""
Save a list in a heapq.
Assume that each object only appears once
in the list.
"""
self.queue_length = 0
self.qheap = []
for e in object_list:
self.qheap.append((e.fscore,e.tiles))
self.queue_length += 1
heapq.heapify(self.qheap)
def push(self, new_object):
""" save object in heapq """
heapq.heappush(self.qheap,(new_object.fscore,new_object.tiles))
self.queue_length += 1
def pop(self):
""" remove object from heap and return """
if self.queue_length < 1:
return None
fscore, tiles = heapq.heappop(self.qheap)
self.queue_length -= 1
global all_positions
pos = all_positions[tiles]
if pos.fscore == fscore:
return pos
else:
return self.pop()
def __repr__(self):
# printable version of self
strrep = ""
for e in self.qheap:
fscore, tiles = e
strrep += str(fscore)+":"+str(tiles)+"\n"
return strrep
conflict_table = None
def build_conflict_table():
global conflict_table
conflict_table = dict()
# assumes goal tuple has up to
# for the given pattern it the start position
# how much to add for linear conflicts
# 2 per conflict - max of 6
# goal tuple is ('g0', 'g1', 'g2', 'g3')
conflict_table[('g0', 'g1', 'g2', 'g3')] = 0
conflict_table[('g0', 'g1', 'g2', 'x')] = 0
conflict_table[('g0', 'g1', 'g3', 'g2')] = 2
conflict_table[('g0', 'g1', 'g3', 'x')] = 0
conflict_table[('g0', 'g1', 'x', 'g2')] = 0
conflict_table[('g0', 'g1', 'x', 'g3')] = 0
conflict_table[('g0', 'g1', 'x', 'x')] = 0
conflict_table[('g0', 'g2', 'g1', 'g3')] = 2
conflict_table[('g0', 'g2', 'g1', 'x')] = 2
conflict_table[('g0', 'g2', 'g3', 'g1')] = 4
conflict_table[('g0', 'g2', 'g3', 'x')] = 0
conflict_table[('g0', 'g2', 'x', 'g1')] = 2
conflict_table[('g0', 'g2', 'x', 'g3')] = 0
conflict_table[('g0', 'g2', 'x', 'x')] = 0
conflict_table[('g0', 'g3', 'g1', 'g2')] = 4
conflict_table[('g0', 'g3', 'g1', 'x')] = 2
conflict_table[('g0', 'g3', 'g2', 'g1')] = 4
conflict_table[('g0', 'g3', 'g2', 'x')] = 2
conflict_table[('g0', 'g3', 'x', 'g1')] = 2
conflict_table[('g0', 'g3', 'x', 'g2')] = 2
conflict_table[('g0', 'g3', 'x', 'x')] = 0
conflict_table[('g0', 'x', 'g1', 'g2')] = 0
conflict_table[('g0', 'x', 'g1', 'g3')] = 0
conflict_table[('g0', 'x', 'g1', 'x')] = 0
conflict_table[('g0', 'x', 'g2', 'g1')] = 2
conflict_table[('g0', 'x', 'g2', 'g3')] = 0
conflict_table[('g0', 'x', 'g2', 'x')] = 0
conflict_table[('g0', 'x', 'g3', 'g1')] = 2
conflict_table[('g0', 'x', 'g3', 'g2')] = 2
conflict_table[('g0', 'x', 'g3', 'x')] = 0
conflict_table[('g0', 'x', 'x', 'g1')] = 0
conflict_table[('g0', 'x', 'x', 'g2')] = 0
conflict_table[('g0', 'x', 'x', 'g3')] = 0
conflict_table[('g1', 'g0', 'g2', 'g3')] = 2
conflict_table[('g1', 'g0', 'g2', 'x')] = 2
conflict_table[('g1', 'g0', 'g3', 'g2')] = 4
conflict_table[('g1', 'g0', 'g3', 'x')] = 2
conflict_table[('g1', 'g0', 'x', 'g2')] = 2
conflict_table[('g1', 'g0', 'x', 'g3')] = 2
conflict_table[('g1', 'g0', 'x', 'x')] = 2
conflict_table[('g1', 'g2', 'g0', 'g3')] = 4
conflict_table[('g1', 'g2', 'g0', 'x')] = 4
conflict_table[('g1', 'g2', 'g3', 'g0')] = 6
conflict_table[('g1', 'g2', 'g3', 'x')] = 0
conflict_table[('g1', 'g2', 'x', 'g0')] = 4
conflict_table[('g1', 'g2', 'x', 'g3')] = 0
conflict_table[('g1', 'g2', 'x', 'x')] = 0
conflict_table[('g1', 'g3', 'g0', 'g2')] = 4
conflict_table[('g1', 'g3', 'g0', 'x')] = 4
conflict_table[('g1', 'g3', 'g2', 'g0')] = 6
conflict_table[('g1', 'g3', 'g2', 'x')] = 0
conflict_table[('g1', 'g3', 'x', 'g0')] = 4
conflict_table[('g1', 'g3', 'x', 'g2')] = 2
conflict_table[('g1', 'g3', 'x', 'x')] = 0
conflict_table[('g1', 'x', 'g0', 'g2')] = 2
conflict_table[('g1', 'x', 'g0', 'g3')] = 2
conflict_table[('g1', 'x', 'g0', 'x')] = 2
conflict_table[('g1', 'x', 'g2', 'g0')] = 4
conflict_table[('g1', 'x', 'g2', 'g3')] = 0
conflict_table[('g1', 'x', 'g2', 'x')] = 0
conflict_table[('g1', 'x', 'g3', 'g0')] = 4
conflict_table[('g1', 'x', 'g3', 'g2')] = 2
conflict_table[('g1', 'x', 'g3', 'x')] = 0
conflict_table[('g1', 'x', 'x', 'g0')] = 2
conflict_table[('g1', 'x', 'x', 'g2')] = 0
conflict_table[('g1', 'x', 'x', 'g3')] = 0
conflict_table[('g2', 'g0', 'g1', 'g3')] = 4
conflict_table[('g2', 'g0', 'g1', 'x')] = 4
conflict_table[('g2', 'g0', 'g3', 'g1')] = 4
conflict_table[('g2', 'g0', 'g3', 'x')] = 2
conflict_table[('g2', 'g0', 'x', 'g1')] = 4
conflict_table[('g2', 'g0', 'x', 'g3')] = 2
conflict_table[('g2', 'g0', 'x', 'x')] = 2
conflict_table[('g2', 'g1', 'g0', 'g3')] = 4
conflict_table[('g2', 'g1', 'g0', 'x')] = 4
conflict_table[('g2', 'g1', 'g3', 'g0')] = 6
conflict_table[('g2', 'g1', 'g3', 'x')] = 2
conflict_table[('g2', 'g1', 'x', 'g0')] = 4
conflict_table[('g2', 'g1', 'x', 'g3')] = 2
conflict_table[('g2', 'g1', 'x', 'x')] = 2
conflict_table[('g2', 'g3', 'g0', 'g1')] = 4
conflict_table[('g2', 'g3', 'g0', 'x')] = 4
conflict_table[('g2', 'g3', 'g1', 'g0')] = 6
conflict_table[('g2', 'g3', 'g1', 'x')] = 4
conflict_table[('g2', 'g3', 'x', 'g0')] = 4
conflict_table[('g2', 'g3', 'x', 'g1')] = 4
conflict_table[('g2', 'g3', 'x', 'x')] = 0
conflict_table[('g2', 'x', 'g0', 'g1')] = 4
conflict_table[('g2', 'x', 'g0', 'g3')] = 2
conflict_table[('g2', 'x', 'g0', 'x')] = 2
conflict_table[('g2', 'x', 'g1', 'g0')] = 4
conflict_table[('g2', 'x', 'g1', 'g3')] = 2
conflict_table[('g2', 'x', 'g1', 'x')] = 2
conflict_table[('g2', 'x', 'g3', 'g0')] = 4
conflict_table[('g2', 'x', 'g3', 'g1')] = 4
conflict_table[('g2', 'x', 'g3', 'x')] = 0
conflict_table[('g2', 'x', 'x', 'g0')] = 2
conflict_table[('g2', 'x', 'x', 'g1')] = 2
conflict_table[('g2', 'x', 'x', 'g3')] = 0
conflict_table[('g3', 'g0', 'g1', 'g2')] = 6
conflict_table[('g3', 'g0', 'g1', 'x')] = 4
conflict_table[('g3', 'g0', 'g2', 'g1')] = 6
conflict_table[('g3', 'g0', 'g2', 'x')] = 4
conflict_table[('g3', 'g0', 'x', 'g1')] = 4
conflict_table[('g3', 'g0', 'x', 'g2')] = 4
conflict_table[('g3', 'g0', 'x', 'x')] = 2
conflict_table[('g3', 'g1', 'g0', 'g2')] = 6
conflict_table[('g3', 'g1', 'g0', 'x')] = 4
conflict_table[('g3', 'g1', 'g2', 'g0')] = 6
conflict_table[('g3', 'g1', 'g2', 'x')] = 4
conflict_table[('g3', 'g1', 'x', 'g0')] = 4
conflict_table[('g3', 'g1', 'x', 'g2')] = 4
conflict_table[('g3', 'g1', 'x', 'x')] = 2
conflict_table[('g3', 'g2', 'g0', 'g1')] = 6
conflict_table[('g3', 'g2', 'g0', 'x')] = 4
conflict_table[('g3', 'g2', 'g1', 'g0')] = 6
conflict_table[('g3', 'g2', 'g1', 'x')] = 4
conflict_table[('g3', 'g2', 'x', 'g0')] = 4
conflict_table[('g3', 'g2', 'x', 'g1')] = 4
conflict_table[('g3', 'g2', 'x', 'x')] = 2
conflict_table[('g3', 'x', 'g0', 'g1')] = 4
conflict_table[('g3', 'x', 'g0', 'g2')] = 4
conflict_table[('g3', 'x', 'g0', 'x')] = 2
conflict_table[('g3', 'x', 'g1', 'g0')] = 4
conflict_table[('g3', 'x', 'g1', 'g2')] = 4
conflict_table[('g3', 'x', 'g1', 'x')] = 2
conflict_table[('g3', 'x', 'g2', 'g0')] = 4
conflict_table[('g3', 'x', 'g2', 'g1')] = 4
conflict_table[('g3', 'x', 'g2', 'x')] = 2
conflict_table[('g3', 'x', 'x', 'g0')] = 2
conflict_table[('g3', 'x', 'x', 'g1')] = 2
conflict_table[('g3', 'x', 'x', 'g2')] = 2
conflict_table[('x', 'g0', 'g1', 'g2')] = 0
conflict_table[('x', 'g0', 'g1', 'g3')] = 0
conflict_table[('x', 'g0', 'g1', 'x')] = 0
conflict_table[('x', 'g0', 'g2', 'g1')] = 2
conflict_table[('x', 'g0', 'g2', 'g3')] = 0
conflict_table[('x', 'g0', 'g2', 'x')] = 0
conflict_table[('x', 'g0', 'g3', 'g1')] = 2
conflict_table[('x', 'g0', 'g3', 'g2')] = 2
conflict_table[('x', 'g0', 'g3', 'x')] = 0
conflict_table[('x', 'g0', 'x', 'g1')] = 0
conflict_table[('x', 'g0', 'x', 'g2')] = 0
conflict_table[('x', 'g0', 'x', 'g3')] = 0
conflict_table[('x', 'g1', 'g0', 'g2')] = 2
conflict_table[('x', 'g1', 'g0', 'g3')] = 2
conflict_table[('x', 'g1', 'g0', 'x')] = 2
conflict_table[('x', 'g1', 'g2', 'g0')] = 4
conflict_table[('x', 'g1', 'g2', 'g3')] = 0
conflict_table[('x', 'g1', 'g2', 'x')] = 0
conflict_table[('x', 'g1', 'g3', 'g0')] = 4
conflict_table[('x', 'g1', 'g3', 'g2')] = 2
conflict_table[('x', 'g1', 'g3', 'x')] = 0
conflict_table[('x', 'g1', 'x', 'g0')] = 2
conflict_table[('x', 'g1', 'x', 'g2')] = 0
conflict_table[('x', 'g1', 'x', 'g3')] = 0
conflict_table[('x', 'g2', 'g0', 'g1')] = 4
conflict_table[('x', 'g2', 'g0', 'g3')] = 2
conflict_table[('x', 'g2', 'g0', 'x')] = 2
conflict_table[('x', 'g2', 'g1', 'g0')] = 4
conflict_table[('x', 'g2', 'g1', 'g3')] = 2
conflict_table[('x', 'g2', 'g1', 'x')] = 2
conflict_table[('x', 'g2', 'g3', 'g0')] = 4
conflict_table[('x', 'g2', 'g3', 'g1')] = 4
conflict_table[('x', 'g2', 'g3', 'x')] = 0
conflict_table[('x', 'g2', 'x', 'g0')] = 2
conflict_table[('x', 'g2', 'x', 'g1')] = 2
conflict_table[('x', 'g2', 'x', 'g3')] = 0
conflict_table[('x', 'g3', 'g0', 'g1')] = 4
conflict_table[('x', 'g3', 'g0', 'g2')] = 4
conflict_table[('x', 'g3', 'g0', 'x')] = 2
conflict_table[('x', 'g3', 'g1', 'g0')] = 4
conflict_table[('x', 'g3', 'g1', 'g2')] = 4
conflict_table[('x', 'g3', 'g1', 'x')] = 2
conflict_table[('x', 'g3', 'g2', 'g0')] = 4
conflict_table[('x', 'g3', 'g2', 'g1')] = 4
conflict_table[('x', 'g3', 'g2', 'x')] = 2
conflict_table[('x', 'g3', 'x', 'g0')] = 2
conflict_table[('x', 'g3', 'x', 'g1')] = 2
conflict_table[('x', 'g3', 'x', 'g2')] = 2
conflict_table[('x', 'x', 'g0', 'g1')] = 0
conflict_table[('x', 'x', 'g0', 'g2')] = 0
conflict_table[('x', 'x', 'g0', 'g3')] = 0
conflict_table[('x', 'x', 'g1', 'g0')] = 2
conflict_table[('x', 'x', 'g1', 'g2')] = 0
conflict_table[('x', 'x', 'g1', 'g3')] = 0
conflict_table[('x', 'x', 'g2', 'g0')] = 2
conflict_table[('x', 'x', 'g2', 'g1')] = 2
conflict_table[('x', 'x', 'g2', 'g3')] = 0
conflict_table[('x', 'x', 'g3', 'g0')] = 2
conflict_table[('x', 'x', 'g3', 'g1')] = 2
conflict_table[('x', 'x', 'g3', 'g2')] = 2
def linear_conflicts(start_list,goal_list):
"""
calculates number of moves to add to the estimate of
the moves to get from start to goal based on the number
of conflicts on a given row or column. start_list
represents the current location and goal_list represnts
the final goal.
"""
# Find which of the tiles in start_list have their goals on this line
# build a pattern to use in a lookup table of this form:
# g0, g1, g3, g3 fill in x where there is no goal for this line
# all 'x' until we file a tile whose goal is in this line
goal_pattern = ['x', 'x', 'x', 'x']
for g in range(4):
for s in range(4):
start_tile_num = start_list[s]
if start_tile_num == goal_list[g] and start_tile_num != 0:
goal_pattern[s] = 'g' + str(g) # i.e. g0
global conflict_table
tup_goal_pattern = tuple(goal_pattern)
if tup_goal_pattern in conflict_table:
return conflict_table[tuple(goal_pattern)]
else:
return 0
class lcmap(dict):
"""
Lets you return 0 if you look for an object that
is not in the dictionary.
"""
def __missing__(self, key):
return 0
def listconflicts(goal_list):
"""
list all possible start lists that will have at least
one linear conflict.
Possible goal tile configurations
g g g g
g g g x
g g x g
g x g g
x g g g
g g x x
g x g x
g x x g
x g g x
x g x g
x x g g
"""
all_tiles = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
non_goal_tiles = []
for t in all_tiles:
if t not in goal_list:
non_goal_tiles.append(t)
combinations = lcmap()
# g g g g
for i in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(i)
for j in tile_list2:
tile_list3 = tile_list2[:]
tile_list3.remove(j)
for k in tile_list3:
tile_list4 = tile_list3[:]
tile_list4.remove(k)
for l in tile_list4:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# g g g x
for i in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(i)
for j in tile_list2:
tile_list3 = tile_list2[:]
tile_list3.remove(j)
for k in tile_list3:
for l in non_goal_tiles:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# g g x g
for i in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(i)
for j in tile_list2:
tile_list3 = tile_list2[:]
tile_list3.remove(j)
for k in non_goal_tiles:
for l in tile_list3:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# g x g g
for i in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(i)
for j in non_goal_tiles:
for k in tile_list2:
tile_list3 = tile_list2[:]
tile_list3.remove(k)
for l in tile_list3:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# x g g g
for i in non_goal_tiles:
for j in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(j)
for k in tile_list2:
tile_list3 = tile_list2[:]
tile_list3.remove(k)
for l in tile_list3:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# g g x x
for i in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(i)
for j in tile_list2:
tile_list3 = tile_list2[:]
tile_list3.remove(j)
for k in non_goal_tiles:
tile_list4 = non_goal_tiles[:]
tile_list4.remove(k)
for l in tile_list4:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# g x g x
for i in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(i)
for j in non_goal_tiles:
tile_list3 = non_goal_tiles[:]
tile_list3.remove(j)
for k in tile_list2:
for l in tile_list3:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# g x x g
for i in goal_list:
tile_list2 = goal_list[:]
tile_list2.remove(i)
for j in non_goal_tiles:
tile_list3 = non_goal_tiles[:]
tile_list3.remove(j)
for k in tile_list2:
for l in tile_list3:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# x g g x
for i in non_goal_tiles:
tile_list2 = non_goal_tiles[:]
tile_list2.remove(i)
for j in goal_list:
tile_list3 = goal_list[:]
tile_list3.remove(j)
for k in tile_list3:
for l in tile_list2:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# x g x g
for i in non_goal_tiles:
tile_list2 = non_goal_tiles[:]
tile_list2.remove(i)
for j in goal_list:
tile_list3 = goal_list[:]
tile_list3.remove(j)
for k in tile_list3:
for l in tile_list2:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
# x x g g
for i in non_goal_tiles:
tile_list2 = non_goal_tiles[:]
tile_list2.remove(i)
for j in tile_list2:
for k in goal_list:
tile_list3 = goal_list[:]
tile_list3.remove(k)
for l in tile_list3:
start_list = (i, j, k, l)
conflictadd = linear_conflicts(start_list,goal_list)
if conflictadd > 0:
combinations[start_list]=conflictadd
return combinations
class HeuristicObj(object):
""" Object used to preprocess goal position for heuristic function """
def __init__(self, goal):
"""
Preprocess goal position to setup internal data structures
that can be used to speed up heuristic.
"""
build_conflict_table()
self.goal_map = []
for i in range(16):
self.goal_map.append(i)
self.goal_lists = goal.tiles
# preprocess for manhattan distance
for row in range(4):
for col in range(4):
self.goal_map[goal.tiles[row][col]] = (row, col)
# make access faster by changing to a tuple
self.goal_map = tuple(self.goal_map)
# preprocess for linear conflicts
self.row_conflicts = []
for row in range(4):
t = goal.tiles[row]
conf_dict = listconflicts([t[0],t[1],t[2],t[3]])
self.row_conflicts.append(conf_dict)
self.col_conflicts = []
for col in range(4):
col_list =[]
for row in range(4):
col_list.append(goal.tiles[row][col])
conf_dict = listconflicts(col_list)
self.col_conflicts.append(conf_dict)
def heuristic(self, start):
"""
Estimates the number of moves from start to goal.
The goal was preprocessed in __init__.
"""
distance = 0
# local variables for instance variables
t = start.tiles
g = self.goal_map
rc = self.row_conflicts
cc = self.col_conflicts
# calculate manhattan distance
for row in range(4):
for col in range(4):
start_tilenum = t[row][col]
if start_tilenum != 0:
(grow, gcol) = g[start_tilenum]
distance += abs(row - grow) + abs(col - gcol)
# add linear conflicts
for row in range(4):
curr_row = t[row]
distance += rc[row][curr_row]
for col in range(4):
col_tuple = (t[0][col], t[1][col], t[2][col], t[3][col])
distance += cc[col][col_tuple]
return distance
# global variable for heuristic object
hob = None
def a_star(start_tiles, goal_tiles):
""" Based on https://en.wikipedia.org/wiki/A*_search_algorithm """
start = new_position(start_tiles)
goal = new_position(goal_tiles)
# Process goal position for use in heuristic
global hob
hob = HeuristicObj(goal)
# The set of currently discovered nodes that are not evaluated yet.
# Initially, only the start node is known.
# For the first node, the fscore is completely heuristic.
start.fscore = hob.heuristic(start)
openSet = PriorityQueue([start])
# The cost of going from start to start is zero.
start.gscore = 0
num_popped = 0
while openSet.queue_length > 0:
current = openSet.pop()
if current == None: # tried to pop but only found old fscore values
break
num_popped += 1
if num_popped % 100000 == 0:
print(str(num_popped)+" positions examined")
if current == goal:
return reconstruct_path(current)
for neighbor in current.neighbors():
# The distance from start to a neighbor
# All nodes are 1 move from their neighbors
tentative_gScore = current.gscore + 1
# update gscore and fscore if this is shorter path
# to the neighbor node
if tentative_gScore < neighbor.gscore:
neighbor.cameFrom = current
neighbor.gscore = tentative_gScore
neighbor.fscore = neighbor.gscore + hob.heuristic(neighbor)
openSet.push(neighbor) # add to open set every time
def find_zero(tiles):
""" file the 0 tile """
for row in range(4):
for col in range(4):
if tiles[row][col] == 0:
return (row, col)
def path_as_0_moves(path):
"""
Takes the path which is a list of Position
objects and outputs it as a string of rlud
directions to match output desired by
Rosetta Code task.
"""
strpath = ""
if len(path) < 1:
return ""
prev_pos = path[0]
p_row, p_col = find_zero(prev_pos.tiles)
for i in range(1,len(path)):
curr_pos = path[i]
c_row, c_col = find_zero(curr_pos.tiles)
if c_row > p_row:
strpath += 'd'
elif c_row < p_row:
strpath += 'u'
elif c_col > p_col:
strpath += 'r'
elif c_col < p_col:
strpath += 'l'
# reset for next loop
prev_pos = curr_pos
p_row = c_row
p_col = c_col
return strpath
</lang>
Output:
<pre>
C:\bobby\15puzzlesolver\my15puzzlesolver>testone.py
100000 positions examined
200000 positions examined
300000 positions examined
400000 positions examined
500000 positions examined
600000 positions examined
700000 positions examined
800000 positions examined
Path length = 52
Path using rlud:
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
Run time in seconds: 56.601139201
</pre>
| |||