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

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