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

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