Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Simple BFS solution in Clear category for The 88th Puzzle by nickie
from collections import deque
GOAL = (1,2,1,0,2,0,0,3,0,4,3,4)
def puzzle88(state):
# The indices of the marbles that rotate, in each move
MOVES = ((2,5,3,0), (3,6,4,1), (7,10,8,5), (8,11,9,6))
# The rest is a simple BFS
seen = set([state])
queue = deque([(state, "")])
while queue:
(s, moves) = queue.popleft()
if s == GOAL:
return moves
for disc, r in enumerate(MOVES):
# calculate the next state
n = list(s)
j = r[0]
x = n[j]
for i in r:
n[j] = n[i]
j = i
n[j] = x
t = tuple(n)
# if not already seen, add it for further examination
if t not in seen:
seen.add(t)
queue.append((t, moves + str(1+disc)))
June 1, 2015
