Skip to content

Instantly share code, notes, and snippets.

@fa7ad

fa7ad/8puzzle.py

Created Feb 6, 2019
Embed
What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment