• Advertisement
Sign in to follow this  

Sudoku Solver Class

This topic is 4023 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
#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

Sudoku.h
#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

Share this post


Link to post
Share on other sites
Advertisement
Alright, a few suggestions. (Mainly because the code formatting got things messed up, and I also don't have time to understand the code completely).

You have a lot of memory allocation and C strings. Why not replace your arrays with a safer vector, and char*'s with std::string?

int CharToInt(char c)

There's a lovely function in C called isdigit that will determine if your character is a numeral. Then you could just cast it to the number. While technically not faster, using premade functions that already exist can help clean up code. Other functions such as StringToInt would also disappear this way too.

I'd also probably break up Sodoku into a header and cpp file. Just for readability sake. And for clarification (due mainly to time limitations on my part), how are you solving the puzzle? Brute force? Algorithm? etc.

Share this post


Link to post
Share on other sites
Quote:
You have a lot of memory allocation and C strings. Why not replace your arrays with a safer vector, and char*'s with std::string?

I will look into vectors and strings, my strings and arrays are really simple so Im not sure if larger things are needed.

Quote:
There's a lovely function in C called isdigit that will determine if your character is a numeral. Then you could just cast it to the number. While technically not faster, using premade functions that already exist can help clean up code. Other functions such as StringToInt would also disappear this way too.

Ill look into cleaning this up, found atoi function that converts an char to an int.

Quote:
I'd also probably break up Sodoku into a header and cpp file. Just for readability sake.

I usually do this but I wanted to release it as a little Sudoku ?library? and thought it would easier to handle and stuff if it were a simple .h

Quote:

And for clarification (due mainly to time limitations on my part), how are you solving the puzzle? Brute force? Algorithm? etc.

There are two functions:
// 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();

They are called in that order until both of them return 0 meaning they made no progress. If they dont make progress, that means it is solved or the solution requires guessing.




Now I have tried to add multi-threading support to speed up the solving but I failed using pthread. I had the thinking I could have one thread run MarkNotPossible() while the other ran CheckForSinglePossibility() until it was solved. Any ideas or maybe a link to some good multi-threading tutorials?

Share this post


Link to post
Share on other sites
I looked into this over a year ago when sudoku first came to my attention and found another C based solver. I can't remember where I found it unfortunately, but it had a nice feature that you could implement.

It created a move tree with the different options available at any time. If a move led to the Sudoku not being solvable it would step back to the last decision point and try the next option. That will lead to a nicer solver.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well to clarify the code for the minisquares you might want to use modulo.

int ymin = y - (y % miniSize);
int ymax = y + (miniSize - (y % miniSize));


ok, is not that much of an improvement; but atleast you stay in the ints... you might wrap that in a function call like

int ymin = get_square_min(y);
int ymax = get_square_max(y);

Following the idea of of readable code.

Your code is ok. You might want to pack the single parts into functions / methods. It all goes to the idea of readabe code; which is worth gold.

Here a litle example
for (int x = 0; x &tl size; x++) {
for (int y = 0; y < size; y++) {
if (is_empty_cell(x,y)) {
mark_horizontal_column(x,y);
mark_vertical_column(x,y);
mark_square(x,y);
}
}
}


You aproach is a deph search aproach wich gets you stuck on some cases. Thought about backtracking? Since what is a solver good for if it gets stuck?

Ok, you might know that backtracking has square complexity; how about solving sodoku with a more generic aproach like simulated anealing. Or an optimized graph search like a*.

Just getting you into some ideas, to show that there are more solutions to solving a problem than the algorithmic one.


I have noticed that you do alot of duplicate work, that is you look at all cells and mark all non possible values. There is a simple solution to combining marking cadidates and filling cells.

1. Scan the field and mark candidats that are not posible. Evey time you mark a cell that drops to on candiate you put it in a list.
2 For all cells in the list of one candidate you set the value and mark the all cells afected, while marking you continue to fill the list with single candidates.

The clue is that you combine the setting of the value of a cell with marking and marking of cells with gathering single values.

If you keep a list of cells with two candidates, once the list for one is depeleted, you store the state on a stack and guess one value. If you do not find a solution, pop the old state of the stack and use the other value. This will keep you going quite far.

Share this post


Link to post
Share on other sites
Quote:
Original post by JY
I looked into this over a year ago when sudoku first came to my attention and found another C based solver. I can't remember where I found it unfortunately, but it had a nice feature that you could implement.

It created a move tree with the different options available at any time. If a move led to the Sudoku not being solvable it would step back to the last decision point and try the next option. That will lead to a nicer solver.


If I understand what you mean, this one actually does that, the multi-dimentional possible array is an array of booleans that mark all possible numbers for each spot, maybe I will make an OpenGL demo of this so you could see what it is doing behind the scenes. :)


