数独 算法 C语言 代码

一、步骤：

1.对每一个空格，根据规则推断它可能填入的数字，并存储它的所有可能值；

2.根据可能值的个数，确定填写的顺序。比如说，有些空格只有一种可能，那必然是正确的结果，首先填入。

3.将所有只有一种可能的空格填写完毕以后，回到步骤1，重新确定剩下空格的可能值；

4.当没有只有一种可能的空格时（即每个空格都有两种以上可能），按照可能值个数从小到大的顺序，使用深度（广度）优先搜索，完成剩下空格拿帆。

二、例程：

#include <windows.h>

#include <stdio.h>

#include <悉裤time.h>

 

char sd[81]

bool isok = false

 

//显示数独

void show()

{

 if (isok) puts("求解完成")

 else puts("初始化完成")

 

 for (int i = 0 i < 81 i++)

 {

  putchar(sd[i] + '0')

  if ((i + 1) % 9 == 0) putchar('\n')

 }

 putchar('\n')

}

 

//读取数独

bool Init()

{

 FILE *fp = fopen("in.txt", "rb")

 if (fp == NULL) return false

 fread(sd, 81, 1, fp)

 fclose(fp)

 for (int i = 0 i < 消陆雹81 i++)

 {

  if (sd[i] >= '1' && sd[i] <= '9') sd[i] -= '0'

  else sd[i] = 0

 }

 show()

 return true

}

 

//递归解决数独

void force(int k)

{

 if (isok) return

 if (!sd[k])

 {

  for (int m = 1 m <= 9 m++)

  {

   bool mm = true

   for (int n = 0 n < 9 n++)

   {

    if ((m == sd[k/27*27+(k%9/3)*3+n+n/3*6]) || (m == sd[9*n+k%9]) || (m == sd[k/9*9+n]))

    {

     mm = false

     break

    }

   }

   if (mm)

   {

    sd[k] = m

    if (k == 80)

    {

     isok = true

     show()

     return

    }

    force(k + 1)

   }

  }

  sd[k] = 0

 }

 else

 {

  if (k == 80)

  {

   isok = true

   show()

   return

  }

  force(k + 1)

 }

}

 

int main()

{

 system("CLS")

 if (Init())

 {

  double start = clock()

  force(0)

  printf("耗时%.0fms", clock() - start)

 }

 else puts("初始化错误")

 getchar()

}

在上海乘坐地铁的朋友都知道 上海地铁站免费赠阅的时代报上 经常会刊登有数独这个益智游戏 如果用纸和笔人工去算的话 恐怕你要花上老半天功夫了 有时候还不一定能解出来 心中一定很郁闷吧？网上也有一些数独游核亮埋戏的求解计算器 不过我想与其直接拿来主义 还不如自己研究编一个呢！所以 花了大概有一个多月的时间来编写了这样一个数独求解软件 由于不是利用所谓的穷举算法 所以如果数独游戏非唯一解的话 它就只提供最先找到的那个解 不过 请放心 肯定是正确的！下面我就来详述一下这个算法的精要

定义一个类 代表数独游戏中的每一个数 它有如下属性          #region 属性        /// <summary>        /// 数值        /// </summary>        public int Num        {            set            {                if (UnFilled)                {                    _num = value                    _unfilled = false                    Choices Clear()                    SetNumEvent(this)                }            }            get { return _num}        }        /// <summary>        /// 行坐标        /// </summary>        public int Xpos        {            set { _x = value}            get { return _x}        }        /// <summary>        /// 列坐标        /// </summary>        public int Ypos        {            set { _y = value}            get { return _y}        }        /// <summary>        /// 是否已填充的标记        /// </summary>        public bool UnFilled        {            get { return _unfilled}        }        /// <summary>        /// 候选数列表        /// </summary>        public List<int>Choices        {            set { _choices = value}            get { return _choices}        }        #endregion

在求解的主类里 根据游戏的规则 设计这样一套算法 当某一个数值被设定以后 与它同行或同列的以及在同一个九宫里的数的候选数列里都要去掉这个数本身 数独游戏中出现的数为已知数 需要我们填补的则是未知数 未知数需要我们去试解 不过在试解之前先要备份初始化以后的数组矩阵 以备在前一次试解失败以后进行恢复再进行下一次试解 直到试解成功为止

算法本身看上去不是太复杂 但是涉及到一个遍历和回滚的问题 所以 在编程的改蚂时候还是要注意一下的

下面我就来简单介绍一下这个数独求解软件的 *** 作和使用方法

软件总体来说还是 *** 作比较简单的 但是由于当时编写的时候只是想给自己用的 所以并没有设计菜单和帮助文档 用户在输入初始数据的时候可以用上下左右方向键或者ASDF来进行跳格 如果数错了 在按确定按钮以前可以按Back Space或Delete键进行修改 一旦按了确定按钮 就只得按F 清空后重新输入了

软件下载地址

源码下载地址键耐

lishixinzhi/Article/program/net/201311/13980

---