解数独程序

// Soduku.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <map>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
#define ROW_NUM (9)
#define COL_NUM (9)
#define NUMBERS (9)
const unsigned char originalArray[ROW_NUM][COL_NUM] = {
	{0,0,0,1,0,0,2,6,0},
	{7,0,0,0,3,0,0,0,0},
	{3,0,2,0,8,0,4,0,0},
	{0,0,0,4,0,8,0,0,1},
	{0,3,5,0,0,0,9,4,0},
	{2,0,0,3,0,5,0,0,0},
	{0,0,6,0,5,0,7,0,9},
	{0,0,0,0,4,0,0,0,8},
	{0,5,7,0,0,9,0,0,0}
};
const unsigned char digits[NUMBERS] = {1,2,3,4,5,6,7,8,9};

struct Grid{
	unsigned char row;
	unsigned char column;
	unsigned char value;
	map<unsigned char, unsigned char> options;
	Grid(){
		row = 0;
		column = 0;
		value = 0;
		options.clear();
	}
};

Grid soduku[ROW_NUM][COL_NUM] = {};

struct NineGrid{
	pair<unsigned char, unsigned char> start;
	pair<unsigned char, unsigned char> end;
	set<unsigned char> values;
	NineGrid(){
		start.first = 0;
		start.second = 0;
		end.first = 0;
		end.second = 0;
		values.clear();
	}
};

NineGrid nineGrid[(ROW_NUM/3)*(COL_NUM/3)] = {};

void InitializeSoduku(){
	for(unsigned char i = 0; i < ROW_NUM; ++i)
	{
		for(unsigned char j = 0; j < COL_NUM; ++j)
		{
			soduku[i][j].row = i;
			soduku[i][j].column = j;
			soduku[i][j].value = originalArray[i][j];
		}
	}
	unsigned char index = 0;
	for(unsigned char i = 0; i < ROW_NUM; i+=3)
	{
		for(unsigned char j = 0; j < COL_NUM; (index++,j+=3))
		{
			nineGrid[index].start.first = i;
			nineGrid[index].start.second = j;
			nineGrid[index].end.first = i+2;
			nineGrid[index].end.second = j+2;
		}
	}
	for(unsigned char n = 0; n < ROW_NUM; ++n)
	{
		for(unsigned char i = nineGrid[n].start.first; i <= nineGrid[n].end.first; ++i)
		{
			for(unsigned char j = nineGrid[n].start.second; j <= nineGrid[n].end.second; ++j)
			{
				if(soduku[i][j].value != 0)
				{
					nineGrid[n].values.insert(soduku[i][j].value);
				}
			}
		}
	}
}
void CollectRow(set<unsigned char>& row, unsigned char rowIndex)
{
	for(unsigned char j = 0; j < COL_NUM; ++j)
	{
		if(soduku[rowIndex][j].value != 0)
		{
			row.insert(soduku[rowIndex][j].value);
		}
	}
}
void CollectColumn(set<unsigned char>& col, unsigned char colIndex)
{
	for(unsigned char i = 0; i < ROW_NUM; ++i)
	{
		if(soduku[i][colIndex].value != 0)
		{
			col.insert(soduku[i][colIndex].value);
		}
	}
}
void CollectNineGrid(set<unsigned char>& gridSet,unsigned char row, unsigned char col)
{
	for(unsigned int i = 0; i < ROW_NUM; ++i)
	{
		if(nineGrid[i].start.first <= row && row <= nineGrid[i].end.first)
		{
			if(nineGrid[i].start.second <= col && col <= nineGrid[i].end.second)
			{
				for(unsigned char m = nineGrid[i].start.first; m <= nineGrid[i].end.first; ++m )
				{
					for(unsigned char n = nineGrid[i].start.second; n <= nineGrid[i].end.second; ++n)
					{
						if(soduku[m][n].value != 0)
						{
							gridSet.insert(soduku[m][n].value);
						}
					}
				}
				break;
			}
		}
	}
}
void CollectAll(set<unsigned char>& vals,unsigned char row, unsigned char col)
{
	vals.clear();
	CollectRow(vals, row);
	CollectColumn(vals, col);
	CollectNineGrid(vals, row, col);
}
void PrintCurrent()
{
	for(unsigned char i = 0; i < ROW_NUM; ++i)
	{
		for(unsigned char j = 0; j < COL_NUM; ++j)
		{
			if(soduku[i][j].value == 0)
			{
				cout<<"(";
				std::map<unsigned char, unsigned char>::iterator iter = soduku[i][j].options.begin();
				for(iter; iter !=  soduku[i][j].options.end(); ++iter)
				{
					cout<<(unsigned short)iter->second<<",";
				}
				cout<<")";
			}else
			{
				cout<<(unsigned short)soduku[i][j].value<<" ";
			}
			
		}
		cout<<std::endl;
	}
}
bool HasExisted(std::set<unsigned char>& values, unsigned char val)
{
	return values.find(val) != values.end();
}
void DigitsLoop()
{
	for(unsigned char m = 0; m < NUMBERS; ++m)
	{
		unsigned char digit = digits[m];
		for(unsigned char n = 0; n < ROW_NUM; ++n)
		{
			for(unsigned char i = nineGrid[n].start.first; i <=  nineGrid[n].end.first; ++i)
			{
				for(unsigned char j = nineGrid[n].start.second; j <= nineGrid[n].end.second; ++j)
				{
					if(soduku[i][j].value != 0)
					{
						continue;
					}
					set<unsigned char> values;
					do
					{	//验证九宫格中的数
						values.clear();
						CollectNineGrid(values, i, j);
						if(HasExisted(values, digit))
						{
							break;
						}
						//验证横排
						values.clear();
						CollectRow(values, i);
						if(HasExisted(values, digit))
						{
							break;
						}
						//验证竖排
						values.clear();
						CollectColumn(values, j);
						if(HasExisted(values, digit))
						{
							break;
						}

						soduku[i][j].options[digit] = digit;
					}while(0);
				}
			}
		}
	}
}

