#ifndef MISCFUNCTIONS_H
#define MISCFUNCTIONS_H
#include <math.h>
int Power(int x, int y)
{
if( y > 0 )
return x *= Power(x, y-1);
else
return 1;
}
int CharToInt(char c)
{
if( c < '0' || c > '9' )
return -1;
else
return c - '0';
}
int StringToInt(char *str)
{
int number = 0;
int power = strlen(str) - 1;
for(int i = 0; i <= power; i++)
{
number += CharToInt(str) * Power(10, power - i);
}
return number;
}
int IntLen(int num)
{
return static_cast<int>( ceil( log10( static_cast<float>( num ) ) ) );
}
#endif
#ifndef SUDOKU_H
#define SUDOKU_H
#define SUCCESS 1
#define FAILED 0
#include <iostream>
#include <fstream>
#include <math.h>
#include "MiscFunctions.h"
using namespace std;
class Sudoku {
public:
Sudoku();
~Sudoku();
// Methods of sudoku matrix inputs
int ReadFile(const char* filePath);
// Fill in the blanks as much as possible without guessing
int Solve();
// Take 1 step toward solving
void Step();
int **matrix;
bool ***possible;
int size;
private:
// Scans all cells for numbers and marks that number
// in all cells of the same row, column, and 3x3 as not
// possible because it is already used.
int MarkNotPossible();
// Scans all cells and if there is only 1 possiblility
// then simply set that value to the corresponding
// matrix value.
int CheckForSinglePossibility();
};
Sudoku::Sudoku()
{
size = 1;
}
Sudoku::~Sudoku()
{
// Cleanup matrix
for(int i = 0; i < size; i++)
{
delete [] matrix;
}
delete [] matrix;
// Cleanup Possible array
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
delete [] possible[j];
}
delete [] possible;
}
delete [] possible;
}
int Sudoku::ReadFile(const char* filePath)
{
// Flag
bool bSuccess = true;
ifstream file(filePath);
if( file.good() )
{
// Get the size of the sudoku matrix stored in the file
char c;
while( file.get(c) && c != '\n' )
{
if(c == ' ')
size++;
}
// Create the matrix array
matrix = new int*[size];
for(int i = 0; i < size; i++)
{
matrix = new int[size];
}
// Create the possible array
possible = new bool**[size];
for(int i = 0; i < size; i++)
{
possible = new bool*[size];
for(int j = 0; j < size; j++)
{
possible[j] = new bool[size];
for(int k = 0; k < size; k++)
{
possible[j][k] = 1;
}
}
}
//---------------------------------------------------------
// Extract string numbers from the file then convert
// them to int and store them
//
// -maxLength max number of chars each value can use
// -ch holds the current chacter to put in cc
// -cc stores current value as a string
// -ccindex index position of cc
// -pos file cursor position
//---------------------------------------------------------
int maxLength = IntLen(size);
char ch;
char *cc = new char[maxLength];
int ccindex = 0;
int pos = 0;
for(int y = 0; y < size; y++)
{
for(int x = 0; x < size; x++)
{
file.seekg(pos);
while( file.get(ch) && ch != ' ' && ch != '\n' && ccindex < maxLength)
{
cc[ccindex] = ch;
ccindex++;
pos++;
}
pos++;
ccindex = 0;
// Make sure the value is within range and store value
int value = StringToInt(cc);
if( value >= 0 && value <= size )
matrix[x][y] = value;
else
bSuccess = FAILED;
// Reset cc to null
for(int i = 0; i < maxLength; i++)
{
cc = '\0';
}
}
pos++;
}
delete [] cc;
}
else
bSuccess = FAILED;
file.close();
return bSuccess;
}
int Sudoku::Solve()
{
// Loop while one of these are making progress
while( MarkNotPossible() || CheckForSinglePossibility() ) {}
// If any cell is 0 then fail
for(int y = 0; y < size; y++)
{
for(int x = 0; x < size; x++)
{
if( matrix[x][y] == 0)
{
return FAILED;
}
}
}
return SUCCESS;
}
void Sudoku::Step()
{
MarkNotPossible();
CheckForSinglePossibility();
}
int Sudoku::MarkNotPossible()
{
bool bChanged = false;
for(int y = 0; y < size; y++)
{
for(int x = 0; x < size; x++)
{
if( matrix[x][y] > 0)
{
// Mark not possible for ROW (x)
for( int z = 0; z < size; z++ )
{
if( possible[z][y][matrix[x][y]-1] )
{
possible[z][y][matrix[x][y]-1] = false;
bChanged = true;
}
}
// Mark not possible for COLUMN (y)
for( int z = 0; z < size; z++ )
{
if( possible[x][z][matrix[x][y]-1] )
{
possible[x][z][matrix[x][y]-1] = false;
bChanged = true;
}
}
// Mark not possible for minisquare
float miniSize = float( sqrt(size) );
int ymin = int( floor(float(y)/miniSize) * miniSize );
int ymax = int( ceil(float(y)/miniSize) * miniSize );
if(ymax == ymin) ymax = ymin+int(miniSize);
int xmin = int( floor(float(x)/miniSize) * miniSize );
int xmax = int( ceil(float(x)/miniSize) * miniSize );
if(xmax == xmin) xmax = xmin+int(miniSize);
for(int Y = ymin; Y < ymax; Y++)
{
for(int X = xmin; X < xmax; X++)
{
if( possible[X][Y][matrix[x][y]-1] )
{
possible[X][Y][matrix[x][y]-1] = false;
bChanged = true;
}
}
}
}
}
}
return bChanged;
}
int Sudoku::CheckForSinglePossibility()
{
int possibleVal = 0;
int possibilities = 0;
bool bChanged = false;
// Find a cell with only 1 possibility and adjust matrix value
for(int y = 0; y < size; y++)
{
for(int x = 0; x < size; x++)
{
if(matrix[x][y] == 0)
{
for(int z = 0; z < size; z++)
{
if( possible[x][y][z] == true )
{
possibleVal = z;
possibilities++;
}
}
if(possibilities == 1)
{
bChanged = true;
matrix[x][y] = possibleVal + 1;
}
}
possibilities = 0;
}
}
return bChanged;
}
#endif