//#=====================================================================================
//#
//#       Filename:  sudoku_gen.cpp
//#
//#    Description:  sodoku puzzle generator/solver
//#  Usage:
//#     With no options it generates a puzzle (with all entries filled in)
//#     To solve a puzzle use the -f option and pass in a file.
//#         -v              verbose
//#         -f <filename>    Unsolved state, space-separated, one line per row,
//#                          with empty cells marked with 0
//#  
//#
//#        Version:  1.0
//#        Created:  12/02/2005
//#       Revision:  none
//#       Compiler:  GNU C/C++
//#
//#         Author: J. van Donsel
//#        Company:  
//#          Email:  jim at jimandbarb.net
//#
//#         This software is freely available to use as you wish. No rights reserved.
//#
//#=====================================================================================

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include <unistd.h>
#include <sys/time.h>
#include <math.h>
#include <ctype.h>

#define PUZZLE_SIZE 9


int g_MiniSize = 0;
int g_Init[PUZZLE_SIZE][PUZZLE_SIZE];

// Options
bool g_bVerbose = false;
bool g_bInit    = false;


//----------------------------------------------------------------------
//  class cCell
//----------------------------------------------------------------------
class cCell
{
    public:
        cCell(){m_Count = 0; memset(&m_P, 0, sizeof(m_P));};

    inline int GetCount() { return m_Count;}
    void RemovePossible(int value);
    void SetValue(int value);
    void SetAllValues();
    int  GetFirstPossible();
    void Dump(bool bSpaces);

    bool m_P[PUZZLE_SIZE+1];  // 1-based, true indicates this value is possible
    int m_Count; 
};

//----------------------------------------------------------------------
//  RemovePossible
//
//  Removes the given value from the list of possible values 
//----------------------------------------------------------------------
void cCell::RemovePossible(int value)
{
    if (m_P[value])
    {
        if (--m_Count < 0 ) m_Count = 0;
    }
    m_P[value] = false;
        
} // endRemovePossible 

//----------------------------------------------------------------------
//  SetAllValues
//
//  Sets all possible values. 
//----------------------------------------------------------------------
void cCell::SetAllValues()
{
    for (int i = 1; i <= PUZZLE_SIZE; ++i)
    {
        m_P[i] = true;
    }

    m_Count = PUZZLE_SIZE;
        
} // end SetAllValues

//----------------------------------------------------------------------
//  SetValue
//
//  Sets the given value. No other values are possible
//----------------------------------------------------------------------
void cCell::SetValue(int value)
{
    // No other values are possible
    for (int i = 1; i <= PUZZLE_SIZE; ++i)
    {
        m_P[i] = false;
    }

    m_P[value] = true;
    
    m_Count = 1;

        
} // end SetValue

//----------------------------------------------------------------------
//  GetFirstPossible
//
//  Gets the first value from the possible list 
//  Returns zero if no values are possible.
//----------------------------------------------------------------------
int cCell::GetFirstPossible()
{
    for (int i = 1; i <= PUZZLE_SIZE; ++i)
    {
        if (m_P[i])
        {
            return i;
        }
    }

    return 0;
} // endRemovePossible 


//----------------------------------------------------------------------
//  Dump
//
//----------------------------------------------------------------------
void cCell::Dump(bool bSpaces)
{
    // No other values are possible
    for (int i = 1; i <= PUZZLE_SIZE; ++i)
    {
        if (m_P[i])
        {
            printf("%2d", i);
        }
        if (bSpaces)
        {
            printf(" ");
        }
    }

        
} // end Dump

//----------------------------------------------------------------------
//  class cTable 
//----------------------------------------------------------------------
class cTable
{
public:
    cTable() { m_RecursionDepth = 0;}
    bool Solve();
    void Dump(bool bSpaces);
    void SetValue(int row, int col, int value);
    inline int  GetCount(int row, int col) {return m_Cells[row][col].GetCount();}
    inline int  GetFirstPossible(int row, int col) { return m_Cells[row][col].GetFirstPossible();}
    void SetAllValues();
    bool Check();

    int m_RecursionDepth;

protected:
    cCell m_Cells[PUZZLE_SIZE][PUZZLE_SIZE];

}; // end class cTable




//----------------------------------------------------------------------
//  Dump
//----------------------------------------------------------------------
void cTable::Dump(bool bSpaces)
{
    for (int row = 0 ; row < PUZZLE_SIZE; ++row)
    {
        for (int col = 0; col < PUZZLE_SIZE; ++col)
        {
            printf("(");
            m_Cells[row][col].Dump(bSpaces);
            printf(") ");

        }// end for col

        printf("\n");
    } // end for row
    printf("\n");

} // end Dump