Quote:
Original post by Anonymous Poster
Well to clarify the code for the minisquares you might want to use modulo.

int ymin = y - (y % miniSize);
int ymax = y + (miniSize - (y % miniSize));


ok, is not that much of an improvement; but atleast you stay in the ints... you might wrap that in a function call like

int ymin = get_square_min(y);
int ymax = get_square_max(y);

Following the idea of of readable code.

Your code is ok. You might want to pack the single parts into functions / methods. It all goes to the idea of readabe code; which is worth gold.

Here a litle example
for (int x = 0; x &tl size; x++) {
for (int y = 0; y < size; y++) {
if (is_empty_cell(x,y)) {
mark_horizontal_column(x,y);
mark_vertical_column(x,y);
mark_square(x,y);
}
}
}


You aproach is a deph search aproach wich gets you stuck on some cases. Thought about backtracking? Since what is a solver good for if it gets stuck?

Ok, you might know that backtracking has square complexity; how about solving sodoku with a more generic aproach like simulated anealing. Or an optimized graph search like a*.

Just getting you into some ideas, to show that there are more solutions to solving a problem than the algorithmic one.


I have noticed that you do alot of duplicate work, that is you look at all cells and mark all non possible values. There is a simple solution to combining marking cadidates and filling cells.

1. Scan the field and mark candidats that are not posible. Evey time you mark a cell that drops to on candiate you put it in a list.
2 For all cells in the list of one candidate you set the value and mark the all cells afected, while marking you continue to fill the list with single candidates.

The clue is that you combine the setting of the value of a cell with marking and marking of cells with gathering single values.

If you keep a list of cells with two candidates, once the list for one is depeleted, you store the state on a stack and guess one value. If you do not find a solution, pop the old state of the stack and use the other value. This will keep you going quite far.

Great info, I will go over it and see what I can do.

Share this post


Link to post
Share on other sites
Your solution method will not work on all valid boards. There are situations where all the empty cells can have more than one possible value. This doesn't necessarily mean that there is more than one solution (ie an invalid board) because choosing the wrong value to place in a cell will eventually lead to a situation where there are no valid values to place in a cell. In situations like this, taking a guess and then backtracking later if a conflict appears is the usual solution.

