📄 源代码.txt
字号:
数独游戏规则
是一种源自18世纪末瑞士的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。
数独的玩法逻辑简单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。
计算机算法简介
本文所讨论的算法是一种通用算法，虽然不能说是最快的算法，但却可以求解所有的数独游戏。
算法准备：
1、一个可能性：表示某个格子可能填写的数字。
2、可能性数目：表示某个格子可能性的数量。为0表示已经确定。
3、区域标志：表示某个格子所在区域（小九宫）的ID，所有区域标志都是预定义的。
4、确定数量：表示所有数字已经确定的格子的数量，为81时则表示已经找到解。
5、整个九宫格用三个矩阵表示：可能性矩阵，数目矩阵，区域标志矩阵
算法的基本思想：
步骤1、将所有未确定的格子的可能性定义为0xFFFF（即所有数字都可能），可能数目为9。
步骤2、寻找所有确定的格子A（可能数目为0），在所有与A同行、同列和同区域的未确定的格子的可能性中减去与A相同的可能性。例如：A确定为9，则与A同行、同列和同区域（区域标志相同）的未确定的格子的可能性与0xFEFF按位与（除去可能性9），并将其可能性数目减少。
在除去可能性的过程中如果发现某个格子B的可能性数目由1减小为0，说明B和A只能取相同的数字，这可能是题目本身无解引起，也肯能是由于步骤3中搜索方向不对引起的，可认为此方向的搜索无解，退出这一方向的搜索。定义这个检查为唯一性检查。
步骤3、寻找所有未确定格子中可能性数目最少的格子M，如果M的可能性数目为1，则确定M：将M的可能性数目定义为0，并把确定数量加1，如果此时确定数量达到81，则报告找到解，否则，在所有与M同行、同列和同区域的未确定的格子的可能性中减去与M相同的可能性，并进行唯一性检查。然后重复步骤3。
如果M的可能性大于1，则把M假设为所有M的可能性，分多个方向进行搜索，在每一个搜索方向重复步骤3（这个可以用递归来实现）。
算法性能
本算法可以在50毫秒以内求解任意有解的数独游戏
见《数独程序开源》
算法核心代码
由于篇幅限制，不能将所有代码贴出来，只贴一些核心的代码，通过研究这些代码已经可以实现本程序。实在有需要可以联系我。
// 优化
int CNumMatrix::Optimize()
{
int x, y;
int i;
bool changed = true;
while(changed)
{
changed = false;
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
if(NumTrans(m_i16mMatrix[x][y]) == 0)
{
return -1;
}
if(m_cmPossible[x][y] == 1)
{
m_cmPossible[x][y] = 0;
for(i = 0; i < m_iSize; i++)
{
// 减少列可能性
if(m_cmPossible[x][i] > 0)
{
this->RemovePossible(x, i, m_i16mMatrix[x][y]);
if(m_cmPossible[x][i] == 0)
{
return -1;
}
}
// 减少行可能性
if(m_cmPossible[i][y] > 0)
{
this->RemovePossible(i, y, m_i16mMatrix[x][y]);
if(m_cmPossible[i][y] == 0)
{
return -1;
}
}
// 减少区域可能性
if(!RemoveRegionPossible(m_cmRegion[x][y], m_i16mMatrix[x][y]))
{
return -1;
}
}
m_iAssured++;
changed = true;
}
}
}
}
return 0;
}
// 数字翻译
int CNumMatrix::NumTrans(__int16 mask)
{
mask &= ~(0xffff << m_iSize);
if(mask >= -1 && mask < 3)
{
return mask;
}
switch(mask)
{
case 0x0004:
return 3;
case 0x0008:
return 4;
case 0x0010:
return 5;
case 0x0020:
return 6;
case 0x0040:
return 7;
case 0x0080:
return 8;
case 0x0100:
return 9;
case 0x0200:
return 10;
case 0x0400:
return 11;
case 0x0800:
return 12;
case 0x1000:
return 13;
case 0x2000:
return 14;
case 0x4000:
return 15;
case 0x8000:
return 16;
}
return -1;
}
// 从文件读取
bool CNumMatrix::ReadFile(LPCTSTR fileName)
{
FILE * fp = fopen(fileName, "r");
if(fp)
{
int x, y;
char stmp[] = " ";
int tmp;
fscanf(fp, "%d %d, %d ", &m_iSize, &m_ivRegion[0], &m_ivRegion[1]);
if(m_iSize > 0 && m_iSize <= NM_MAX_SIZE && Init())
{
for(y = 0; y < m_iSize; y++)
{
for(x = 0; x < m_iSize; x++)
{
fscanf(fp, "%c", &stmp[0]);
if(stmp[0] == '?')
{
m_i16mMatrix[x][y] = -1;
m_cmPossible[x][y] = m_iSize;
}
else
{
sscanf(stmp, "%X", &tmp);
this->SetVal(x, y, NM_MAKE_MASK(tmp));
}
fscanf(fp, "%c", &stmp[0]);
}
}
}
else
{
fclose(fp);
return false;
}
fclose(fp);
return this->CheckPossibility();
}
return false;
}
// 导出到文件
bool CNumMatrix::WriteFile(LPCTSTR fileName)
{
FILE * fp = fopen(fileName, "w");
if(fp)
{
int x, y;
int tmp;
fprintf(fp, "%d %d, %d ", m_iSize, m_ivRegion[0], m_ivRegion[1], m_iAssured);
for(y = 0; y < m_iSize; y++)
{
for(x = 0; x < m_iSize - 1; x++)
{
tmp = NumTrans(m_i16mMatrix[x][y]);
if(tmp >= 0)
{
fprintf(fp, "%X ", tmp);
}
else
{
fprintf(fp, "? ");
}
}
tmp = NumTrans(m_i16mMatrix[x][y]);
if(tmp >= 0)
{
fprintf(fp, "%X ", tmp);
}
else
{
fprintf(fp, "? ");
}
}
fclose(fp);
return true;
}
return false;
}
// 减少区域可能性
bool CNumMatrix::RemoveRegionPossible(char region, __int16 mask)
{
int x, y;
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
if(m_cmRegion[x][y] == region && m_cmPossible[x][y] > 0)
{
RemovePossible(x, y, mask);
if(m_cmPossible[x][y] == 0)
{
return false;
}
}
}
}
return true;
}
// 可能性检查
bool CNumMatrix::CheckPossibility()
{
int x, y;
int i;
m_iAssured = 0;
bool zero = false;
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
if(m_cmPossible[x][y] == 0)
{
m_iAssured++;
}
else
{
m_cmPossible[x][y] = m_iSize;
m_i16mMatrix[x][y] = -1;
}
}
}
if(m_iAssured)
{
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
if(m_cmPossible[x][y] == 0)
{
for(i = 0; i < m_iSize; i++)
{
// 减少列可能性
if(m_cmPossible[x][i] > 0)
{
this->RemovePossible(x, i, m_i16mMatrix[x][y]);
if(m_cmPossible[x][i] == 0)
{
return false;
}
}
// 减少行可能性
if(m_cmPossible[i][y] > 0)
{
this->RemovePossible(i, y, m_i16mMatrix[x][y]);
if(m_cmPossible[i][y] == 0)
{
return false;
}
}
// 减少区域可能性
if(!RemoveRegionPossible(m_cmRegion[x][y], m_i16mMatrix[x][y]))
{
return false;
}
}
}
}
}
}
return true;
}
// 查找解
bool CNumMatrix::FindSolution()
{
static int si = 0;
if(Optimize() < 0)
{
return false;
}
if(m_iAssured == m_iSize * m_iSize)
{
return true;
}
CNumMatrix tmp;
// 查找最小可能性的格子
int x, y;
int mx = -1, my = -1;
char min = m_iSize + 1;
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
if(m_cmPossible[x][y] != 0 && m_cmPossible[x][y] < min)
{
mx = x;
my = y;
min = m_cmPossible[x][y];
}
}
}
// 取得可能性
__int16 possible[NM_MAX_SIZE];
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -