Solved by 272 users: ...
UserDateAttemptTimeCMSC
12whoami34`10 sep 2012`Ruby105.23250
Darii`23 oct 2010`C++2501.77318
kostya1996`30 jul 2014`C++2501.87328
Rizvanov`15 sep 2009`C++100.22347
Darii`23 oct 2010`C++2601.76350
Rizvanov`15 sep 2009`C++200.16369
Philip_PV`07 jul 2008`C++400.68378
MasterYoda`14 oct 2010`C++1701.80388
Remag`12 mar 2010`C++700.77406
Philip_PV`07 jul 2008`C++300.39410
Rizvanov`15 sep 2009`C++300.04415
var`04 may 2007`C++1301.50416
NSI`27 mar 2006`C++201.88416
Rizvanov`15 sep 2009`C++500.04422
Remag`12 mar 2010`C++500.75422
Rizvanov`15 sep 2009`C++400.04423
frost_nova`07 mar 2009`C++100.80433
 C++ 199 FPC 38 Java 17 Kylix 17 C 6 Ruby 1
` >  >  >  >  >  >  >  >  >  > `

## 8-puzzle

Time limit = 2 second(s)

Memory limit = 10Mb

8-puzzle is analogue of the wellknown 15-puzzle. There is square region of size 3x3 with 8 square paves of size 1x1 inside. One small square inside is not paved. You can move one of the paves to the empty square.

The target position is displayed in the Figure 1.

 1 2 3 4 5 6 7 8

Figure 1. Target position.

 a1 a2 a3 a4 a5 a6 a7 a8 a9

Figure 2. Order of squares in input data.

Your task is to reach target position starting with given position and make minimal number of moves.

Input. Input consists of one line with identifiers a1 a2 .. a9 corresponding to paves numbers of the position (see Fig. 2). Identifier 0 stands for empty square.

Output. Output "Yes" if given puzzle is solvable, and "No" otherwise. If "Yes" then output minimal number of moves.

 Input#1```1 2 3 4 5 6 7 8 0 ``` Output#1```Yes 0 ```
 Input#2```0 1 2 3 4 5 6 7 8 ``` Output#2```Yes 22 ```

Author:
Folklor. Tests and description by Vladimir Chelnokov.
5 March 2006

 © acm.mipt DevGroupThe page was generated in 200ms