Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
8 Puzzle solution in Uncategorized category for 8 Puzzle by capback250
# migrated from python 2.7
from copy import deepcopy
from functools import reduce
COORDS = ((-1, 0), (0, -1), (0, 1), (1, 0))
MOVES = {(-1, 0): 'U', (0, -1): 'L', (0, 1): 'R', (1, 0): 'D'}
TARGET = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
def checkio(puzzle):
queqe, checked , curr = [], [], []
queqe.append(diffPositions([puzzle, '']))
while 1:
queqe = sorted(queqe, key=lambda x: x[2], reverse=True)
current = queqe.pop()
# print current
mtx, path, cost = current
if mtx == TARGET:
return path
checked.append(mtx)
zx, zy = [(i, j) for i in range(3) for j in range(3) if not mtx[i][j]][0]
for c in COORDS:
dx, dy = zx + c[0], zy + c[1]
if 0 <= dx < 3 and 0 <= dy < 3:
nextMove = movemaker(mtx, MOVES[c], zx, zy)
if nextMove not in checked and nextMove not in curr:
curr.append(nextMove)
queqe.insert(0, diffPositions([nextMove, path + MOVES[c]]))
def diffPositions(array):
diff = 0
a = reduce(list.__add__, [x for x in array[0]])
b = reduce(list.__add__, [x for x in TARGET])
for i in range(len(a)):
if a[i] != b[i]:
diff += 1
return array + [diff + len(array[1])]
def movemaker(matrix, code, zx, zy):
copy = deepcopy(matrix)
if code == 'U':
copy[zx][zy] = copy[zx - 1][zy]
copy[zx - 1][zy] = 0
elif code == 'L':
copy[zx][zy] = copy[zx][zy - 1]
copy[zx][zy - 1] = 0
elif code == 'R':
copy[zx][zy] = copy[zx][zy + 1]
copy[zx][zy + 1] = 0
else:
copy[zx][zy] = copy[zx + 1][zy]
copy[zx + 1][zy] = 0
return copy
Feb. 26, 2016
