<PREV Problem:
NEXT>
Solved by 15 users: WsemirZ, JohnJones_001, zloy_mipt, pmnox, UdH-WiNGeR, regal, defrager, Rizvanov, Dest, EAA2008, fetetriste, ripatti, dan, vi002, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

3D puzzle

Time limit = 5 second(s)

This problem is about 3D-version 3x3x3 of wellknown 15-puzzle.

Initial position corresponds to

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

"0" stands for empty cell.

верхний		средний		нижний
слой 0:		слой 1:		слой 2:

0 1 2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 6 7 8 15 16 17 24 25 26

Input Description of position — permutation od numbers {0,1,..,26}.

Output Output IMPOSSIBLE if thereis now way to get initial position.

Output K+1 line if there is way to get initial position by K moves. K may be not minimal one, but less than 500.

The first line has description of given position. Next K lines should contain descriptions of positions.

i-th position should be achiieved from the (i-1)-th position by on move.

Input#1
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Output#1
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Input#2
 0  2  1  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Output#2
IMPOSSIBLE

Input#3
 3  1  2  0  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Output#3
 3  1  2  0  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Input#4
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14  0 25 17 18 19 20 21 22 23 15 24 26

Output#4
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14  0 25 17 18 19 20 21 22 23 15 24 26  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23  0 24 26  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23 24  0 26  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23 24 26  0  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23 24  0 26 
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15  0 17 18 19 20 21 22 23 24 25 26 
 3  1  2  4 13  5  6  7  8  9 10 11 12  0 14 15 16 17 18 19 20 21 22 23 24 25 26 
 3  1  2  4  0  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  
 3  1  2  0  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26



Author:
Vladimir Povolotsky
23 May 2008

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.162.181.75