SudokuSolverC.cpp

#include <tchar.h>
#include <iostream>
#include <list>
#include <string>
#include <sstream>
#include <Windows.h>

using namespace std;

class Grid
{
public:
	int values[9][9];
	int resolved_count;
	list<int> possibilities[9][9];
	void set_value(int x, int y,int v)
	{
		values[x][y] = v;
		for(int i = 0; i < 9; i++)
		{
			if(y != i)
				possibilities[x][i].remove(v);
			if(x != i)
				possibilities[i][y].remove(v);
		}
		int rectX = x / 3 * 3, rectY = y / 3 * 3;
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				possibilities[rectX + i][rectY + j].remove(v);
		resolved_count++;
	}
	void update_values()
	{
		bool updated;
		do
		{
			updated = false;
			for (int i = 0; i < 9; i++)
				for(int j = 0; j < 9; j++)
					if(values[i][j] == 0 && possibilities[i][j].size() == 1)
					{
						set_value(i, j, possibilities[i][j].front());
						updated = true;
					}
		}
		while (updated);
	}
	string get_string()
	{
		stringstream ss;
		for (int i = 0; i < 9; i++)
		{
			for(int j = 0; j < 9; j++)
				ss << values[i][j] << " ";
			ss << "\r\n";
		}
		return ss.str();
	}

	Grid() 
	{
		for (int i = 0; i < 9; i++)
		{
			for(int j = 0; j < 9; j++)
			{
				for(int k = 1; k < 10; k++)
					possibilities[i][j].push_back(k);
			}
		}
		resolved_count = 0;
	}
	Grid(const Grid& another)
	{
		for (int i = 0; i < 9; i++)
		{
			for(int j = 0; j < 9; j++)
			{
				values[i][j] = another.values[i][j];
				possibilities[i][j] = *new list<int>(another.possibilities[i][j]);
			}
		}
		resolved_count = another.resolved_count;
	}
} grid;

bool resolve(int x, int y, Grid* state)
{
	Grid copy = Grid(*state);
	list<int> possibilities = list<int>(copy.possibilities[x][y]);
	for(list<int>::const_iterator iterator = possibilities.begin();
		iterator != possibilities.end();
		++iterator)
	{
		copy.set_value(x, y, *iterator);
		copy.update_values();
		if(copy.resolved_count == 81)
		{
			cout << copy.get_string() << endl;
			return true;
		}

		int nextX, nextY, thisCount, nextCount = 10;
		bool skip = false;
		for (int i = 0; i < 9; i++)
		{
			for(int j = 0; j < 9; j++)
			{
				if(copy.values[i][j] == 0)
				{
					thisCount = copy.possibilities[i][j].size();
					if(thisCount == 0)
					{
						skip = true;
						break;
					}
					if(thisCount < nextCount)
					{
						nextX = i;
						nextY = j;
						nextCount = thisCount;
					}
				}
			}
			if(skip)
				break;
		}
		if(!skip)
			if(resolve(nextX, nextY, &copy))
				return true;
		copy = Grid(*state);
	}
	return false;
}

double PCFreq = 0.0;
__int64 CounterStart = 0;

void StartCounter()
{
    LARGE_INTEGER li;
    if(!QueryPerformanceFrequency(&li))
	cout << "QueryPerformanceFrequency failed!\n";

    PCFreq = li.QuadPart;

    QueryPerformanceCounter(&li);
    CounterStart = li.QuadPart;
}
double GetCounter()
{
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return double(li.QuadPart-CounterStart)/PCFreq;
}

int _tmain(int argc, _TCHAR* argv[])
{
	grid.set_value(0, 0, 8);
	grid.set_value(1, 2, 3);
	grid.set_value(1, 3, 6);
	grid.set_value(2, 1, 7);
	grid.set_value(2, 4, 9);
	grid.set_value(2, 6, 2);
	grid.set_value(3, 1, 5);
	grid.set_value(3, 5, 7);
	grid.set_value(4, 4, 4);
	grid.set_value(4, 5, 5);
	grid.set_value(4, 6, 7);
	grid.set_value(5, 3, 1);
	grid.set_value(5, 7, 3);
	grid.set_value(6, 2, 1);
	grid.set_value(6, 7, 6);
	grid.set_value(6, 8, 8);
	grid.set_value(7, 2, 8);
	grid.set_value(7, 3, 5);
	grid.set_value(7, 7, 1);
	grid.set_value(8, 1, 9);
	grid.set_value(8, 6, 4);

	StartCounter();

	// grid.update_values();

	if(grid.resolved_count == 81)
		cout << grid.get_string() << endl;
	else
	{
		int nextX, nextY, thisCount, nextCount = 10;
		for (int i = 0; i < 9; i++)
		{
			for(int j = 0; j < 9; j++)
			{
				if(grid.values[i][j] == 0)
				{
					thisCount = grid.possibilities[i][j].size();
					if(thisCount < nextCount)
					{
						nextX = i;
						nextY = j;
						nextCount = thisCount;
					}
				}
			}
		}
		resolve(nextX, nextY, &grid);
	}
	
	cout << GetCounter() << endl;

	string input;
	cin >> input;
	return 0;
}