8puzzle.py

import math
from random import randrange
from copy import deepcopy


class Puzzle:
    def __init__(self):
        self.board = [
            [1, 2, 3],
            [4, 5, 6],
            [7, 8, 0]
        ]
        self.path = []
        self.moves = []
        self.last_move = None

    def randomize(self):
        shuffle_moves = randrange(100, 200)
        for i in range(shuffle_moves):
            piece = randrange(0, 9)
            self.move(piece)

    def print(self, board=None):
        if board is None:
            board = self.board
        for row in board:
            for col in row:
                out = str(col)
                if col == 0:
                    out = ' '
                print(out, end=' ')
            print('')

    def print_all(self, moves):
        for board in moves:
            self.print(board)
            print('---')

    def get_blank_space_position(self):
        for i in range(3):
            for j in range(3):
                element = self.board[i][j]
                if element == 0:
                    return [i, j]

    def swap(self, i1, j1, i2, j2):
        temp = self.board[i1][j1]
        self.board[i1][j1] = self.board[i2][j2]
        self.board[i2][j2] = temp

    def get_move(self, piece):
        line, column = self.get_blank_space_position()
        if line > 0 and piece == self.board[line - 1][column]:
            return 'D'
        elif line < 2 and piece == self.board[line + 1][column]:
            return 'U'
        elif column > 0 and piece == self.board[line][column - 1]:
            return 'R'
        elif column < 2 and piece == self.board[line][column + 1]:
            return 'L'
        else:
            return None

    def move(self, piece):
        move = self.get_move(piece)
        if move is None:
            return None

        line, column = self.get_blank_space_position()
        if move == 'L':
            self.swap(line, column, line, column + 1)
        elif move == 'R':
            self.swap(line, column, line, column - 1)
        elif move == 'U':
            self.swap(line, column, line + 1, column)
        elif move == 'D':
            self.swap(line, column, line - 1, column)
        self.last_move = piece
        return move

    def is_goal_state(self):
        for i in range(3):
            for j in range(3):
                piece = self.board[i][j]
                if piece != 0:
                    line = math.floor((piece - 1) / 3)
                    column = (piece - 1) % 3
                    if i != line or j != column:
                        return False
        return True

    def get_copy(self):
        n_puzzle = Puzzle()
        n_puzzle.board = deepcopy(self.board)
        for path in self.path:
            n_puzzle.path.append(path)
        for move in self.moves:
            n_puzzle.moves.append(move)
        return n_puzzle

    def get_allowed_moves(self):
        moves = []
        for i in range(3):
            for j in range(3):
                piece = self.board[i][j]
                if self.get_move(piece) is not None:
                    moves.append(piece)
        return moves

    def visit(self):
        children = []
        all_moves = self.get_allowed_moves()
        for move in all_moves:
            if move != self.last_move:
                new = self.get_copy()
                new.move(move)
                new.path.append(move)
                new.moves.append(deepcopy(self.board))
                children.append(new)
        return children

    def solve(self, should_print=False):
        start = self.get_copy()
        start.path = []
        start.moves = []
        states = [start]
        while len(states) > 0:
            state = states.pop(0)
            if state.is_goal_state():
                if should_print:
                    self.print_all(state.moves)
                    self.print(state.board)
                return state.path
            states.extend(state.visit())


p = Puzzle()
print('Initial')
p.print()
print()
print('Randomized')
p.randomize()
p.print()
print('\n' * 2)

print('Solution')
p.solve(True)