void AddToNineGridSet(unsigned char row, unsigned char col, unsigned char val)
{
	for(unsigned int i = 0; i < ROW_NUM; ++i)
	{
		if(nineGrid[i].start.first <= row && row <= nineGrid[i].end.first)
		{
			if(nineGrid[i].start.second <= col && col <= nineGrid[i].end.second)
			{
				nineGrid[i].values.insert(val);
				break;
			}
		}
	}
}
void RemoveAll(unsigned char row, unsigned char col, unsigned char val)
{
	//1.去除行中其他空格可选项中val对应的项目
	std::map<unsigned char, unsigned char>::iterator iter;
	for(unsigned char j = 0; j < COL_NUM; ++j)
	{
		if(soduku[row][j].options.empty())
		{
			continue;
		}
		iter = soduku[row][j].options.find(val);

		if(iter != soduku[row][j].options.end())
		{
			soduku[row][j].options.erase(iter);
		}
	}
	//2.去除列中其他空格可选项中val对应的项目
	for(unsigned int i = 0; i < ROW_NUM; ++i)
	{
		if(soduku[i][col].options.empty())
		{
			continue;
		}
		iter = soduku[i][col].options.find(val);

		if(iter != soduku[i][col].options.end())
		{
			soduku[i][col].options.erase(iter);
		}
	}
	//3.去除九宫格中其他空格可选项中val对应的项目
	for(unsigned int i = 0; i < ROW_NUM; ++i)
	{
		if(nineGrid[i].start.first <= row && row <= nineGrid[i].end.first)
		{
			if(nineGrid[i].start.second <= col && col <= nineGrid[i].end.second)
			{
				for(unsigned char m = nineGrid[i].start.first; m <= nineGrid[i].end.first; ++m )
				{
					for(unsigned char n = nineGrid[i].start.second; n <= nineGrid[i].end.second; ++n)
					{
						if(soduku[m][n].options.empty())
						{
							continue;
						}
						iter = soduku[m][n].options.find(val);

						if(iter != soduku[m][n].options.end())
						{
							soduku[m][n].options.erase(iter);
						}
					}
				}
				break;
			}
		}
	}
}
void MakeChoice()
{
	for(unsigned char i = 0; i < ROW_NUM; ++i)
	{
		for(unsigned char j = 0; j < COL_NUM; ++j)
		{
			if(soduku[i][j].options.size() == 1)
			{
				//赋值给对应的空格
				soduku[i][j].value = soduku[i][j].options.begin()->first;
				//加入九宫格中的集合中
				AddToNineGridSet(i, j, soduku[i][j].value);
				//去除横列和九宫格中其他空格可选项中含有该值的项目
				RemoveAll(i, j, soduku[i][j].value);
			}
		}
	}
}
void Exception()
{
	set<unsigned char> vals;
	
	for(unsigned char i = 0; i < ROW_NUM; ++i)
	{
		for(unsigned char j = 0; j < COL_NUM; ++j)
		{
			if(soduku[i][j].value != 0)
			{
				continue;
			}
			CollectAll(vals, i, j);
			vector<unsigned char> result(10);
			std::set_difference(digits, digits+NUMBERS, vals.begin(), vals.end(), result.begin());

			for(unsigned int n = 0; n < result.size(); ++n)
			{
				if(result[n] != 0)
				{
					soduku[i][j].options[result[n]] = result[n];
				}
			}
		}
	}
}
bool CanEnd()
{
	for(unsigned char i = 0; i < ROW_NUM; ++i)
	{
		for(unsigned char j = 0; j < COL_NUM; ++j)
		{
			if(soduku[i][j].value == 0)
			{
				return false;
			}
		}
	}

	return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
	InitializeSoduku();
	do
	{
		DigitsLoop();
		MakeChoice();
		Exception();
		MakeChoice();
		
	}while(!CanEnd());

	PrintCurrent();

	getchar();

	return 0;
}