www.pudn.com > sudoku.rar > 1NumMatrix.cpp
#include "StdAfx.h"
#include ".\nummatrix.h"
CNumMatrix::CNumMatrix(void)
: m_iAssured(0)
, m_iSize(9)
{
m_ivSel[0] = 2;
m_ivSel[1] = 5;
m_ivRegion[0] = 3;
m_ivRegion[1] = 3;
}
CNumMatrix::~CNumMatrix(void)
{
}
// 设置区域
bool CNumMatrix::SetRegion(int nx, int ny)
{
if(m_iSize % nx || m_iSize % ny)
{
return false;
}
m_ivRegion[0] = nx;
m_ivRegion[1] = ny;
int ex = m_iSize / nx;
int x, y;
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
m_cmRegion[x][y] = x / nx + (y / ny) * ex;
}
}
return true;
}
// 取得可能值
int CNumMatrix::GetPossibleVal(int x, int y, __int16 possible[])
{
int sum = 0;
__int16 mask = 1;
__int16 tmp = m_i16mMatrix[x][y];
for(int i = 1; i <= m_iSize; i++)
{
if(tmp & mask)
{
possible[sum] = mask;
sum++;
}
mask <<= 1;
}
m_cmPossible[x][y] = sum;
return sum;
}
// 优化
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(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(char * fileName)
{
FILE * fp = fopen(fileName, "r");
if(fp)
{
int x, y;
char stmp[] = " ";
int tmp;
fscanf(fp, "%d\n%d, %d\n", &m_iSize, &m_ivRegion[0], &m_ivRegion[1]);
if(m_iSize > 0 && m_iSize <= NM_MAX_SIZE && Init(m_ivRegion[0], m_ivRegion[1]))
{
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(char * fileName)
{
FILE * fp = fopen(fileName, "w");
if(fp)
{
int x, y;
int tmp;
fprintf(fp, "%d\n%d, %d(%d)\n", 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\n", tmp);
}
else
{
fprintf(fp, "?\n");
}
}
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;
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;
// 遍历可能性
__int16 possible[NM_MAX_SIZE];
int x, y;
char min = m_iSize + 1;
int sum, i;
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
if(m_cmPossible[x][y] > 0)
{
sum = GetPossibleVal(x, y, possible);
for(i = 0; i < sum; i++)
{
memcpy(&tmp, this, sizeof(CNumMatrix));
tmp.SetVal(x, y, possible[i]);
/*char s[100];
sprintf(s, "z-%04d.txt", si++);
tmp.WriteFile(s);*/
if(tmp.CheckPossibility() && tmp.FindSolution())
{
memcpy(this, &tmp, sizeof(CNumMatrix));
return true;
}
}
}
}
}
return false;
}
// 绘制
void CNumMatrix::Paint(CDC * pDC)
{
CFont font;
VERIFY(font.CreateFont(
NM_FONT_WIDTH, // nHeight
0, // nWidth
0, // nEscapement
0, // nOrientation
FW_BOLD, // nWeight
FALSE, // bItalic
FALSE, // bUnderline
0, // cStrikeOut
ANSI_CHARSET, // nCharSet
OUT_DEFAULT_PRECIS, // nOutPrecision
CLIP_DEFAULT_PRECIS, // nClipPrecision
DEFAULT_QUALITY, // nQuality
DEFAULT_PITCH | FF_SWISS, // nPitchAndFamily
"黑体")); // lpszFacename
CFont* def_font = pDC->SelectObject(&font);
int x, y;
int i;
pDC->FillSolidRect(0, 0, m_iSize * NM_GRID_WIDTH, m_iSize * NM_GRID_HEIGHT, RGB(255, 255, 255));
// 绘制灰色区域
int nx, ny;
nx = m_iSize / m_ivRegion[0];
ny = m_iSize / m_ivRegion[1];
for(x = 0; x < nx; x++)
{
for(y = 0; y < ny; y++)
{
if(((x % 2) + (y % 2)) % 2)
{
pDC->FillSolidRect(
x * NM_GRID_WIDTH * m_ivRegion[0],
y * NM_GRID_HEIGHT * m_ivRegion[1],
NM_GRID_WIDTH * m_ivRegion[0],
NM_GRID_HEIGHT * m_ivRegion[1],
RGB(192, 192, 192));
}
}
}
pDC->SetBkMode(TRANSPARENT);
// 划线
for(i = 0; i <= m_iSize; i++)
{
pDC->MoveTo(0, i * NM_GRID_HEIGHT);
pDC->LineTo(m_iSize * NM_GRID_WIDTH, i * NM_GRID_HEIGHT);
pDC->MoveTo(i * NM_GRID_WIDTH, 0);
pDC->LineTo(i * NM_GRID_WIDTH, m_iSize * NM_GRID_HEIGHT);
}
if(m_ivSel[0] >= 0 && m_ivSel[1] >= 0)
{
pDC->MoveTo(m_ivSel[0] * NM_GRID_WIDTH + 1, m_ivSel[1] * NM_GRID_HEIGHT + 1);
pDC->LineTo(m_ivSel[0] * NM_GRID_WIDTH + 1, (m_ivSel[1] + 1) * NM_GRID_HEIGHT - 1);
pDC->LineTo((m_ivSel[0] + 1) * NM_GRID_WIDTH - 1, (m_ivSel[1] + 1) * NM_GRID_HEIGHT - 1);
pDC->LineTo((m_ivSel[0] + 1) * NM_GRID_WIDTH - 1, m_ivSel[1] * NM_GRID_HEIGHT + 1);
pDC->LineTo(m_ivSel[0] * NM_GRID_WIDTH + 1, m_ivSel[1] * NM_GRID_HEIGHT + 1);
}
CString s;
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
i = NumTrans(m_i16mMatrix[x][y]);
if(i != -1)
{
s.Format("%X", i);
}
else
{
s = " ";
}
pDC->TextOut(
x * NM_GRID_WIDTH + NM_FONT_DW,
y * NM_GRID_HEIGHT + NM_FONT_DH, s);
}
}
CFont font2;
VERIFY(font2.CreateFont(
12, // nHeight
0, // nWidth
0, // nEscapement
0, // nOrientation
FW_NORMAL, // nWeight
FALSE, // bItalic
FALSE, // bUnderline
0, // cStrikeOut
ANSI_CHARSET, // nCharSet
OUT_DEFAULT_PRECIS, // nOutPrecision
CLIP_DEFAULT_PRECIS, // nClipPrecision
DEFAULT_QUALITY, // nQuality
DEFAULT_PITCH | FF_SWISS, // nPitchAndFamily
"黑体")); // lpszFacename
pDC->SelectObject(&font2);
pDC->SetTextColor(RGB(0, 0, 255));
for(x = 0; x < m_iSize; x++)
{
for(y = 0; y < m_iSize; y++)
{
s.Format("%X", this->m_cmPossible[x][y]);
pDC->TextOut(
x * NM_GRID_WIDTH + 3,
y * NM_GRID_HEIGHT + 2, s);
}
}
pDC->SelectObject(def_font);
}