注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简单代码

寻找代码的灵魂

 
 
 

日志

 
 
关于我

对于本博客内所有原创文章和代码的引用必须标明“来源:http://simplesource.blog.163.com/”。如需应用于商业目的必须经本人同意,本人对所有原创文章和代码保留一切权利。 PS:需要部分程序源代码的请留下邮箱地址

网易考拉推荐

数独游戏求解程序(附源代码)  

2007-08-10 16:00:21|  分类: 我的程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

  数独游戏规则

  是一种源自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];

  if(mx == -1)

  {

    return false;

  }

  int sum = GetPossibleVal(mx, my, possible);

  // 遍历可能性

  int i;

  for(i = 0; i < sum; i++)

  {

    memcpy(&tmp, this, sizeof(CNumMatrix));

    tmp.SetVal(mx, my, possible[i]);

    if(tmp.CheckPossibility() && tmp.FindSolution())

    {

      memcpy(this, &tmp, sizeof(CNumMatrix));

      return true;

    }

  }

 

  return false;

}

  评论这张
 
阅读(16536)| 评论(35)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018