from copy import deepcopy
from queue import PriorityQueue
def arr2grid(arr):
return [ [arr[0], arr[1], arr[2]], [arr[3], arr[4], arr[5]], [arr[6], arr[7], arr[8]] ]
def distance(grid):
m = {1:(0, 0), 2:(0, 1), 3:(0, 2), 4:(1,0), 5:(1, 1), 6:(1, 2), 7:(3, 0), 8:(3,1), 0:(3, 2)}
ans = 0
for i in range(3):
for j in range(3):
ii, jj = m[grid[i][j]]
ans += abs(i - ii) + abs(j - jj)
return ans
def hash(grid):
ans = 0
base = 1
for i in range(3):
for j in range(3):
ans += base * grid[i][j]
base *= 10
return ans
s = input().split()
arr = []
for val in s:
if val == 'x':
arr.append(0)
else:
arr.append(int(val))
rev_cnt = 0
for i in range(9):
if arr[i] != 0:
for j in range(i):
if arr[j] > arr[i]:
rev_cnt += 1
if rev_cnt % 2 == 1:
print('unsolvable')
else:
init_grid = arr2grid(arr)
pos_i, pos_j = -1, -1
for i in range(3):
for j in range(3):
if init_grid[i][j] == 0:
pos_i, pos_j = i, j
break
min_heap = PriorityQueue()
min_heap.put( (distance(init_grid), 0, pos_i, pos_j, init_grid, hash(init_grid)) ) # (预估距离,真实距离,0位置i, 0位置j, 方阵, hash值)
best_stat = { hash(init_grid): (0, None, None) } # (开销值,上一个状态到这个状态的移动方式,上一个状态)
target = [[1,2,3], [4,5,6], [7,8,0]]
target_hash = hash(target)
flag = False
while not min_heap.empty():
_, dis, pos_i, pos_j, cur_grid, hash_code = min_heap.get()
#print(cur_grid)
if hash_code == target_hash:
# 倒推路径
cur = cur_grid
path = []
while cur:
key = hash(cur)
if best_stat[key][1]:
path.append(best_stat[key][1])
cur = best_stat[key][2]
path = path[::-1]
print(''.join(path))
flag = True
break
if pos_i >= 1:
new_grid = deepcopy(cur_grid)
new_grid[pos_i][pos_j], new_grid[pos_i-1][pos_j] = new_grid[pos_i-1][pos_j], new_grid[pos_i][pos_j]
key = hash(new_grid)
if key not in best_stat or dis + 1 < best_stat[key][0]:
best_stat[key] = (dis+1, 'u', cur_grid)
min_heap.put( (dis+1+distance(new_grid), dis+1, pos_i-1, pos_j, new_grid, key) )
if pos_i <= 1:
new_grid = deepcopy(cur_grid)
new_grid[pos_i][pos_j], new_grid[pos_i+1][pos_j] = new_grid[pos_i+1][pos_j], new_grid[pos_i][pos_j]
key = hash(new_grid)
if key not in best_stat or dis + 1 < best_stat[key][0]:
best_stat[key] = (dis+1, 'd', cur_grid)
min_heap.put( (dis+1+distance(new_grid), dis+1, pos_i+1, pos_j, new_grid, key) )
if pos_j >= 1:
new_grid = deepcopy(cur_grid)
new_grid[pos_i][pos_j], new_grid[pos_i][pos_j-1] = new_grid[pos_i][pos_j-1], new_grid[pos_i][pos_j]
key = hash(new_grid)
if key not in best_stat or dis + 1 < best_stat[key][0]:
best_stat[key] = (dis + 1, 'l', cur_grid)
min_heap.put((dis + 1 + distance(new_grid), dis + 1, pos_i, pos_j - 1, new_grid, key))
if pos_j <= 1:
new_grid = deepcopy(cur_grid)
new_grid[pos_i][pos_j], new_grid[pos_i][pos_j+1] = new_grid[pos_i][pos_j+1], new_grid[pos_i][pos_j]
key = hash(new_grid)
if key not in best_stat or dis + 1 < best_stat[key][0]:
best_stat[key] = (dis + 1, 'r', cur_grid)
min_heap.put((dis + 1 + distance(new_grid), dis + 1, pos_i, pos_j + 1, new_grid, key))