12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For those not familiar with the npuzzle, please read the link provided... \$\endgroup\$ – st0le Mar 9 '11 at 7:02
  • \$\begingroup\$ in your question , shouldn't grid which is filled with numbers from 0-9 be grid which is filled with numbers from 0-8 ? \$\endgroup\$ – Clyde Lobo Mar 9 '11 at 9:07
  • \$\begingroup\$ @Clyde, Oops! :) Fixed. \$\endgroup\$ – st0le Mar 9 '11 at 10:14
  • \$\begingroup\$ Pretty sure it's always possible to solve, right? \$\endgroup\$ – Magic Octopus Urn Aug 1 '17 at 13:50
  • \$\begingroup\$ @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 \$\endgroup\$ – st0le Aug 1 '17 at 19:38
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ like the ' '*3 trick. \$\endgroup\$ – st0le Mar 10 '11 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.