//----------------------------------------------------------------------
//  SetValue 
//  Sets the given value for this cell and removes the possibility 
//  from all adjacent cells.
//
//----------------------------------------------------------------------
void cTable::SetValue(int row, int col, int value)
{
    m_Cells[row][col].SetValue(value);

    // Remove from column 
    for (int c = 0; c < PUZZLE_SIZE; ++c)
    {
        if (c != col)
        {
            m_Cells[row][c].RemovePossible(value);
        }
    }
    // Remove from row
    for (int r = 0; r < PUZZLE_SIZE; ++r)
    {
        if (r != row)
        {
            m_Cells[r][col].RemovePossible(value);
        }
    }
    // Remove from mini-square 
    int row_start = g_MiniSize*(row/g_MiniSize);
    int col_start = g_MiniSize*(col/g_MiniSize);
    for (int r = row_start; r < row_start + g_MiniSize; ++r)
    {
        for (int c = col_start; c < col_start + g_MiniSize; ++c)
        {
            if (r != row && c != col)
            {
                m_Cells[r][c].RemovePossible(value);
                
            }
        }
    }
    

} // end SetValue


//----------------------------------------------------------------------
//  Check
//  Checks the given stat for validity.
//  Returns true if value, false if not
//
//----------------------------------------------------------------------
bool cTable::Check()
{
    for (int row = 0; row < PUZZLE_SIZE; ++row)
    {
        for (int col = 0; col < PUZZLE_SIZE; ++col)
        {
            int count = m_Cells[row][col].GetCount();
            if (count == 0)
            {
                return false;
            }
            if (count == 1)
            {
                // Force this cell to its current value, which 
                // cleans out neighboring cells
                SetValue(row, col, m_Cells[row][col].GetFirstPossible());
            }
        }
    }
    
    return true;
    
} // end Check




//----------------------------------------------------------------------
//  SetAllValues
//----------------------------------------------------------------------
void cTable::SetAllValues(void)
{
   // indicate that all values are possible
    for (int row = 0; row < PUZZLE_SIZE; ++row)
    {
        for (int col = 0; col < PUZZLE_SIZE; ++col)
        {
            m_Cells[row][col].SetAllValues(); 
        }
    }
} // end SetAllValues

//----------------------------------------------------------------------
//  Solve
//  Returns true if we have a solution.
//----------------------------------------------------------------------
bool cTable::Solve()
{
    // Find the first ambiguous cell, choose its first possibility, 
    // and recurse.
    //
    m_RecursionDepth++;

    if (g_bVerbose)
    {
        //system("clear");
        printf("Solve, depth=%d\n", m_RecursionDepth);
        Dump(true);
    }

    
    for (int row = 0; row < PUZZLE_SIZE; ++row)
    {
        for (int col = 0; col < PUZZLE_SIZE; ++col)
        {
          
            int count = GetCount(row,col);
            if ( count == 0)
            {
                if (g_bVerbose) printf("Row=%d, col=%d has count of zero\n", row,col);
                return false;
            }
            
            if ( count == 1)
            {
                // unambigous. Skip to next cell.
               
                continue;
            }

            // If we got here we have an ambigous cell.
            // Check each possible value

            while (int value = GetFirstPossible(row,col))
            {
                // Make a new working table
                cTable *pNew = new cTable();
                *pNew = *this;
                  
                if (g_bVerbose) printf("Setting row=%d, col=%d to %d\n", row, col, value);
                pNew->SetValue(row, col,value);
                
                if (!pNew->Check())
                {
                    // Not a valid state
                    if (g_bVerbose) printf("Set of row=%d, col=%d to %d caused emptiness, depth=%d\n", row, col,value, m_RecursionDepth);
                    this->m_Cells[row][col].RemovePossible(value);
                    delete pNew;
                    continue;
                }
                
                if (pNew->Solve())
                {
                    // Someone down below found a solution. Trickle back up.
                    if (g_bVerbose) printf("Percolating up, depth=%d\n", m_RecursionDepth);
                    delete pNew;
                    return true;
                }
                else
                {
                    // Someone down below discovered that isn't a solution 
                    if (g_bVerbose) printf("Set of row=%d, col=%d to %d failed at lower level, depth=%d\n", row, col,value, m_RecursionDepth);
                    this->m_Cells[row][col].RemovePossible(value);
                    delete pNew;
                    continue;
                }
            } // end while
            if (g_bVerbose) printf("No more possibilities for row=%d, col=%d, depth=%d\n", row, col, m_RecursionDepth);
            return false;
                   

        } //end for col

    } // end for row

    printf(">>>>> Solution <<<<<<\n");
    Dump(false);

    return true;

} // end Solve