The only time you know that a board has no solution is when it inevitably leads to a cell having no possible values. Otherwise there is still a chance to find a solution by filling in an arbitrary value. You only know that a board has more than one solution if you actually find more than one solution (or mathematically prove that somehow, but I don't think we want to get into that).

Share this post


Link to post
Share on other sites
Quote:
Original post by MVP
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
*** Source Snippet Removed ***

Sudoku.h
*** Source Snippet Removed ***


I took a quick glance and one thing I would change, and admittedly this isn't an important change, is that Power(int,int) function to use iteration instead of recursion.


int Power(int x,int y)
{
int ret=1;
for (int i=0;i<y;i++)
ret*=x;
return ret;
}



I just think it's generally better to avoid recursion when possible because it can easily lead to blowing the stack. Although in this case the problem of integer overload will likely crop up before that..

Share this post


Link to post
Share on other sites
Ive made quite a bit of progress, optmized a lot.

In a for loop would you guys use char? I dont really need 4 byte int to do them so I could probably get away with char. I.E. for(char i = 0; i < x; i++) or unsigned char even.

What are your thoughts?

Share this post


Link to post
Share on other sites
Well the solution involves guessing and backtracking, so actually it will solve all possible (valid) boards. The idea is to get a solution that involves no searching for a candidate, since that always involves at least square complexity. The point for the two list, is a to keep a list of possible candidates for for the guessing. The solution will get about 3/4 of all possible sodoku boards. And I have never seen any boards where the guess took more than two candidates. But the heuristic behind the guess is that the best candidate for a guess is the one with the few possible candidates.

P.S. I am actually cheating... We had to solve the problem in a "computational intelligence" course

P.P.S I am the anonymous poster, had not noticed that I was not logged on.

P.P.P.S sorry about that double post...

Share this post


Link to post
Share on other sites
rioki, did you look at the code that was posted? I didn't see any backtracking in there. If I missed it, could someone point out where it is?

Using a char instead of an int is a really low level micro-optimization. You're not really saving any significant amount of memory, and unless you're profiling your code you really have no way of knowing if it makes the code run faster or slower. If it did make the code run faster, it would be by an extremely small amount. As long as you know it won't overflow, it can't hurt I guess. But you're not really gaining much.

Share this post


Link to post
Share on other sites
Quote:
Original post by MVP
It would use less memory.

Really? What about alignment issues? Variables around your loop index may have to be placed on a 32-bit alignment (or something other than 8-bit alignment) anyway, leaving your loop variable with a number of bytes padding wasted memory. Nothing saved.

Besides, I can see you allocate arrays with several levels of pointers and allocations. Way more than all loop variables combined. Saving loop variables is nothing compared to that. Save where it matters, and loop variables is not that place.

[Edited by - Brother Bob on February 2, 2007 6:11:32 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by MVP
It would use less memory.


You should be aware that anything smaller than an int is very likely to be optimized to int.

In the IA-32 architecture, if the data on the stack is not 4 byte aligned then you incur an extra IO cycle when popping and pushing from the stack. Sure, in this example it's an irrelevance, but it's worthwhile being aware of it.

Share this post


Link to post
Share on other sites
Small update, I just cleaned it up a little bit, still need to add guessing functionality.

Link to the Code Blocks Project File: Sudoku Solver

Main.cpp
#include <iostream>
using namespace std;
#include "Sudoku.h"
#include <windows.h>

double GetMicroTime()
{
LARGE_INTEGER ticks, ticksPerSecond;

QueryPerformanceFrequency(&ticksPerSecond);

QueryPerformanceCounter(&ticks);

return ( double(ticks.QuadPart) / double(ticksPerSecond.QuadPart) );
}

void PrintSudoku(Sudoku *sud)
{
for(int y = 0; y < sud->GetSize(); y++)
{
for(int x = 0; x < sud->GetSize(); x++)
{
if( sud->GetMatrixElement(x, y) < 10)
cout << " ";
cout << sud->GetMatrixElement(x, y) << " ";
}

cout << endl;
}
}

int main()
{
double time1 = 0.0, time2 = 0.0;
Sudoku sud;

char fileName[64];

cout << "Open File: ";
cin >> fileName;

time1 = GetMicroTime();
if( sud.ReadFile(fileName) )
{
time2 = GetMicroTime();
cout << "ReadFile: " << (time2 - time1)*1000.0 << " ms" << endl << endl;

PrintSudoku(&sud);

cout << endl;

time1 = GetMicroTime();
// START TIMING

sud.Solve();

// END TIMING
time2 = GetMicroTime();

PrintSudoku(&sud);

cout << endl << "Solve: " << (time2 - time1)*1000.0 << " ms" << endl << endl;
}
else
cout << "Failed to read file." << endl;

system("PAUSE");
return 0;
}









Sudoku.h
#ifndef SUDOKU_H
#define SUDOKU_H

#include <fstream>

using namespace std;

class Sudoku {

public:
Sudoku();
~Sudoku();

// Methods of sudoku matrix inputs
int ReadFile(const char* filePath);

// 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();

// Fill in the blanks as much as possible without guessing
int Solve();

// Check if the sudoku has been solved
bool IsSolved();

// Take 1 step toward solving
void Step();

// Accessor functions
int GetSize() { return size; }
int GetMatrixElement(int x, int y) { return matrix[x][y]; }

private:
int **matrix;
int size;
bool ***possible;
bool readSuccessful;

void CreateMatrixAndPossibilityArray(int size);
void DeleteMatrixAndPossibilityArray();

bool MarkNotPossible_Row(int x, int y);
bool MarkNotPossible_Column(int x, int y);
bool MarkNotPossible_MiniSquare(int x, int y);

void SetSize( ifstream *file );
};

#endif









Sudoku.cpp
#include "Sudoku.h"
#include "MiscFunctions.h"
#include <iostream>
using namespace std;

Sudoku::Sudoku()
{
size = 1;
readSuccessful = false;
}

Sudoku::~Sudoku()
{
DeleteMatrixAndPossibilityArray();
}

int Sudoku::ReadFile(const char* filePath)
{
bool bSuccess = true;

// Open File
ifstream file(filePath);

// If path given doesnt link to a file
if(!file.good())
return false;

SetSize(&file);
CreateMatrixAndPossibilityArray(size);

int maxLength = IntLen(size);

// Get File Length
file.seekg (0, ios::end);
int fileLen = file.tellg();
file.seekg (0, ios::beg);

// Create array to store the file contents in
char *fileArray = new char[fileLen];

for(int i = 0; i < fileLen; i++)
{
file.get( fileArray);
}

// File inside of array now so close the file
file.close();

// Parse the fileArray for number sections and place them int the matrix array
char *curNumAsStr = new char[maxLength];
int curNumAsStrIndex = 0;
int matrixIndex = 0;

for(int i = 0; i < fileLen; i++)
{
if(fileArray >= '0' && fileArray <= '9')
{
curNumAsStr[curNumAsStrIndex] = fileArray;
curNumAsStrIndex++;
}
else if(curNumAsStrIndex && (fileArray == ' ' || fileArray == '\n'|| i == fileLen-1))
{
matrix[matrixIndex%size][matrixIndex/size] = StringToInt(curNumAsStr);
matrixIndex++;
curNumAsStrIndex = 0;

// Unset curNumAsStr
for(int j = 0; j < maxLength; j++)
curNumAsStr[j] = '\0';
}
}

delete [] curNumAsStr;

delete [] fileArray;

readSuccessful = bSuccess;
return bSuccess;
}

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)
{
// MarkNotPossible functions return true if
// they changed the possibility array
if( MarkNotPossible_Row(x, y) ||
MarkNotPossible_Column(x, y) ||
MarkNotPossible_MiniSquare(x, y) )
{
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;
}

int Sudoku::Solve()
{
// Loop while one of these are making progress
while( MarkNotPossible() || CheckForSinglePossibility() ) {}

return IsSolved();
}

bool Sudoku::IsSolved()
{

// 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 false;
}
}
}

