/** * Solution to Hex Game */ import java.util.*; public class Hex { public static Scanner in = new Scanner(System.in); public static int n; // Number of test cases public static int[][] piece = new int[7][6]; // 7 pieces, each with 6 numbers public static void main(String[] args) { n = in.nextInt(); for (int caseNum = 1; caseNum <= n; caseNum++) { // Read in numbers for each piece for (int p = 0; p < 7; p++) { for (int i = 0; i < 6; i++) { piece[p][i] = in.nextInt(); } } // Rotate each piece so the "1" comes first (this just makes // it easier to place the first piece, which always has "1" on top): for (int i = 0; i < 7; i++) { int j = 0; while (j < 6 && piece[i][j] != 1) j++; // Rotate by doing three reversals: flip(i,0,j-1); flip(i,j,5); flip(i,0,5); // DEBUG: /* System.out.print("Piece " + i +": "); for (int k = 0; k < 6; k++) { System.out.print(piece[i][k] + " "); } System.out.println(); */ } // Now try all possible arrangements in which the middle // piece has a "1" at the top; since there are only 7! = // 5040 possible such arrangements, just do an exhaustive // search. In fact, to really be "dumb" about this, let's // just list all 7^7 ways of choosing seven pieces and // then eliminate duplications with "if" statements: int pos[] = new int[7]; boolean found = false; for (int i0 = 0; i0 < 7; i0++) { pos[0] = i0; for (int i1 = 0; i1 < 7; i1++) { if (i1 == i0) continue; pos[1] = i1; for (int i2 = 0; i2 < 7; i2++) { if (i2 == i0 || i2 == i1) continue; pos[2] = i2; for (int i3 = 0; i3 < 7; i3++) { if (i3 == i0 || i3 == i1 || i3 == i2) continue; pos[3] = i3; for (int i4 = 0; i4 < 7; i4++) { if (i4 == i0 || i4 == i1 || i4 == i2 || i4 == i3) continue; pos[4] = i4; for (int i5 = 0; i5 < 7; i5++) { if (i5 == i0 || i5 == i1 || i5 == i2 || i5 == i3 || i5 == i4) continue; pos[5] = i5; for (int i6 = 0; i6 < 7; i6++) { if (i6 == i0 || i6 == i1 || i6 == i2 || i6 == i3 || i6 == i4 || i6 == i5) continue; pos[6] = i6; if (verify(pos)) { System.out.print("Case " + caseNum + ": "); display(pos); if (found) System.out.println("Duplicate"); found = true; } } } } } } } } if (!found) System.out.println("Case " + caseNum + ": No solution"); } } /** * Reverse the i-th piece between positions 'begin' and 'end' */ public static void flip(int i, int begin, int end) { if (begin == end) return; // Reverse by swapping, working from ends of range into middle of range: for (int j = 0; j < (end-begin+1)/2; j++) { int temp = piece[i][j+begin]; piece[i][j+begin] = piece[i][end-j]; piece[i][end-j] = temp; } } /** * Check whether the current set of piece positions is a solution: */ public static boolean verify(int[] pos) { int rotate[] = {0,0,0,0,0,0,0}; // amt. to rotate each piece // NOTE: rotate[0] is never used // The matches of the outside pieces (1-6) with the center piece (0) // form the "spokes" of a 6-sided wheel: // piece 0,0 -- piece 1,3 // piece 0,1 -- piece 2,4 // piece 0,2 -- piece 3,5 // piece 0,3 -- piece 4,0 // piece 0,4 -- piece 5,1 // piece 0,5 -- piece 6,2 // Rotate pieces 1--6 to make "spokes" match up: for (int p = 1; p <= 6; p++) { int matchPos = (p+2)%6; // position to be matched on outside piece int matchVal = piece[pos[0]][p-1]; // value on center piece // Search the piece in position p for the matchVal; then remember // by how much that piece must be rotated counterclockwise in // order to get the matched value in position: for (int i = 0; i < 6; i++) { if (matchVal == piece[pos[p]][i]) { rotate[p] = (6-matchPos+i)%6; break; } } } /* if (pos[0] == 0 && pos[1] == 1 && pos[2] == 2 && pos[3] == 3 && pos[4] == 4 && pos[5] == 5 && pos[6] == 6) { System.out.println("After aligning spokes:"); System.out.println("Rotations:"); for (int x = 0; x < 7; x++) System.out.print(rotate[x] + " "); System.out.println(); display(pos); } */ // "rim": // piece 1,2 -- piece 2,5 // piece 2,3 -- piece 3,0 // piece 3,4 -- piece 4,1 // piece 4,5 -- piece 5,2 // piece 5,0 -- piece 6,3 // piece 6,1 -- piece 0,4 boolean okay = true; for (int p = 1; p <= 6; p++) { int matchVal = piece[pos[p]][(rotate[p]+p+1)%6]; int q = p+1; if (q == 7) q = 1; if (matchVal != piece[pos[q]][(p+4+rotate[q])%6]) { okay = false; break; } } return okay; } public static void display(int[] pos) { for (int i = 0; i < 7; i++) { System.out.print(pos[i]); if (i < 6) System.out.print(" "); } System.out.println(); } }