shuducore.cpp

玩过数独吗？这里是一个数独的求解程序。可以为你挽救不少脑细胞。题目输入格式：逐行输入数字

#include "StdAfx.h"
#include "ShuDuCore.h"
#include <stack>
#include <iostream>
#include <assert.h>
using namespace std;

ShuDuCore::ShuDuCore(void)
{
	memset(probability,0,NUMS*sizeof(int));
}

ShuDuCore::~ShuDuCore(void)
{
}

void ShuDuCore::DoShudu(int* input)
{
	int Cur_data[NUMS];
	for(int i=0; i<NUMS; i++)
	{
		Cur_data[i] = input[i]; 
	}

	int x,y,t;
	int pro[WIDTH];
	int unset = 1;
	while(unset!=0)
	{		
		//change the probability map and find the least one
		unset = 0;
		t = 101;
		for(int i=0; i<WIDTH; i++)
		{
			for(int j=0; j<WIDTH; j++)
			{
				probability[i*WIDTH+j] = GetPossibility(i,j,Cur_data,pro);
				if(probability[i*WIDTH+j] < t)
				{
					t = probability[i*WIDTH+j];
					x=i;
					y=j;
				}
				if(probability[i*WIDTH+j] != 100)
				{
					unset++;
				}
			}
		}

		//recursion
		if(unset==0)
		{
			break;
		}
		else if(t == 0)
		{
			a_step tstep;
			if(AllStep.size() == 0)
			{
				cout<< "failed to find a solution!" << endl;
				return;
			}
			else
			{
				tstep=AllStep.top();
				AllStep.pop();
				Cur_data[tstep.x*WIDTH+tstep.y] = 0;
//				cout << tstep.x <<' '<< tstep.y <<' '<< "0 " <<endl;
			}

			while(tstep.val.size() == 0)
			{
				if(AllStep.size() == 0)
				{
					cout<< "failed to find a solution!" << endl;
					return;
				}
				tstep=AllStep.top();
				AllStep.pop();
				Cur_data[tstep.x*WIDTH+tstep.y] = 0;
//				cout << tstep.x <<' '<< tstep.y <<' '<< "0 " <<endl;
			}
 
			Cur_data[tstep.x*WIDTH+tstep.y] = tstep.val.top();
//			cout << tstep.x << ' '<< tstep.y <<' '
//				<< tstep.val.top() <<' '<< "tstep"<< endl;
			tstep.val.pop();
			AllStep.push(tstep);
		}
		else
		{
			//creat new step node
			if(x==0&&y==0)
			{
				int xx = 0;
			}
			GetPossibility(x,y,Cur_data,pro);
			a_step newStep;
			newStep.x = x;
			newStep.y = y;
			for(int i=0; i<WIDTH; i++)
			{
				if(pro[i] == 0)
				{
					newStep.val.push(i+1);
				}
			}
			if(newStep.x==0&&newStep.y==0&&newStep.val.top() == 9)
			{
				int xia = 0;
			}
			//change the data
			Cur_data[newStep.x*WIDTH+newStep.y] = newStep.val.top();
//			cout << newStep.x << ' ' << newStep.y << ' '
//				<< newStep.val.top() << ' '<< "newstep" <<endl;
			newStep.val.pop();
			AllStep.push(newStep);
		}

// 		//test
// 		cout << "¨X¨T¨T¨T¨j¨T¨T¨T¨j¨T¨T¨T¨[" << endl;
// 		for(int i=0; i<WIDTH; i++)
// 		{
// 			for(int j=0; j<WIDTH; j++)
// 			{
// 				if(j==0||j==3||j==6)
// 					cout << "¨U";
// 				cout << Cur_data[i*WIDTH+j] << ' ';
// 			}
// 			cout <<"¨U" << endl;
// 			if(i==2||i==5)
// 				cout <<"¨d¨T¨T¨T¨p¨T¨T¨T¨p¨T¨T¨T¨g" << endl;
// 		}
// 		cout << "¨^¨T¨T¨T¨m¨T¨T¨T¨m¨T¨T¨T¨a" << endl;
	}

	//finished
	cout << endl;
	cout << ">>>>> just point to xia" << endl;
	cout << endl;
	cout << "╔═══╦═══╦═══╗" << endl;
	for(int i=0; i<WIDTH; i++)
	{
		for(int j=0; j<WIDTH; j++)
		{
			if(j==0||j==3||j==6)
				cout << "║";
			cout << Cur_data[i*WIDTH+j] << ' ';
		}
		cout <<"║" << endl;
		if(i==2||i==5)
				cout <<"╠═══╬═══╬═══╣"<<endl;
	}
	cout << "╚═══╩═══╩═══╝" << endl;

}

int ShuDuCore::GetPossibility(int x, int y, int* Cur_data, int *p)
{
	memset(p,0,9*sizeof(int));

	int num = 0;
	

	if(Cur_data[x*WIDTH+y] != 0) //had been set
	{
		num =  100;//never to change
	}
	else
	{
		for(int i=0; i<WIDTH; i++)
		{
			if(Cur_data[x*WIDTH+i]!=0)
				p[Cur_data[x*WIDTH+i]-1] = 1;
			if(Cur_data[i*WIDTH+y]!=0)
				p[Cur_data[i*WIDTH+y]-1] = 1;
		}

		int xp = x/3*3;
		int yp = y/3*3;
		for(int i=0; i<3; i++)
		{
			for(int j=0; j<3; j++)
			{
				if(Cur_data[(i+xp)*WIDTH + j+yp] != 0)
					p[Cur_data[(i+xp)*WIDTH + j+yp]-1] = 1;
			}
		}

		for(int i=0; i<WIDTH; i++)
		{
			if(p[i] == 0)
			{
				num++;
			}
		}
	}

	return num;
}