Sudoku Solver

This will really be the last time I will look at depth first game trees. I could not resist modifying my old sudoku solver to the template I had proposed earlier

bool ComputeSolution(set<cell>& currentState)
{
	cell const lastCell = { 9, 9, 9, 9 };

	if (currentState.size() == 81)
	{
		return true;
	}
	//find the first empty cell
	cell emptycell = { 0, 0, 0, 0 };
	GetNextFreeCell(emptycell, currentState);
	emptycell.box = boxId(emptycell.row, emptycell.col);
	//fill the empty cell
	for (int val = 1; val <= 9 ; ++val)
	{
		emptycell.val = val;
		bool found = legal(currentState,  emptycell);
		if (found)
		{
			set<cell> newstate(currentState);
			newstate.insert(emptycell);
			if (ComputeSolution(newstate))
			{
				currentState.swap(newstate);
				return true;
			}
		}
	}
	return false;
}
Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Algorithm, C++, Software Engineering. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s