COMMEDIA - Commedia dell Arte

So called commedia dell' arte is a theater genre first played in Italy at 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 get the original ordering of the tiles after they have been randomly reshuffled. 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.

You 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 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.

Output

For each case, print exactly one line. If the original configuration can be reached by sliding the tiles, print the sentence 'Puzzle can be solved.'. Otherwise, print the sentence 'Puzzle is unsolvable.'.

Example

Sample input:
2
2
1 2 3 4
5 7 6 0
2
2 1 3 5
4 6 0 7

Sample output:
Puzzle is unsolvable.
Puzzle can be solved.
Warning: large Input/Output data, be careful with certain languages

Added by:adrian
Date:2004-06-06
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:ACM Central European Programming Contest, Prague 1998

hide comments
2024-07-09 10:43:00
https://www.youtube.com/watch?v=YI1WqYKHi78
2019-07-04 13:53:40 Akshay Aradhya
https://www.youtube.com/watch?v=yyVISFFViQQ
2018-12-07 06:22:33
It's much easier than it looks like, just consider the parity of the permutation.
2016-03-09 21:02:51
A* Algorithm
2011-06-04 12:44:32 Shagun Akarsh
Give some hint on approach....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.