Original Post
This is just practice but I want to make sure it is cross platform and is over decent code, if you see anything wrong with it or something that should be made better let me know. MainFunctions.h Sudoku.h
#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