//----------------------------------------------------------------------------
// 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 <cassert>
#include <iostream>    // Provides cin, cout, endl
#include <set>         // Provides the set<char> class
#include <stack>       // Provides the stack 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]
    );

// An arrangement is stacktacular if there are no conflicts yet.
bool is_stacktacular(
    unsigned int using_size,
    char grid[MAX_GRID_SIZE][MAX_GRID_SIZE],
    check_type what,
    int which
    );
bool is_stacktacular(
    unsigned int using_size,
    char grid[ ][MAX_GRID_SIZE]
    );

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 make_systematic_change(
    unsigned int using_size,
    string letters_to_use,
    char grid[ ][MAX_GRID_SIZE],
    bool is_fixed_location[ ][MAX_GRID_SIZE],
    stack<unsigned int>& choices
    );

void print(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;
    stack<unsigned int> choices;
    unsigned int row, col;
    
    initialize_grid(using_size, letters_to_use, grid, is_fixed_location);
    cout << "Here is the initial grid:\n";
    print(using_size, grid);

    // The size of the stack tells which choice I am about to make.
    // The element on top of the stack tells me how many things I've tried
    // so far for that choice.
    choices.push(0);
    while (choices.size( ) <= using_size*using_size && choices.size( ) != 0)
    {
	row = (choices.size( ) - 1)/using_size;
	col = (choices.size( ) - 1)%using_size;
	make_systematic_change(using_size, letters_to_use, grid, is_fixed_location, choices);
        if (is_stacktacular(using_size, grid))
	{   // Move forward to the next choice
	    choices.push(0);
	}
	else while (
	    choices.size( ) > 0
	    &&
	    (choices.top( ) == using_size || is_fixed_location[row][col])
	    )
	{   // Backup
	    if (!is_fixed_location[row][col])
		grid[row][col] = '.';
	    choices.pop( );
	    row = (choices.size( ) - 1)/using_size;
	    col = (choices.size( ) - 1)%using_size;
	}
	if (++counter % 100000 == 0)
	{
	    cout << "After " << counter << " iterations:" << endl;
	    print(using_size, grid);
	}
    }

    if (choices.size( ) == 0)
    {
	cout << "\nNo Solution\n";
    }
    else
    {
	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_stacktacular(
    unsigned int using_size,
    char grid[MAX_GRID_SIZE][MAX_GRID_SIZE],
    check_type what,
    int which
    )
{
    unsigned int i; // Loop control variable
    unsigned int many_dots = 0;
    set<char> found;
    
    switch(what)
    {
    case ROW:
	for (i = 0; i < using_size; ++i)
	    if (grid[which][i] == '.')
		++many_dots;
	    else
		found.insert(grid[which][i]);
	break;
	
    case COLUMN:
	for (i = 0; i < using_size; ++i)
	    if (grid[i][which] == '.')
		++many_dots;
	    else
		found.insert(grid[i][which]);
	break;

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


//----------------------------------------------------------------------------
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 make_systematic_change(
    unsigned int using_size,
    string letters_to_use,
    char grid[ ][MAX_GRID_SIZE],
    bool is_fixed_location[ ][MAX_GRID_SIZE],
    stack<unsigned int>& choices
    )
{
    int row = (choices.size( ) - 1)/using_size;
    int col = (choices.size( ) - 1)%using_size;

    if (is_fixed_location[row][col])
    {
	choices.top( ) = 1;
    }
    else
    {
	grid[row][col] = letters_to_use[choices.top( )];
	++choices.top( );
    }
}
//----------------------------------------------------------------------------

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

bool is_stacktacular(
    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_stacktacular(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_stacktacular(using_size, grid, COLUMN, i))
	    return false;
    }

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

    return true;
}