1nummatrix.cpp

用C++写的数独游戏。提供了各种功能

#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);
}