Dice Puzzle
Time limit1sMemory limit128 MB
Given partial top and front faces of a 3x3x3 cube of standard dice with fixed chirality and opposite-face contact constraints, enumerate all valid orientations and report every possible sum of the right-side faces.
- Level
Medium7 of 10
- Topics
- Backtracking, Simulation, Combinatorics, Brute force
- Solved
- No attempts yet
Problem
You are given the following dice puzzle.
- Every die is an ordinary six-sided die whose opposite faces always sum to (so is opposite , is opposite , and is opposite ). Every die has the same right-handed orientation: when the face showing is on top and the face showing is at the front, the face showing is on the right.
- Twenty-seven such dice are packed together to form a cube.
- Wherever two dice touch, the two faces pressed against each other must sum to . For example, if one face of a touching pair shows , the face it is pressed against shows .
- Some of the die faces that appear on the top and on the front of the cube are given; every other face is unknown.
- A plausible arrangement is any way of placing and orienting the dice that obeys all of the rules above and matches every given top and front face.
For each plausible arrangement, look at the right side of the cube and add the nine numbers that appear there. Your task is to report every possible value of this right-side sum.
Input
The first line contains an integer , the number of datasets. The datasets follow.
Each dataset consists of six lines. The first three lines describe the top view of the cube as a grid
T11 T12 T13
T21 T22 T23
T31 T32 T33
and the next three lines describe the front view as a grid in the same layout
F11 F12 F13
F21 F22 F23
F31 F32 F33
Each and is either the number on that face (an integer from to ) or , which means the face is unknown. The values in a line are separated by spaces.
Number the columns of both grids to from left to right. The cube splits into three vertical layers, one per column, and the -th column of the top view and the -th column of the front view describe the same layer. Such a layer holds nine dice, indexed by depth (front to back) and by height (bottom to top). The three entries of that top-view column list the layer's top faces, one per depth; the three entries of that front-view column list the layer's front faces, one per height. Consequently the die at a given depth and height in the layer shows the top face of that depth and the front face of that height.
Output
For each dataset, consider every plausible arrangement and compute, for each of them, the sum of the nine faces on the right side of the cube (numbered like the other views), that is .
Print one line per dataset containing all the distinct right-side sums in ascending order, separated by a single space. If the dataset has no plausible arrangement, print a single . The output is compared exactly, so do not print any trailing spaces at the end of a line.