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