Under construction

Still being built. Things may change

Commedia dell'arte

Time limit1sMemory limit128 MB

Summary
Determine whether a 3D M^3 sliding puzzle can be restored to its solved state given its parity/permutation solvability rules.
Level

Medium6 of 10

Topics
Math, Combinatorics, Implementation
Solved
No attempts yet

Problem

Commedia dell'arte is a theater genre that first appeared in Italy at the start of the 16th century, inspired by Roman theater. The plays had no fixed script, so the actors (also called performers) had to improvise constantly — the author gave only loose directions such as "enter the stage and do something funny" or "everyone comes on stage and everything ends happily."

A theater company wants to stage a brand-new play. Its hero owns a puzzle that plays a central role and opens up many chances to improvise. The puzzle is the world-famous Fifteen Puzzle, but to make the play more interesting the company replaces the standard puzzle with a three-dimensional version.

The 3D puzzle is a cube of M3M^3 slots. Every slot but one holds a cubic tile; exactly one position is free. The tiles are numbered from 11 to M3−1M^3 - 1. The goal is to restore the original ordering after the tiles have been randomly reshuffled. The only allowed move is to slide a tile that is adjacent to the free position into that free position, along one of the three principal axes.

In the original (goal) configuration, the slot at coordinates (x,y,z)(x, y, z) with x,y,z∈{0,…,M−1}x, y, z \in \{0, \dots, M-1\} holds tile number z⋅M2+y⋅M+x+1z \cdot M^2 + y \cdot M + x + 1, and the slot (M−1,M−1,M−1)(M-1, M-1, M-1) is free.

Write a program that decides whether the puzzle can be solved.

Input

The input consists of NN cases. The first line contains a single positive integer NN. The cases follow.

The first line of each case contains one integer MM (1≤M≤1001 \le M \le 100), the side length of the cube. Then follow MM lines, each containing exactly M2M^2 numbers that describe one layer: the first line is the top layer of the cube and the last line is the bottom layer. Within a layer the numbers are listed row by row, from the top-left corner to the bottom-right corner. Equivalently, the slot at coordinates (x,y,z)(x, y, z) is the (x+M⋅y+1)(x + M \cdot y + 1)-th number on the (z+1)(z + 1)-th line. Numbers are separated by spaces, and 00 marks the free position.

Output

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

Examples4

  1. Example 1

    Input
    2
2
1 2 3 4
5 7 6 0
2
2 1 3 5
4 6 0 7
    Expected output
    Puzzle is unsolvable.
Puzzle can be solved.

  2. Example 2

    Input
    1
1
0
    Expected output
    Puzzle can be solved.

  3. Example 3

    Input
    1
2
1 2 3 4
5 6 7 0
    Expected output
    Puzzle can be solved.

  4. Example 4

    Input
    1
3
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
    Expected output
    Puzzle can be solved.