//---------------------------------------------------------------------- // enigma1374.c (c) 2006 by Charles Petzold // // "Dominoes to the Power of Two" by Adrian Somerfield, // New Scientist, 14 January 2006, page 52 // // Standard set of 28 dominoes, layed end to end with matching pips, // starting with 0-0. Total number of pips equal progressively // increasing perfect squares, until 5 left over, 4 of which are doubles. //---------------------------------------------------------------------- #include typedef struct { int A; int B; int flip; } DOMINO; // 28 dominoes in a standard set DOMINO set[28]; // flags for dominoes used in chain int used[28]; // Recursive function int AddAnother(DOMINO chain[], int index, int square) { int i, j; // Display chain up to now for (i = 0; i <= index; i++) printf("%i%i ", chain[i].flip ? chain[i].B : chain[i].A, chain[i].flip ? chain[i].A : chain[i].B); printf("\n"); // If we've reached the potential end of the chain... if (index == 22) { // Count up the unused doubles. int unusedDoubles = 0; for (i = 0; i < 28; i++) if (!used[i] && set[i].A == set[i].B) unusedDoubles++; // If not equal to 4, return 0 return unusedDoubles == 4; } // Loop through the domino set for (i = 1; i < 28; i++) { // Ignore anything that's been used so far if (!used[i]) { int flip, gotOne = 0; // See if the domino can fit at the end of the chain if ((chain[index].flip == 0 && chain[index].B == set[i].A) || (chain[index].flip == 1 && chain[index].A == set[i].A)) { gotOne = 1; flip = 0; } if ((chain[index].flip == 0 && chain[index].B == set[i].B) || (chain[index].flip == 1 && chain[index].A == set[i].B)) { gotOne = 1; flip = 1; } if (gotOne) { // If so, count up the pips int total = 0; // Count up the pips for (j = 0; j <= index; j++) total += chain[j].A + chain[j].B; total += set[i].A + set[i].B; // That total must be less than or equal to the next square if (total <= (square + 1) * (square + 1)) { int newSquare = square; // If it's equal, it's the new square if (total == (square + 1) * (square + 1)) newSquare = square + 1; // Put the domino at the end of the chain chain[index + 1] = set[i]; chain[index + 1].flip = flip; // Set the domino as used used[i] = 1; // Try another domino if (AddAnother(chain, index + 1, newSquare)) return 1; // If that doesn't work, the domino is still available used[i] = 0; } } } } // If we've reached the end of the line, return a failure return 0; } int main(void) { DOMINO chain[23]; int i, A, B; // Initialize the domino set. i = 0; for (A = 0; A <= 6; A++) for (B = A; B <= 6; B++) { used[i] = 0; set[i].flip = 0; set[i].A = A; set[i++].B = B; } // Set the first domino in the chain chain[0] = set[0]; used[0] = 1; // Call recursive function AddAnother(chain, 0, 0); // Print the unused dominos printf("\n\nUnused:\n"); for (i = 0; i < 28; i++) if (!used[i]) printf("%i-%i\n", set[i].A, set[i].B); return 0; }