return true;
}

void Sudoku::Step()
{
MarkNotPossible();
CheckForSinglePossibility();
}

void Sudoku::CreateMatrixAndPossibilityArray(int size)
{
// Create the matrix array
matrix = new int*[size];
for(int i = 0; i < size; i++)
{
matrix = new int[size];

for(int j = 0; j < size; j++)
{
matrix[j] = 0;
}
}

// 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;
}
}
}
}

void Sudoku::DeleteMatrixAndPossibilityArray()
{
if( readSuccessful )
{
// 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;
}
}

bool Sudoku::MarkNotPossible_Row(int x, int y)
{
bool bChanged = false;

// 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;
}
}

return bChanged;
}

bool Sudoku::MarkNotPossible_Column(int x, int y)
{
bool bChanged = false;

// 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;
}
}

return bChanged;
}

bool Sudoku::MarkNotPossible_MiniSquare(int x, int y)
{
bool bChanged = false;

// Mark not possible for minisquare
int miniSize = int(sqrt(size));

int ymin = y - (y % miniSize);
int ymax = y + (miniSize - (y % miniSize));

int xmin = x - (x % miniSize);
int xmax = x + (miniSize - (x % 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;
}

// Set the size of the sudoku matrix stored in the file
void Sudoku::SetSize( ifstream *file )
{
char c;
while( file->get(c) && c != '\n' )
{
if(c == ' ')
size++;
}
}









MiscFunctions.h
#ifndef MISCFUNCTIONS_H
#define MISCFUNCTIONS_H

#include <math.h>
#include <iostream>
using namespace std;
int Power(int x, int y)
{
int ret = 1;

for(int i = 0; i < y; i++)
{
ret *= x;
}

return ret;
}

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







Share this post


Link to post
Share on other sites
You moved the function implementations in Soduku.h to Soduku.cpp. That's excellent, but you also need to do that for the functions in MiscFunctions.h
Quote:
Original post by MVP
It would use less memory.

Honestly, saving 3 bytes of memory on a machine with over a billion bytes of memory* is not worth the millisecond you spent considering it. That is an example of micro-optimization at its worst. Avoid optimizing your code for now, it will only lead to hard-to-solve problems.

* Actually, in this case the compiler is likely to keep the variable in a register regardless of the size, so you have saved no memory at all.

Share this post


Link to post
Share on other sites
Thanks. :) I split MiscFunctions.h up. Im going to be looking into algorithms now, I haven't done any complex ones before so Im not sure where to start for the guessing stuff. If you know of any awesome resources for this one I would love a link so I can take a gander. :)

Thanks again. :)

