//------------------------------------------------------------------- // enigma1356.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Magic Spot" by Susan Denham, New Scientist, 3 September 2005, page 50. // // Eight dominoes -- including 6-6 and 3-1 -- are chosen from a // "standard set" and and arranged in a 4-by-4 grid: // // +--+--+--+--+ // | | | | | // +--+--+--+--+ // | | | | | // +--+--+--+--+ // | | | | | // +--+--+--+--+ // | | | | | // +--+--+--+--+ // // Each of the four cells in the interior of the grid have the same // number of spots. Also, the 4-by-4 grid is "magic" in the sense that // the cells sum equally in horizontals, verticals, diagonals, and also // the four outer corners. // // Find the six other dominoes. // // By "standard set" I assume is meant all the combinations of blank // through 6 paired with blank through 6. // (See http://en.wikipedia.org/wiki/Dominoes) // There are 28 (7+6+5+4+3+2+1) dominoes in this standard set. // // This problem potentially entails very many combinations and // permutations. We need to pick 6 dominoes out of 26, and that can // be done 26! / (6! * (26 - 6)!) different ways. // // There are several ways of arranging the 8 dominoes in a 4X4 grid, // and for each configuration, the 8 dominoes can be arranged in 8! // different ways. // // Each of the dominoes can be flipped 180 degrees, so each possibility // is multiplied by 2**8 or 256 different combinations of flipping. // // It's essential to trim this problem down to size. At first I thought // that the dominoes with blanks were implicitly excluded. However, it // turned out that they're required. // // The four inner cells in the grid are all equal. Let's call that // value A: // // +--+--+--+--+ // | | | | | // +--+--+--+--+ // | |A |A | | // +--+--+--+--+ // | |A |A | | // +--+--+--+--+ // | | | | | // +--+--+--+--+ // // Because the "magic total" is equal to both the sum of // the 4 corners and the sum of each diagonal, it is easy to show // that the magic total is 4A, and the grand total of all the // numbers in the grid is 16A. // // Let's see why the dominoes with 0 spots must be included. We'll // first assume they're excluded: // // Because the 3-1 domino is part of a row or column, the maximum // sum of that row or column is 3 + 1 + 6 + 6 or 16. Because the // 6-6 is part of a row or column, the minimum sum of that row or // column is 6 + 6 + 1 + 1 = 14. It is clear that the magic total // is 16 and A equals 4. // // However, the 3-1 domino must occupy one of the outer rows or // columns. The cell opposite the 1 (call it x) must be such that // 1 plus x plus two cells in the center (4 and 4) equals 16. // Not possible. // // So, let's include the dominoes with 0 spots. Because 3-1 is part // of a row or column, the maximum sum is still 16. However, the // 6-6 can be part of a row or column that includes 0-0, so the sum // can be as low as 12. // // Thus, A equals 3 and 4A equals 12. // // There are 12 outer cells. The 6-6 domino must occupy an outer row // or column. Opposite the two 6's must be two 0's. Also, the row // or column with the two 6's must include two 0's to sum to 12. // Opposite those two 0's must be two other 6's. // // We already know that the center four cells are 3, and the 12 outer // cells include four 6's and four 0's. // // The 1 half of the 3-1 domino must occupy an outer row or column. // Opposite it must be a 5. The two remaining cells must also be 1 and 5. // // So, we need dominoes where we have four 0's, two 1's, four 3's, // two 5's, and four 6's. That excludes a few dominoes (anything with a // 2 or 4), but I look at all dominoes anyway. (It takes awhile.) //------------------------------------------------------------------------ #include // A few definitions to clarify things. typedef int BOOL; #define TRUE 1; #define FALSE 0; // Like a 45 RPM record, a domino has an A side and B side. typedef struct { int A, B; } DOMINO; // This is a coordinate in the 4-by-4 gird (X, Y range from 0 to 3). typedef struct { int X, Y; } COORDINATE; // This recursive function generates all combinations from an array 'arr' containing // 'num' items indicated by 0 and 1. When calling the function, 'nest' must equal 0. // Suppose you want to get all ways of picking 3 items from a population of 10. // The array 'arr' has 10 elements initialized 1 1 1 0 0 0 0 0 0 0 and 'num' equals 10. // After the first call to NextCombination, 'arr' is 1 1 0 1 0 0 0 0 0 0. // And so forth. BOOL NextCombination(int arr[], int num, int nest) { int i = num - nest - 1; if (arr[i] == 0) { while (i >= 0 && arr[i] == 0) i--; if (i < 0) return FALSE; arr[i] = 0; arr[i + 1] = 1; return TRUE; } else { arr[i] = 0; if (NextCombination(arr, num, nest + 1)) { while (arr[i] == 0) i--; arr[i + 1] = 1; return TRUE; } } return FALSE; } void Swap(int arr[], int i1, int i2) { int temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } // The 'arr' argument is initially 'num' increasing integers representing // array indices. // When the array is uniformly decreasing, the function returns FALSE. BOOL NextPermutation(int arr[], int num) { int i, j, k; // This simple case happens in half the calls. if (arr[num - 1] > arr[num - 2]) { Swap(arr, num - 1, num - 2); return TRUE; } i = num - 2; while (i >= 0 && arr[i] > arr[i + 1]) i--; if (i < 0) return FALSE; // arr[i] is lower than anything to the right of it. // We now need to find the lowest number to the right // of arr[i]. for (j = k = i + 1; j < num; j++) if (arr[j] > arr[i] && arr[j] < arr[k]) k = j; Swap(arr, i, k); i++; // The remainder are sorted to be ascending. for ( ; i < num - 1; i++) for (j = i + 1; j < num; j++) if (arr[i] > arr[j]) Swap(arr, i, j); return TRUE; } int main(void) { // There are 7 different configurations of 8 dominoes in a 4-by-4 grid. // (Some configurations are not present because they wouldn't result in // the same number being in all four internal squares.) // There are 8 dominoes in each configuration. // Each domino occupies 2 coordinates in the grid. COORDINATE configs[7][8][2] = { 0,0, 0,1, 1,0, 2,0, 3,0, 3,1, 1,1, 2,1, 0,2, 0,3, 1,2, 1,3, 2,2, 2,3, 3,2, 3,3, 0,0, 0,1, 1,0, 2,0, 3,0, 3,1, 1,1, 2,1, 0,2, 1,2, 2,2, 3,2, 0,3, 1,3, 2,3, 3,3, 0,0, 0,1, 1,0, 2,0, 3,0, 3,1, 1,1, 2,1, 0,2, 0,3, 1,2, 1,3, 2,2, 3,2, 2,3, 3,3, 0,0, 0,1, 1,0, 1,1, 2,0, 2,1, 3,0, 3,1, 0,2, 0,3, 1,2, 1,3, 2,2, 2,3, 3,2, 3,3, 0,0, 0,1, 1,0, 1,1, 2,0, 2,1, 3,0, 3,1, 0,2, 1,2, 2,2, 3,2, 0,3, 1,3, 2,3, 3,3, 0,0, 0,1, 1,0, 1,1, 2,0, 2,1, 3,0, 3,1, 0,2, 0,3, 1,2, 1,3, 2,2, 3,2, 2,3, 3,3, 0,0, 1,0, 2,0, 2,1, 3,0, 3,1, 0,1, 2,1, 0,2, 0,3, 1,2, 1,3, 2,2, 3,2, 2,3, 3,3 }; // This is the array of dominoes in the standard set except for two. // It's initialized below. DOMINO set[26]; // This is the array of the 8 chosen dominoes. The first two elements // are given in the statement of the problem. DOMINO chosen[8] = { 6, 6, 3, 1 }; // Here's our 4-by-4 grid in which the dominoes are placed. int grid[4][4]; // This array is passed to the NextPermutation function and is used // to index chosen. int index[8]; // This array is passed to the NextCombination function and is used // to pick 6 dominoes out of 'set'; int used[26] = { 1, 1, 1, 1, 1, 1 }; int A, B, i, j; // Fill up 'set' array with all dominoes in the standard set except 6-6 and 3-1. i = 0; for (B = 0; B <= 6; B++) for (A = B; A <= 6; A++) { if (((A == 3) && (B == 1)) || ((A == 6) && (B == 6))) continue; set[i].A = A; set[i].B = B; i++; } do // NextCombination { int totalsum = 0; int sums[7] = {0, 0, 0, 0, 0, 0, 0}; // Fill up the 'chosen' array with 6 dominoes from 'set' based on bits set in 'used'. for (i = 0, j = 2; i < 26; i++) if (used[i]) chosen[j++] = set[i]; // Find the sum of each domino number and the total sum. for (i = 0; i < 8; i++) { sums[chosen[i].A]++; sums[chosen[i].B]++; totalsum += chosen[i].A + chosen[i].B; } if (totalsum != 48) continue; // Here's the code that eliminates many possibilities based // on the analysis of how many numbers must be present. if (sums[0] != 4 || sums[1] != 2 || sums[2] != 0 || sums[3] != 4 || sums[4] != 0 || sums[5] != 2 || sums[6] != 4) continue; // Initialize the array used with the NextPermutation function. for (i = 0; i < 8; i++) index[i] = i; do // NextPermuation { int config; // Loop through the 7 configurations. for (config = 0; config < 7; config++) { int flip; // Loop through all the possiblities of flipping the 8 dominoes // 180 degrees in the configuration. for (flip = 0; flip < 256; flip++) { int domino, sum; // Put the dominoes in the 'grid' array for (domino = 0; domino < 8; domino++) { int bit; COORDINATE coord[2]; for (i = 0; i < 2; i++) coord[i] = configs[config][domino][i]; bit = (flip >> domino) & 1; grid[coord[ bit].X][coord[ bit].Y] = chosen[index[domino]].A; grid[coord[1-bit].X][coord[1-bit].Y] = chosen[index[domino]].B; } // Test that the middle cells are equal. if (grid[1][1] != grid[2][1] || grid[1][1] != grid[1][2] || grid[1][1] != grid[2][2]) continue; // Test the "magic" qualities of 'grid'. // Four corners sum = grid[0][0] + grid[0][3] + grid[3][0] + grid[3][3]; // Diagonals. if (sum != grid[0][0] + grid[1][1] + grid[2][2] + grid[3][3]) continue; if (sum != grid[3][0] + grid[2][1] + grid[1][2] + grid[0][3]) continue; for (i = 0; i < 4; i++) { // Horizontals if (sum != grid[0][i] + grid[1][i] + grid[2][i] + grid[3][i]) break; // Verticals if (sum != grid[i][0] + grid[i][1] + grid[i][2] + grid[i][3]) break; } if (i < 4) continue; // We have a winner! printf("config = %i flip = %i\n", config, flip); printf("Grid: "); for (i = 0; i < 16; i++) printf("%i", grid[0][i]); printf("\n"); printf("Six other dominoes: "); for (i = 2; i < 8; i++) printf("%i-%i ", chosen[i].A, chosen[i].B); printf("\n"); // Go on to another configuration break; } } } while (NextPermutation(index, 8)); } while (NextCombination(used, 26, 0)); return 0; }