//---------------------------------------------------------------------
// enigma1360.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "An Enigma Gem" by Bob Walker, New Scientist, 1 October 2005, page 48
//
// This is a sudoku-like puzzle with letters rather than numbers.
// We start with this 6-by-6 grid:
//
//	+---+---+---+---+---+---+
//	|   |   |   |   |   |   |
//	+---+---+---+---+---+---+
//	|   |   |   |   |   |   |
//	+---+---+---+---+---+---+
//	|   |   |   |   |   | G |
//	+---+---+---+---+---+---+
//	| A |   |   |   |   | E |
//	+---+---+---+---+---+---+
//	| N |   |   |   |   | M |
//	+---+---+---+---+---+---+
//	| E | N | I | G | M | A |
//	+---+---+---+---+---+---+
//
// Each row, column, and diagonal must contain the letters in "ENIGMA".
// What is the second row?
//
// I must confess that this puzzle didn't interest me very much, 
// and I couldn't see an obvious logical path to a solution.
//
// I decided to use a recursive function to generate each letter, and 
// to back up through the nested calls when a contradiction popped up.
//
// I originally had the program print out each letter as it considered it,
// and then backspace if the letter was rejected, but the program worked
// so fast I didn't see any real action.
//
// I suspect that "Joe's" parents are named Ian and Meg.
//----------------------------------------------------------------------

#include <stdio.h>

// Forward declaration of recursive function.

int NextLetter(int grid[][6], int iCell);

// Entry point.

int main(void)
{
	// I'll be using numbers 0 to 5 rather than letters. 
	// The numbers map to letters based on this string.
	// This string is used solely for printing the solution.

	char * enigma = "ENIGMA";

	// This is the grid, but from the bottom up for efficiency.
	// The first (i.e., bottom) row is filled, and some in the
	// outer columns.
	// A 0 means E, 1 means N, 2 means I, etc. 
	// Cells that haven't been filled in yet are also 0, but
	// program logic doesn't need to differentiate those.

	int grid[6][6] = { 0, 1, 2, 3, 4, 5,
	                   1, 0, 0, 0, 0, 4, 
	                   5, 0, 0, 0, 0, 0,
	                   0, 0, 0, 0, 0, 3,
	                   0, 0, 0, 0, 0, 0,
	                   0, 0, 0, 0, 0, 0 };

	int iRow, iCol;

	// The recursive function should return 1 if everything works.

	if (NextLetter(grid, 0))
	{
		// Display the grid rightside up.
		
		for (iRow = 5; iRow >= 0; iRow--)
		{
			for (iCol = 0; iCol < 6; iCol++)
				printf("%c ", enigma[grid[iRow][iCol]]);
		
			printf("\n");
		}
	}
	return 0;
}

int NextLetter(int grid[][6], int iCell)
{
	// These are the cells that are fixed by the initial conditions.

	static int fixed[6][6] = { 1, 1, 1, 1, 1, 1,
	                           1, 0, 0, 0, 0, 1,
	                           1, 0, 0, 0, 0, 1,
	                           0, 0, 0, 0, 0, 1,
	                           0, 0, 0, 0, 0, 0,
	                           0, 0, 0, 0, 0, 0 };

	// These arrays are used to keep track of the numbers that have
	// been used in each of the 6 rows, 6 columns, and 2 diagonals.
	//
	// For example, row[3][2] refers to the fourth row and the third
	// letter, which is I. row[3][2] is 1 if I is already present 
	// in the fourth row.

	static int row[6][6] = { 1, 1, 1, 1, 1, 1,
	                         0, 1, 0, 0, 1, 0,
	                         1, 0, 0, 0, 0, 1,
	                         0, 0, 0, 1, 0, 0,
	                         0, 0, 0, 0, 0, 0,
	                         0, 0, 0, 0, 0, 0 };

	static int col[6][6] = { 1, 1, 0, 0, 0, 1,
	                         0, 1, 0, 0, 0, 0,
	   	                 0, 0, 1, 0, 0, 0,
	                         0, 0, 0, 1, 0, 0,
	                         0, 0, 0, 0, 1, 0,
	                         1, 0, 0, 1, 1, 1 };

	static int diag[2][6] = { 1, 0, 0, 0, 0, 0,
	                          0, 0, 0, 0, 0, 1 };

        // Calculate the row and column of this cell

	int iRow = iCell / 6;
	int iCol = iCell % 6;
	int letter;

	// If all the cells are filled, we're done, return 1.

	if (iCell == 36)
		return 1;

	// Check if it's a fixed cell.
	// If so, move to the next cell.

	if (fixed[iRow][iCol])
		return NextLetter(grid, iCell + 1);

	// Otherwise, loop through the six letters.

	for (letter = 0; letter < 6; letter++)
	{
		// If the letter is already used in the row,
		// we can't use it again.

		if (row[iRow][letter])
			continue;

		// Similarly for the column.

		if (col[iCol][letter])
			continue;

		// Similarly for the diagonals.

		if (iRow == iCol && diag[0][letter])
			continue;

		if (iRow + iCol == 5 && diag[1][letter])
			continue;

		// The letter is available, so put it 
		// in the grid, and set the other arrays

		grid[iRow][iCol] = letter;
		row[iRow][letter] = 1;
		col[iCol][letter] = 1;

		if (iRow == iCol)
			diag[0][letter] = 1;

		if (iRow + iCol == 5)
			diag[1][letter] = 1;

		// Try the next letter.
		// Return 1 if it works, which basically means that the function
		//	has gone all the way to the end and we're done.

		if (NextLetter(grid, iCell + 1))
			return 1;

		// If 0 is returned, there's been a contradiction further up the line.
		// Back up and try the next letter.

		grid[iRow][iCol] = 0;
		row[iRow][letter] = 0;
		col[iCol][letter] = 0;
		
		if (iRow == iCol)
			diag[0][letter] = 0;

		if (iRow + iCol == 5)
			diag[1][letter] = 0;
	}

	// If we're plum out of letters for this cell, return false

	return 0;
}