Share this post


Link to post
Share on other sites
Oh boy.

Sorry to say, this is still pretty awful. I haven't had a chance to test anything, cut it up properly into files or write out my explanations of what's wrong coherently, yet; but for now you can go over my notes:


- bizarre file parsing: requires whitespace to separate numbers even though it calculates a "max length" for them - can only generate overflows. No null terminator anyway!
- Hungarian notation on booleans. Also, return bool FFS!
- But never mind that, because the correct approach is to read the data in in the constructor, and throw an exception on failure. Also, storing 'readSuccessful' internally is no use because it isn't checked except to clean up (hint: deleting a null pointer is fine).
- Use the standard library.
- You don't need to comment things like "open the file"; see the other thread.
- Data layout. There should be a separate class to represent individual cells. Having done that, we can organize the algorithm properly, and also see that the 'value' property of a cell is redundant and can be calculated from the possibilities array.
- fstream include goes in Sudoku.cpp, not .h. And never 'using namespace std' in a header!!!
- PrintSudoku is Sudoku class functionality. Also the formatting is not very general.
- Public interface of Sudoku should only have the solve and print functionality.
- Time conversion is the wrong way around.
- endl abuse.
- Don't artificially pause programs at the end!!!
Keep scrolling for improved-source-in-progress...
#include <iostream>
using namespace std;
#include "Sudoku.h"
#include <windows.h>

double GetMicroTime() {
LARGE_INTEGER ticks, ticksPerSecond;

QueryPerformanceFrequency(&ticksPerSecond);

QueryPerformanceCounter(&ticks);

return ( double(ticks.QuadPart) / double(ticksPerSecond.QuadPart) );
}

int main() {
std::string fileName;

cout << "Open File: ";
cin >> fileName;

try {
double time = GetMicroTime();
Sudoku s(fileName);
cout << "ReadFile: " << (GetMicroTime() - time1) / 1000.0 << " ms\n\n" << s << endl;

time = GetMicroTime();
s.solve();
time = GetMicroTime() - time;

cout << s << "\nSolve: " << time / 1000.0 << " ms\n" << endl;
} catch (std::exception& ex) {
cout << "Oops, something went wrong: " << ex.what() << endl;
}
}

#ifndef SUDOKU_H
#define SUDOKU_H

const int UNKNOWN_CELL = 0;
const int IMPOSSIBLE_CELL = -1; // a logical contradiction was found.

class Cell {
public:
Cell(int value, int max) : possibilities(new bool[max]) {
for (int i = 0; i < max; ++i) {
possibilities = (i + 1 == value) || (value == UNKNOWN_CELL);
}
}

~Cell() { delete[] possibilities; }

bool removePossibility(int value) {
if (possibilities[value - 1]) {
possibilities[value - 1] = false;
return true;
}
return false;
}

bool known() {
int v = value();
return v != IMPOSSIBLE_CELL && v != UNKNOWN_CELL;
}

int value() {
int result = IMPOSSIBLE_CELL;
for (int i = 0; i < max; ++i) {
if (possibilities) {
result = (result == IMPOSSIBLE_CELL) ? (i + 1) : UNKNOWN_CELL;
}
}
return result;
}

private:
bool* possibilities;
Cell(const Cell&);
Cell& operator=(const Cell&);
};

