Skip to content
{{ message }}

Instantly share code, notes, and snippets.

fa7ad/8puzzle.py

Created Feb 6, 2019
 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)
to join this conversation on GitHub. Already have an account? Sign in to comment