Jump to content
  • Advertisement
Sign in to follow this  
MVP

Sudoku Solver Class

This topic is 4258 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!