class Sudoku {
public:
Sudoku();

// Fill in the blanks as much as possible without guessing
bool solve();

// Check if the sudoku has been solved
bool isSolved();

// Take 1 step toward solving
void reduce();

friend ostream& operator<<(ostream& os, const Sudoku& s);

private:
vector<Cell> matrix;
int size;
int mini_size;

Cell& at(int x, int y) {
return matrix[y * size + x];
}

bool reduce_row(int x, int y, int value);
bool reduce_column(int x, int y, int value);
bool reduce_minisquare(int x, int y, int value);
};
#endif

#include "Sudoku.h"
#include <iostream>
#include <fstream>

using namespace std;

ostream& operator<<(ostream& os, const Sudoku& s) {
// Figure out how wide the numbers may be.
stringstream ss;
ss << s.size;
int width = ss.str().size();

for (int y = 0; y < s.size; y++) {
for (int x = 0; x < s.size; x++) {
os << setwidth(width);
int value = s.at(x, y).value();
switch(value) {
case UNKNOWN_CELL: os << "?"; break;
case IMPOSSIBLE_CELL: os << "X"; break;
default: os << value;
}
}
os << '\n';
}
return os;
}

void Sudoku::appendFileLineToData(const std::string& line, std::vector<int>& data) {
std::stringstream parser(line);
int value;
while (parser >> value) {
data.push_back(value);
}
}

Sudoku::Sudoku(const std::string& filePath) {
ifstream file(filePath.c_str());
// Since we're going to throw an exception for any unexpected file failure,
// we can just let the file object do that for us:
file.exceptions();

vector<int> data;

// Read the first line and deduce the sudoku size.
std::string line;
std::getline(file, line);

appendFileLineToData(line, data);
size = data.size();
// Make sure this is a valid size
mini_size = sqrt(size);
if (size != mini_size * mini_size) {
stringstream error_message("");
error_message << size << " is not a valid sudoku size (must be a square number)\n";
throw std::runtime_error(error_message);
}

// Now read all the rest of the lines.
data.reserve(size * size);
// This is an unusual way of numbering the lines, but it's convenient here.
for (int i = 2; i <= size; ++i) {
std::getline(file, line);
appendFileLineToData(line, data);
if (data.size() != size * i) {
stringstream error_message("");
error_message << "Incorrect number of elements on line " << i << "(expected " << size << ", got " << data.size() - size * (i - 1) << ")\n";
throw std::runtime_error(error_message);
}
}

// Finally we can convert the numbers into Cell objects.
matrix.reserve(size * size);
for (int i = 0; i < size * size; ++i) {
matrix = Cell(data, size);
}
}

int Sudoku::reduce() {
bool changed = false;

for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (at(x, y).known()) {
int value = at(x, y).value();
if (reduce_row(x, y, value) ||
reduce_column(x, y, value) ||
reduce_minisquare(x, y, value)) {
changed = true;
}
}
}
}

return changed;
}

bool Sudoku::solve() {
while (reduce());

return IsSolved();
}

bool Sudoku::isSolved() {
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
if (!at(x, y).known()) {
return false;
}
}
}
return true;
}

bool Sudoku::reduce_row(int x, int y, int value) {
bool changed = false;

for (int z = 0; z < size; z++) {
if (at(z, y).removePossibility(value)) {
changed = true;
}
}

return changed;
}

bool Sudoku::reduce_column(int x, int y, int value) {
bool changed = false;

for (int z = 0; z < size; z++) {
if (at(x, z).removePossibility(value)) {
changed = true;
}
}

return changed;
}

bool Sudoku::reduce_minisquare(int x, int y, int value) {
bool changed = false;

int ymin = (y / mini_size) * mini_size;
int xmin = (x / mini_size) * mini_size;

for (int j = ymin; j < ymin + mini_size; ++j) {
for (int i = xmin; i < xmin + mini_size; ++i) {
if (at(i, j).removePossibility(value)) {
changed = true;
}
}
}
return changed;
}




I pretty much had to rewrite the file parsing from scratch, because the current approach is a dead end. You'll notice the misc functions are *completely gone*. I won't even bother to go into detail about how the power() algorithm can be made faster for large powers, or how it's wasteful to exponentiate each digit instead of just iteratively "multiplying and accumulating"; because it's not important - manually converting integers to strings is, in a desktop environment, a fool's task.

Share this post


Link to post
Share on other sites
Oh wow, some great ideas. I am definetly going to be going through that later. Thanks a lot. Rating++ :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement