//---------------------------------------------------------------------------
// 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 <stdio.h>

// 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;
}