//----------------------------------------------------------------------
// PrintUsage
//----------------------------------------------------------------------
void PrintUsage()
{
    printf("Usage:\n");
    printf("\tWith no options it generates a puzzle\n");
    printf("\tTo solve a puzzle use the -f option\n");
    printf("\n");
    printf("\t-v                verbose\n");
    printf("\t-f <filename>     Unsolved state, space-separated, one line per row\n");
    
} // end PrintUsage

//----------------------------------------------------------------------
//  GetOptions
//----------------------------------------------------------------------
void GetOptions(int argc, char* argv[])
{
    char c;
    while ((c = getopt (argc, argv, "vf:")) != -1)
        switch (c)
        {
        case 'v':
            g_bVerbose = true;
            break;
            
        case 'f':
            if (optarg)
            {
                FILE* fp = fopen(optarg, "r");
                if (!fp)
                {
                    printf("Could not open input file %d\n", optarg);
                    exit(-1);
                }
                int row = 0;
                char line[128];
                while (fgets(line, sizeof(line), fp))
                {
                    int col = 0;
                    char *p = strtok(line, " ");
                    while (p && *p && !isspace(*p))
                    {
                        //printf("Setting [%d][%d] to %d (%c)\n", row, col, atoi(p), *p);
                        if (row >= PUZZLE_SIZE || col >= PUZZLE_SIZE)
                        {
                            printf("Input size wrong!\n");
                            exit(-1);
                        }
                                   
                        g_Init[row][col++] = atoi(p);
                        p = strtok(NULL, " ");
                    }
                    row++;
                }// end while
                g_bInit = true;                                          
                
            }
            break;
        
        case '?':
            PrintUsage();
            exit(1);
            
        default:
            PrintUsage();
            exit(-1);
        }

} // end GetOptions

//----------------------------------------------------------------------
//  main
//----------------------------------------------------------------------
int main ( int argc, char *argv[] )
{
    GetOptions(argc, argv);
    
    g_MiniSize = (int)sqrt(PUZZLE_SIZE);
    if (g_MiniSize * g_MiniSize != PUZZLE_SIZE)
    {
        printf("Error: puzzle size %d must be a perfect square\n", PUZZLE_SIZE);
        exit(-1);
    }
    
    struct timeval startTime;
    struct timezone zone;
    gettimeofday(&startTime, &zone);
    
    // Create a working table.
    cTable* pw = new cTable;

    pw->SetAllValues();

    if (!g_bInit)
    {
        // No initialization specified
        // Start with random values in the top row
        int randomRow[PUZZLE_SIZE] = {0};
        srand(time(NULL));
        for (int col = 0; col < PUZZLE_SIZE; ++col)
        {
            int r;
            while (1)
            {
                r = (rand() % PUZZLE_SIZE) + 1;
                int c;
                for (c = 0; c < PUZZLE_SIZE; ++c)
                {
                    if (randomRow[c] == r)
                    {
                        // dup
                        break;
                    }
                }
                
                if (c == PUZZLE_SIZE) break;
            } // end while
            randomRow[col] = r;
        }
        
        for (int col = 0; col < PUZZLE_SIZE; ++col)
        {
            pw->SetValue(0, col, randomRow[col]);
        }
    }
    else
    {
        // We had an initialization specified
        for (int row = 0; row < PUZZLE_SIZE; ++row)
        {
            for (int col = 0; col < PUZZLE_SIZE; ++col)
            {
                if (g_Init[row][col])
                     pw->SetValue(row, col, g_Init[row][col]);
            }
        }
    }
    
    
    // Solve the puzzle 
    int r = pw->Solve();
        
    struct timeval endTime;
    gettimeofday(&endTime, &zone);
    
    unsigned start_msec = startTime.tv_usec /1000;
    unsigned end_msec = endTime.tv_usec / 1000;
    unsigned delta_msec;
    if (endTime.tv_sec > startTime.tv_sec)
    {
        end_msec += 1000 * (endTime.tv_sec - startTime.tv_sec);
    }
  
    delta_msec = end_msec - start_msec;
        
    if (delta_msec > 1000)
    {
        printf("Elapsed time = %f seconds\n", delta_msec/1000.0);
    }
    else
    {
        printf("Elapsed time = %d ms\n", delta_msec);
    }
        

	return 0;

}// ----------  end of function main  ----------