Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
colin_8_puzzle solution in Clear category for 8 Puzzle by colinmcnicholl
from collections import deque, namedtuple
from operator import eq
class Puzzle(namedtuple("PuzzleFields", ["board", "width", "zero_at"])):
"""A class representing an '8-puzzle'."""
def __new__(cls, board, width, zero_at=None):
if zero_at is None:
zero_at = board.index(0)
return super().__new__(cls, board, width, zero_at)
def solved(self):
"""The puzzle is solved if the flattened board's numbers are in
increasing order from left to right and the '0' tile is in the
last position on the board."""
return all(map(eq, self.board, range(1, self.width**2)))
def actions(self):
"""Output: a list of 'move', 'action' pairs. 'move' can be called
to return a new puzzle that results in sliding the '0' tile in
the direction of 'action'."""
at = self.zero_at
if at >= self.width:
yield self._move(at - self.width)
if at + self.width < len(self.board):
yield self._move(at + self.width)
if at % self.width:
yield self._move(at - 1)
if (at + 1) % self.width:
yield self._move(at + 1)
def _move(self, to):
"""Output: a new puzzle where 'zero_at' and 'to' tiles have been swapped.
NOTE: all moves should be 'actions' that have been executed."""
a, b = min(self.zero_at, to), max(self.zero_at, to)
board = list(self.board)
board[a], board[b] = board[b], board[a]
return Puzzle(tuple(board), self.width, to)
class Node(namedtuple("NodeFields", ["puzzle", "parent"])):
"""A class representing a Solver node.
- 'puzzle' is a Puzzle instance.
- 'parent' is the preceding node generated by the solver, if any.
- 'action' is the action taken to produce puzzle, if any. """
def __new__(cls, puzzle, parent=None):
return super().__new__(cls, puzzle, parent)
@property
def action(self):
if self.parent is None:
return None
diff_to_action = {
+self.puzzle.width: 'D',
-self.puzzle.width: 'U',
+1: 'R',
-1: 'L',
}
return diff_to_action[self.puzzle.zero_at - self.parent.puzzle.zero_at]
def path(node):
"""Reconstruct a path from to the root 'parent'."""
seen = []
while node is not None:
seen.append(node)
node = node.parent
return reversed(seen)
def solve(start):
"""Perform breadth first search and return a path to the solution,
if it exists (otherwise None)."""
queue = deque([Node(start)])
seen = {start}
if start.solved():
return path(Node(start, None))
while queue:
node = queue.pop()
for move in node.puzzle.actions():
if move.board not in seen:
if move.solved():
return path(Node(move, node))
queue.appendleft(Node(move, node))
seen.add(move.board)
def flat_list(array):
"""Input: A list of lists, e.g. [[1, 2, 3],[4, 6, 8],[7, 5, 0]]
Output: A tuple, e.g., (1,2,3,4,6,8,7,7,0)."""
def flat(item):
for element in item:
if isinstance(element, list):
yield from flat_list(element)
else:
yield element
return tuple(flat(array))
from typing import List
def checkio(puzzle: List[List[int]]) -> str:
"""Input: A matrix with numbers from 1 to 8 as a list of lists with integers.
Breadth first search algorithm implementation.
Output: The route of the empty cell as a string.
"""
board = flat_list(puzzle)
puzz = Puzzle(board, 3)
p = solve(puzz)
actions = ""
for node in p:
actions += str(node.action)
directions = actions[4:]
return directions
if __name__ == '__main__':
print("Example:")
print(checkio([[1, 2, 3],
[4, 6, 8],
[7, 5, 0]]))
#This part is using only for self-checking and not necessary for auto-testing
GOAL = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
MOVES = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def check_solution(func, puzzle):
size = len(puzzle)
route = func([row[:] for row in puzzle])
goal = GOAL
x = y = None
for i, row in enumerate(puzzle):
if 0 in row:
x, y = i, row.index(0)
break
for ch in route:
swap_x, swap_y = x + MOVES[ch][0], y + MOVES[ch][1]
if 0 <= swap_x < size and 0 <= swap_y < size:
puzzle[x][y], puzzle[swap_x][swap_y] = puzzle[swap_x][swap_y], 0
x, y = swap_x, swap_y
if puzzle == goal:
return True
else:
print("Puzzle is not solved")
return False
assert check_solution(checkio, [[1, 2, 3],
[4, 6, 8],
[7, 5, 0]]), "1st example"
assert check_solution(checkio, [[7, 3, 5],
[4, 8, 6],
[1, 2, 0]]), "2nd example"
print("Coding complete? Click 'Check' to earn cool rewards!")
Aug. 7, 2018
