# Solve the 8 Puzzle

The 8 Puzzle is the smaller variant of the 15Puzzle (or the Sliding puzzle). You have a 3x3 grid which is filled with numbers from 0-8 (0 denotes the blank tile) arranged in a random order. Your task is to input a 3x3 grid and show the shortest solution (minimum moves) to get to the goal state. Display each boardstate including the first state in the output.

There may be multiple optimal solutions, you just need to print one.

Input: (small example)

1 2 0
4 5 3
7 8 6


Output:

2 <- denotes minimum number of moves required
1 2 0
4 5 3
7 8 6

1 2 3
4 5 0
7 8 6

1 2 3
4 5 6
7 8 0 <- goal state


If the puzzle can't be solved, print just -1 (denoting unsolvable)

Edit: Time limit : < 30seconds.

• For those not familiar with the npuzzle, please read the link provided... Mar 9 '11 at 7:02
• in your question , shouldn't grid which is filled with numbers from 0-9 be grid which is filled with numbers from 0-8 ? Mar 9 '11 at 9:07
• @Clyde, Oops! :) Fixed. Mar 9 '11 at 10:14
• Pretty sure it's always possible to solve, right? Aug 1 '17 at 13:50
• @MagicOctopusUrn If you arrived at the initial state from the Goal state using the sliding rules, it's always solvable. If you arbitrarily put in tiles then there are states that cannot be solved. Google for Solvability for n puzzle Aug 1 '17 at 19:38

## Python, 418 characters

The code exhaustively enumerates all positions and makes maps of their depth (D), and a position one closer to solved (E). Then it looks up the goal state to get the output.

D={(1,2,3,4,5,6,7,8,0):0}
E=D.copy()
def Z(a,d):
b=list(a);b[i],b[i+d]=b[i+d],0;b=tuple(b)
if b not in E:E[b]=a;D[b]=D[a]+1
for x in' '*32:
for a in E.copy():
i=list(a).index(0)
if i>2:Z(a,-3)
if i%3:Z(a,-1)
if i%3<2:Z(a,1)
if i<6:Z(a,3)
g=[]
for x in' '*3:g+=map(int,raw_input().split())
g=tuple(g)
if g in E:
print D[g]
while g:
for i in(0,3,6):print'%d %d %d'%g[i:i+3]
g=E[g];print
else:print -1

• like the ' '*3 trick. Mar 10 '11 at 4:47