Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for 8 Puzzle by gyahun_dash
from itertools import chain
from operator import sub
steps = {'U': -3, 'D': 3, 'L': -1, 'R': 1}
dirs = 'DR', 'DLR', 'DL', 'DRU', 'DLRU', 'DLU', 'RU', 'LRU', 'LU'
def checkio(puzzle, goal=(1, 2, 3, 4, 5, 6, 7, 8, 0)):
def sum_manhattans(state):
pairs = ((x.index(i) for x in (goal, state)) for i in range(9))
subvals = chain(*(map(sub, *(divmod(n, 3) for n in p)) for p in pairs))
return sum(map(abs, subvals))
used = set()
states = {tuple(chain(*puzzle)): ''}
while True:
state = min(states, key=sum_manhattans)
move = states.pop(state)
if state == goal: return move
used.add(state)
index = state.index(0)
for dr in dirs[index]:
trans = {index + steps[dr]: 0, index: state[index + steps[dr]]}
news = tuple(trans.get(j, n) for j, n in enumerate(state))
if news not in (used | set(states)):
states[news] = move + dr
Oct. 27, 2014
Comments: