//--------------------------------------------------------------------------- // enigma1355.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Cube Words" by Keith Austin, from New Scientist, 27 August 2005, page 46 // // Nine cubes are assigned letters from 'a' to 'f'. // They are arranged in a larger 3 x 3 x 3 cube, and all 27 three-letter // "words" are read off, from top to bottom, west to east, and north to south. // These 27 words are shown in the 'words' array below. // What are the 3 words going through the center of the large cube? // // This one scared me. I knew that methodically putting the words into a // cube pattern and then checking for consistency entailed 27! combinations, // and that was way too many. Methodically putting the letters into the // cube pattern was also problematic, involving 5 ** 27 combinations. // // It seemed reasonable to build up the cube letter-by-letter and checking // for contradictions every step of the way. // // After several false starts, I decided that a recursive function might be // appropriate here. We can view the 27 letters of the cube in a single // chain. Each nested call to the function calculates a new letter in the // chain. The function returns TRUE to indicate success and FALSE for failure. // Thus, it would be possible to pursue a particular path through the chain // but back up if it didn't pan out. //---------------------------------------------------------------------------- #include // Let's make some code a little clearer. typedef int BOOL; #define TRUE 1 #define FALSE 0 // These are the 27 words listed in the problem. char * words[27] = { "acb", "aeb", "afd", "bae", "baf", "bcd", "bce", "bde", "bec", "cbe", "cda", "cef", "cfe", "daf", "dba", "dca", "dea", "dfe", "ebc", "ebd", "edc", "efa", "efb", "efd", "fab", "feb", "fec" }; // This array will be used to determine if a particular 3-letter word // is already taken from the 'words' array or is free. BOOL taken[27]; // And here's the 3 x 3 x 3 cube. The first dimension is the "plane" // from 0 (top) to 2 (bottom). The second dimension is the "row" // from 0 (north) to 2 (south). The third dimension is the "column" // from 0 (west) to 2 (east). char cube[3][3][3]; // This function returns an index in the 'words' array of the word // represented by the three character arguments. // It there is no such word in the array, it returns -1. int GetWordIndex(char ch0, char ch1, char ch2) { int i; for (i = 0; i < 27; i++) if (ch0 == words[i][0] && ch1 == words[i][1] && ch2 == words[i][2]) return i; return -1; } // This function checks if there's an available word in the 'words' // array that begins with the two letters given as arguments. BOOL PossibleNotTakenWord(char ch0, char ch1) { int i; for (i = 0; i < 27; i++) if (!taken[i] && ch0 == words[i][0] && ch1 == words[i][1]) return TRUE; return FALSE; } // This is the primary function of the program. It's called recursively // beginning with an index of 0, indicating a linear index of the 'cube' // array. If the function finds a letter that works, it calls itself // with an argument of index + 1. // The function returns FALSE if it runs out of trial letters. // The function returns TRUE if index is 27 or if a call to itself also // returns TRUE. BOOL FindCubeCell(int index) { // Calculate plane, row, and column indices based on 'index'. int plane = index / 9; int row = index / 3 % 3; int col = index % 3; int i; char ch; // If we've gotten this far, we're really all done. if (index == 27) return TRUE; // Loop through the six possible trial letters for this index. for (ch = 'a'; ch < 'g'; ch++) { // Some variables used later. int takenMaybeUndo[3]; int numTakenMaybeUndo = 0; BOOL ok = TRUE; // Print all the letters we have so far with the trial letter 'ch'. // This slows down the program but it's fun to watch. for (i = 0; i < index; i++) { printf("%c", cube[0][0][i]); if (i % 3 == 2) printf(" "); } printf("%c\n", ch); // This block of code looks like a luxury, but it's essential to making // the program run in a reasonable length of time. // If the trial letter 'ch' is the second letter of a word (indicated // by an plane, row, or column index of 1), check if the first letter // and the trial letter can possibly form a three-letter word. // If it can't, skip that letter. if (plane == 1) { if (!PossibleNotTakenWord(cube[0][row][col], ch)) continue; } if (row == 1) { if (!PossibleNotTakenWord(cube[plane][0][col], ch)) continue; } if (col == 1) { if (!PossibleNotTakenWord(cube[plane][row][0], ch)) continue; } // The stuff that follows constitute the important consistency check. // It needs to be done separately for the three dimensions. // If the 'plane' is 2, we're working on the bottom plane. if (plane == 2) { // See if the new word formed with the trial letter is in the 'words' array. i = GetWordIndex(cube[0][row][col], cube[1][row][col], ch); // If GetWordIndex returns -1, it's not an allowable word. There's also a // problem if the word has already been used. if (i == -1 || taken[i]) { ok = FALSE; } // If the word is OK, set the 'taken' array, but also keep track of all // changes to the 'taken' array. We may have to undo them. else { taken[i] = TRUE; takenMaybeUndo[numTakenMaybeUndo++] = i; } } // Similar code for the last letter of a row. if (ok && (row == 2)) { i = GetWordIndex(cube[plane][0][col], cube[plane][1][col], ch); if (i == -1 || taken[i]) { ok = FALSE; } else { taken[i] = TRUE; takenMaybeUndo[numTakenMaybeUndo++] = i; } } // Similar code for the last letter of a column. if (ok && (col == 2)) { i = GetWordIndex(cube[plane][row][0], cube[plane][row][1], ch); if (i == -1 || taken[i]) { ok = FALSE; } else { taken[i] = TRUE; takenMaybeUndo[numTakenMaybeUndo++] = i; } } // If there's a problem with any of the three dimensions, we have to // undo the 'taken' array. if (!ok) { for (i = 0; i < numTakenMaybeUndo; i++) taken[takenMaybeUndo[i]] = FALSE; } // Otherwise, we can set the 'cube' array and try the next letter // by calling this function for the next index. // If that call returns TRUE, return TRUE likewise. else { cube[plane][row][col] = ch; if (FindCubeCell(index + 1)) return TRUE; // Uh, oh. Something didn't work further on in the chain. else { // Undo the 'taken' array. for (i = 0; i < numTakenMaybeUndo; i++) taken[takenMaybeUndo[i]] = FALSE; // And also undo the 'cube' array. cube[plane][row][col] = '\0'; } } } // If none of the possible letters work, we're on the wrong path. return FALSE; } // Entry point of the program. int main(void) { // Kick off the process. FindCubeCell(0); // Gosh, we're so confident that this worked that we're not even // checking if FindCubeCell return TRUE. // Print the three words that go through the center. printf("\n%c%c%c %c%c%c %c%c%c\n", cube[0][1][1], cube[1][1][1], cube[2][1][1], cube[1][0][1], cube[1][1][1], cube[1][2][1], cube[1][1][0], cube[1][1][1], cube[1][1][2]); return 0; }