//----------------------------------------------------------------------------
// Written by Michael Main (main@colorado.edu)
// Version: Oct 17, 2005
// The purpose of this program is to demonstrate the use of:
// -- two-dimensional arrays
// -- random numbers
// -- the set class
// The program tries to fill a grid of characters so that each row,
// each column, and each diagonal contains the letters of the word
// ENIGMA.  The technique is an inefficient random search.
// The program is written so that it can be easily modified to solve
// other similar problems.
#include <iostream>    // Provides cin, cout, endl
#include <set>         // Provides the set<char> class
#include <string>      // Provides the string class
using namespace std;
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
const int MAX_GRID_SIZE = 9;
enum check_type {ROW, COLUMN, MAJOR_DIAGONAL, MINOR_DIAGONAL};
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
void initialize_grid(
    unsigned int& using_size,
    string& letters_to_use,
    char grid[ ][MAX_GRID_SIZE],
    bool is_fixed_location[ ][MAX_GRID_SIZE]
    );

bool is_wrong(
    unsigned int using_size,
    char grid[MAX_GRID_SIZE][MAX_GRID_SIZE],
    check_type what,
    int which
    );

void make_random_change(
    unsigned int using_size,
    string letters_to_use,
    char grid[ ][MAX_GRID_SIZE],
    bool is_fixed_location[ ][MAX_GRID_SIZE]
    );

void print(unsigned int using_size, char grid[ ][MAX_GRID_SIZE]);

bool solution(
    unsigned int using_size,
    char grid[ ][MAX_GRID_SIZE]
    );
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
int main( )
{
    char grid[MAX_GRID_SIZE][MAX_GRID_SIZE];
    bool is_fixed_location[MAX_GRID_SIZE][MAX_GRID_SIZE];
    unsigned int using_size;
    string letters_to_use;
    int counter = 0;
    
    initialize_grid(using_size, letters_to_use, grid, is_fixed_location);
    cout << "Here is the initial grid:\n";
    print(using_size, grid);

    while (!solution(using_size, grid))
    {
	make_random_change(using_size, letters_to_use, grid, is_fixed_location);
	if (++counter % 1000 == 0)
	    cout << counter << endl;
    }

    cout << "\nSuccess!\n";
    print(using_size, grid);
    return 0;
}
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
void initialize_grid(
    unsigned int& using_size,
    string& letters_to_use,
    char grid[ ][MAX_GRID_SIZE],
    bool is_fixed_location[ ][MAX_GRID_SIZE]
    )
{
    unsigned int row, col;
    
    using_size = 6;
    letters_to_use = "ENIGMA";
    for (row = 0; row < using_size; ++row)
    {
	for (col = 0; col < using_size; ++col)
	{
	    is_fixed_location[row][col] = false;
	    grid[row][col] = '.';
	}
    }
    grid[3][0] = 'A';  is_fixed_location[3][0] = true;
    grid[4][0] = 'N';  is_fixed_location[4][0] = true;
    grid[5][0] = 'E';  is_fixed_location[5][0] = true;
    grid[5][1] = 'N';  is_fixed_location[5][1] = true;
    grid[5][2] = 'I';  is_fixed_location[5][2] = true;
    grid[5][3] = 'G';  is_fixed_location[5][3] = true;
    grid[5][4] = 'M';  is_fixed_location[5][4] = true;
    grid[5][5] = 'A';  is_fixed_location[5][5] = true;
    grid[2][5] = 'G';  is_fixed_location[2][5] = true;
    grid[3][5] = 'E';  is_fixed_location[3][5] = true;
    grid[4][5] = 'M';  is_fixed_location[4][5] = true;
}
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
bool is_wrong(
    unsigned int using_size,
    char grid[MAX_GRID_SIZE][MAX_GRID_SIZE],
    check_type what,
    int which
    )
{
    unsigned int i; // Loop control variable
    set<char> found;
    
    switch(what)
    {
    case ROW:
	for (i = 0; i < using_size; ++i)
	    found.insert(grid[which][i]);
	break;
	
    case COLUMN:
	for (i = 0; i < using_size; ++i)
	    found.insert(grid[which][i]);
	break;

    case MAJOR_DIAGONAL:
	for (i = 0; i < using_size; ++i)
	    found.insert(grid[i][i]);
	break;
	
    case MINOR_DIAGONAL:
	for (i = 0; i < using_size; ++i)
	    found.insert(grid[i][using_size - i - 1]);
	break;
    }
    return (found.size( ) == using_size && !found.count('.'));
}
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
void make_random_change(
    unsigned int using_size,
    string letters_to_use,
    char grid[ ][MAX_GRID_SIZE],
    bool is_fixed_location[ ][MAX_GRID_SIZE]
    )
{
    int row, col;
    
    do
    {
	row = rand( ) % using_size;
	col = rand( ) % using_size;
    }   while (is_fixed_location[row][col]);
    grid[row][col] = letters_to_use[rand( ) % using_size];
}
//----------------------------------------------------------------------------


//----------------------------------------------------------------------------
void print(unsigned int using_size, char grid[ ][MAX_GRID_SIZE])
{
    unsigned int row, col;
    char letter;
    
    for(row = 0; row < using_size; ++row)
    {
	for(col = 0; col < using_size; ++col)
	{
	    cout << letter << ' ';
	}
	cout << endl;
    }
}
//----------------------------------------------------------------------------

bool solution(
    unsigned int using_size,
    char grid[ ][MAX_GRID_SIZE]
    )
{
    unsigned int i;
    
    // Check that each row has all the letters:
    for (i = 0; i < using_size; ++i)
    {   // Check row number i:
	if (is_wrong(using_size, grid, ROW, i))
	    return false;
    }
    
    // Check that each column has all the letters:
    for (i = 0; i < using_size; ++i)
    {   // Check column number i:
	if (is_wrong(using_size, grid, COLUMN, i))
	    return false;
    }

    // Check that each diagonal has all the letters:
    if (is_wrong(using_size, grid, MAJOR_DIAGONAL, 0))
    	return false;
    if (is_wrong(using_size, grid, MINOR_DIAGONAL, 0))
   	return false;

    return true;
}