Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS: brute force search solution in Clear category for The 88th Puzzle by Rcp8jzd
from typing import Tuple
from collections import deque
State = Tuple[int]
GOAL = (1, 2, 1, 0, 2, 0, 0, 3, 0, 4, 3, 4)
RINGS = {1: (0, 3, 5, 2),
2: (1, 4, 6, 3),
3: (5, 8, 10, 7),
4: (6, 9, 11, 8)}
def move_state(state: State, ring_number: int) -> State:
"""Gives the updated state after moving the given ring clockwise.
:param state: 12 ints ranging from 0 to 4 representing the puzzle.
:param ring_number: The ring you want to move.
:return: The new state.
"""
new_state = list(state)
# State of the selected ring
ring = deque(state[i] for i in RINGS[ring_number])
# Rotate clockwise
ring.rotate(1)
for ring_index, index in enumerate(RINGS[ring_number]):
new_state[index] = ring[ring_index]
return tuple(new_state)
def puzzle88(state) -> str:
"""Solve the 88th puzzle and give the shortest solution as a str of the
rings you have to rotate.
:param state: Initial state of the puzzle.
:return: Solution, sequence of rings you have to rotate.
"""
seen = {state}
queue = deque([(state, '')])
while queue:
current_state, moves = queue.popleft()
if current_state == GOAL:
return moves
for ring_number in range(1, 5):
new_state = move_state(current_state, ring_number)
new_moves = moves + str(ring_number)
if tuple(new_state) not in seen:
seen.add(tuple(new_state))
queue.append((new_state, new_moves))
June 30, 2020
Comments: