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