Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
breadth-first search solution in Clear category for The 88th Puzzle by David_Jones
from collections import deque
GOAL = (1, 2, 1, 0, 2, 0, 0, 3, 0, 4, 3, 4)
def puzzle88(state):
state = list(map(str, state))
visited = set()
queue = deque([(list(map(str, GOAL)), '')])
while queue:
current_state, steps = queue.popleft()
if current_state == state:
return steps[::-1]
visited.add(''.join(current_state))
for i, step in zip((0,1,5,6), '1234'):
new_state = current_state[:]
new_state[i], new_state[i+2], new_state[i+3], new_state[i+5] = \
new_state[i+3], new_state[i], new_state[i+5], new_state[i+2]
if ''.join(new_state) not in visited:
queue.append((new_state, steps+step))
May 21, 2019
