Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Mathematics and Computer Science
Commedia dell' arte again
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 1, Accepted users: 0
Problem 10043 : No special judgement
Problem description
  So called commedia dell' arte is a theater genre first played at Italy in the beginning of the sixteenth century. It was inspired with the Roman Theater. The play had no fixed script and the actors (also called performers) had to improvise a lot. There were only a simple directions by the author like "enter the stage and make something funny" or "everyone comes on stage and everything is resolved happily". You can see it might be very interesting to play the commedia dell' arte. Therefore the ACM want to put a new play on a stage, which was completely unknown before. The main hero has a puzzle that takes a very important role in the play and gives an opportunity of many improvisations. The puzzle is the worldwide known Lloyd's Fifteen Puzzle. ACM wants to make the play more interesting so they want to replace the "standard" puzzle with a three-dimensional one. The puzzle consists of a cube containing M3 slots. Each slot except one contains a cubic tile (one position is free). The tiles are numbered from 1 to M3-1. The goal of the puzzle is to determine whether it is possible to switch one of the given state to another given state . The only allowed moves are sliding a neighbouring tile into the free position along one of the three principal directions. Original configuration is when slot with coordinates (x,y,z) from {0,...,M-1}3 contains tile number z.M2+y.M+x+1 and slot (M-1,M-1,M-1) is free.

Your are to write a program to determine whether it is possible to solve the puzzle or not.


Input
  The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. The first line of each case contains only one integer M, 1 <= M <= 100. It is the size of 3D puzzle cube. Then follow 2*M lines, each contains exactly M2 numbers on the tiles for one layer. First is the layer on the top of the cube and the last one on the bottom. In each layer numbers are arranged from the left top corner linewise to the right bottom corner of the layer. In other words, slot with coordinates (x,y,z) is described by the (x+M.y+1)-th number on the (z+1)-th line. Numbers are separated by space. Number 0 means free position. The first M line indicate the initial state of puzzle cube, while the next M line indicate the final state of the puzzle cube.

Output
  For each case, print exactly one line. If the final state configuration can be reached by sliding the initial state of puzzle cube tiles, print the sentence 'Puzzle can be solved.'. Otherwise, print the sentence 'Puzzle is unsolvable.'.

Sample Input
2
2
1 2 3 4
5 7 6 0
1 2 3 4
5 6 7 0
4
49 33 40 6 10 56 7 3 59 31 5 17 37 13 41 52 
35 20 28 1 26 18 16 34 4 0 27 48 32 51 44 30 
22 58 42 43 61 15 55 53 11 62 24 14 60 54 36 25 
57 23 12 45 39 50 29 47 19 9 2 8 63 21 46 38 
42 44 28 52 62 9 4 55 56 22 47 6 27 39 26 0 
7 15 36 40 49 37 31 29 17 60 20 24 58 14 63 16 
23 18 61 21 41 35 13 2 8 57 12 50 10 11 1 45 
43 51 32 33 34 53 48 19 38 30 59 3 46 25 5 54 
Sample Output
Puzzle is unsolvable.
Puzzle can be solved.
Problem Source
  Modify from Central Europe 1998

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:1356 today,10434440 total, since 2010-05-07