ninegong.cpp

使用MFC写的一个解数独的程序

// NineGong.cpp: implementation of the NineGong class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Sudu.h"
#include "NineGong.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

NineGong::NineGong()
{

}

NineGong::~NineGong()
{

}
//设置初始值，value 1~9
//x,y 0~8
//若取值范围不对，则返回false
bool NineGong::SetValue(int x,int y,int value)
{
	if((x>=0 && x<9) 
		&& (y>=0&& y<9) 
		&& (value>0 && value<10))
	{
	    cell[x][y].value=value;
		cell[x][y].testvalue=value;
	    return true;
	}
	else
	{
	    return false;
	}
}

//功能：判断当前格子内是否还有可以使用的数字
//有的话，计算下一格子run(x+1,y+1)，根据run(x+1,y+1)返回结果
//若返回为false则清理痕迹，返回false
//若返回为true则返回true
//x,y为cell[][]的维数，需在x，y超限的时候修改其数值

bool NineGong::run(int x,int y)
{
	if(y>8)
	{
		y=0;
		x=x+1;
		if(x>8)
		{
			//现在已超出数独的最大范围，到达这个位置说明这一流程的数值已是最终的解
			return true;
		}
	}
	bool bRtn;
	while(true)
	{
		bRtn=func_testcell(x,y);
		if(bRtn==true)
		{
			if(true==run(x,y+1))//后面的可以找到合适的数值的时候，说明求解成功
			{
				return true;
			}
			else
			{
				if(cell[x][y].num[0]<9)
				{
					cell[x][y].num[0]=cell[x][y].num[0]+1;
				}
				else
				{
					cell[x][y].num[0]=1;
					cell[x][y].testvalue=cell[x][y].value ;
					return false;					
				}
			}
		}
		else
		{
			cell[x][y].num[0]=1; //清理痕迹
			cell[x][y].testvalue=cell[x][y].value ;
			return false;
		}
	}
}
//cell[x][y].num[10]
//判断cell[x][y].num[]中是否有符合条件的数值，没有的话返回false
//条件就是其横竖、即所在的九宫内没有相同的数值
//有的话返回true，并设置testvalue为相应的数值
//如果本格内也有确定的数值，则返回true
bool NineGong::func_testcell(int x, int y)
{
	if(cell[x][y].value!=0)
	{
		return true;	
	}
	for(int i=cell[x][y].num[0];i<10;i++)
	{
		if(0==cell[x][y].num[i]) //num[]中存放的为可能的数值，如果为零则已没有可能的了
		{
			return false;
		}
		if(false==find_x(x,y,cell[x][y].num[i]))			//横向查找
		{
			if(false==find_y(x,y,cell[x][y].num[i]))		//纵向查找
			{
				if(false==find_nine(x,y,cell[x][y].num[i]))	//九宫
				{
					//找到了一个横竖及其所在的九宫内都没有的数值
					cell[x][y].num[0]=i;
					cell[x][y].testvalue=cell[x][y].num[i];
					return true;				
				}
			}
		}
	}
	return false;	//没有找到合适的数值
}
//横向查找相同的数值
bool NineGong::find_x(int x, int y, int value)
{
	for(int i=0;i<9;i++)
	{
		if(value==cell[x][i].testvalue)
		{
			if(i==y) 
			{
				continue;
			}
			return true;
		}
	}
	return false;
}
//纵向查找相同的数值
bool NineGong::find_y(int x, int y, int value)
{
	for(int i=0;i<9;i++)
	{
		if(value==cell[i][y].testvalue)
		{
			if(i==x) 
			{
				continue;
			}
			return true;
		}
	}
	return false;
}
//九宫内查找
bool NineGong::find_nine(int x, int y, int value)
{
	int t_x=3*(int)(x/3);	// 本格所在九宫左上角坐标x
	int t_y=3*(int)(y/3);	// 本格所在九宫左上角坐标y
	for(int i=t_x;i<t_x+3;i++)
	{
		if(i==x)		//同一行的话不需比较
		{
			continue;		
		}
		for(int j=t_y;j<t_y+3;j++)
		{
			if(j==y)	//同一列不需比较
			{
				continue;
			}
			if(value==cell[i][j].testvalue)
			{				
				return true;
			}
		}
	}
	return false;
}
//扫描所有的格子，得到每个格子里可能的数值放到cell[][].value中
//方法：开始时设置cell[][].num[]的数值为1-9，
//如果某格子中为n，则其横向、纵向、相邻的九宫内不能有相同的数字n
//设置 这些格子cell[][].num[n]=0
//最后统计一下，cell[][].num[0]为cell[][].num[1-9]中不为零的数值的个数
void NineGong::scanall()
{
	int i,j;
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			cell[i][j].initCell();
		}
	}
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			if(cell[i][j].value!=0)
			{
				clear(i,j,cell[i][j].value);
			}
		}
	}
	//整理,去掉cell[i][j].num[]中的零
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			int m=1;
			int temp=0;
			for(int k=1;k<10;k++)
			{
				if(cell[i][j].num[k]!=0)
				{
					temp=cell[i][j].num[k];
					cell[i][j].num[k]=0;
					cell[i][j].num[m]=temp;
					m=m+1;
				}
			}
		}
	}

}

void NineGong::clear(int x, int y, int index)
{
	int i;
	for(i=0;i<9;i++)
	{
		cell[x][i].num[index]=0;
	}
	for(i=0;i<9;i++)
	{
		cell[i][y].num[index]=0;
	}
	int t_x=3*(int)(x/3);	// 本格所在九宫左上角坐标x
	int t_y=3*(int)(y/3);	// 本格所在九宫左上角坐标y
	for(i=t_x;i<t_x+3;i++)
	{
		if(i==x)		//同一行的话不需比较
		{
			continue;		
		}
		for(int j=t_y;j<t_y+3;j++)
		{
			if(j==y)	//同一列不需比较
			{
				continue;
			}
			cell[i][j].num[index]=0; 
		}
	}
}