  # Untitled unknown
plain_text
7 months ago
2.4 kB
5
Indexable
Never
```#A*
import sys
from heapq import heappop, heappush

COLUMNS = 4
ROWS = 3

dist = [[abs(t // COLUMNS - s // COLUMNS) + abs(t % COLUMNS - s % COLUMNS) if s > 0 else 0
for t in range(ROWS * COLUMNS)]
for s in range(ROWS * COLUMNS)]

def compute_empty_position(grid):
for i, v in enumerate(grid):
if v == 0:
return i

def heuristic(grid):
return sum(dist[rv][index] for index, rv in enumerate(grid))

class Node(object):
def __init__(self, grid, actions, empty_position, h, last=None):
self.grid = grid
self.actions = actions
self.h = h
self.dist = len(self.actions) + h
self.last = last
self.empty_position = empty_position

def neighboors(self):
possibilities = []
i = self.empty_position
col = i % COLUMNS
if col + 1 < COLUMNS and self.last != 2:
possibilities.append((i + 1, 1))
if col > 0 and self.last != 1:
possibilities.append((i - 1, 2))
if i < (ROWS - 1) * COLUMNS and self.last != 4:
possibilities.append((i + COLUMNS, 3))
if i >= COLUMNS and self.last != 3:
possibilities.append((i - COLUMNS, 4))

for action, move in possibilities:
before = dist[self.grid[i]][i] + dist[self.grid[action]][action]

new_grid = list(self.grid)
new_grid[i], new_grid[action] = new_grid[action], new_grid[i]
new_grid = tuple(new_grid)

after = dist[new_grid[i]][i] + dist[new_grid[action]][action]

yield Node(new_grid, self.actions + [action], action, self.h - before + after, move)

def __lt__(self, other):
return self.dist < other.dist

def solve(grid):
orig = grid[:]
visited = set()
q = [Node(orig, [], compute_empty_position(orig), heuristic(orig))]
while q:
node = heappop(q)
if node.h == 0:
return node.actions
for n in node.neighboors():
if n.grid not in visited:
heappush(q, n)
print("no solution found!")

if __name__ == '__main__':
grid = tuple(int(x) for _ in range(ROWS) for x in input().split(" "))
res = solve(grid)
for action in res:
print(action // COLUMNS, action % COLUMNS)```  