Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for 8 Puzzle by Moff
class Board(object):
def __init__(self, blocks):
self.size = len(blocks)
self.blocks = [row[::] for row in blocks]
def goal(self, i, j):
if i == self.size - 1 and j == self.size - 1:
return 0
else:
return i * self.size + j + 1
def hamming(self):
count = 0
for i in range(self.size):
for j in range(self.size):
if self.blocks[i][j] != 0 and self.blocks[i][j] != self.goal(i, j):
count += 1
return count
def is_goal(self):
return self.hamming() == 0
def manhattan(self):
sum_ = 0
for i in range(self.size):
for j in range(self.size):
val = self.blocks[i][j]
if val != 0 and val != self.goal(i, j):
x = (val - 1) // self.size
y = val - 1 - x * self.size
sum_ += abs(i - x) + abs(j - y)
return sum_
def __eq__(self, other):
if other is None:
return False
if self.__class__ != other.__class__:
return False
if self.size != other.size:
return False
for i in range(self.size):
for j in range(self.size):
if self.blocks[i][j] != other.blocks[i][j]:
return False
return True
def twin(self):
obj = Board(self.blocks)
for i in range(self.size):
for j in range(self.size - 1):
if self.blocks[i][j] != 0 and self.blocks[i][j + 1] != 0:
obj.exch(i, j, i, j + 1)
return obj
return obj
def exch(self, i, j, it, jt):
if 0 <= it < self.size and 0 <= jt < self.size:
self.blocks[i][j], self.blocks[it][jt] = self.blocks[it][jt], self.blocks[i][j]
return True
return False
def neighbors(self):
boards = []
i0 = j0 = 0
for i in range(self.size):
for j in range(self.size):
if self.blocks[i][j] == 0:
i0, j0 = i, j
for d, di, dj in [('U', -1, 0), ('L', 0, -1), ('R', 0, 1), ('D', 1, 0)]:
board = Board(self.blocks)
if board.exch(i0, j0, i0 + di, j0 + dj):
boards.append((d, board))
return boards
class Solver(object):
class Node(object):
def __init__(self, board, direction, moves, prev):
self.board = board
self.direction = direction
self.moves = moves
self.previous = prev
self.priority = moves + board.manhattan()
def __gt__(self, other):
return self.priority > other.priority
def __init__(self, initial):
self.search_pq = [self.Node(initial, '', 0, None)]
self.twin_pq = [self.Node(initial.twin(), '', 0, None)]
while not self.search_pq[0].board.is_goal() and not self.twin_pq[0].board.is_goal():
self.check_neighbors(self.search_pq)
self.check_neighbors(self.twin_pq)
@property
def is_solvable(self):
return self.search_pq[0].board.is_goal()
def check_neighbors(self, pq):
min_ = pq.pop(0)
for direction, neighbor in min_.board.neighbors():
if min_.previous is not None and neighbor == min_.previous.board:
continue
pq.append(self.Node(neighbor, direction, min_.moves + 1, min_))
pq.sort()
def solution(self):
if not self.is_solvable:
return None
solution = []
node = self.search_pq[0]
while node is not None:
solution.insert(0, node.direction)
node = node.previous
return solution
def checkio(m):
"""A*-algorithm for solve not only 3x3-puzzle"""
return ''.join(Solver(Board(m)).solution())
Aug. 22, 2015