数独 算法 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()

}

1、开心数独

开心数独是趣味数学谜题游戏小程序，是一个很有挑战意义的小程序，且其界面整洁，清晰明了，给人以舒适感，很值得推荐。 开心数独小程序是一个比较容易学会的游戏，首先系统会给出一面数字墙，里面排满密密麻麻的数字，但是这些数字里面有些空格是欠缺的；

玩家需要根据需求把所有的空格填满，且每行每列里面的数字1-9都不可以重复，非常考验大家的观察能力与耐心。 开心数独，一个如此有趣的小程序，你还在犹豫什么？赶紧来挑战吧！

2、千帆数独

千帆数独是数独推理益智游戏，是一个趣味十足的游戏，且其界面整洁，清晰明了，给人以舒适感，很值得大家玩。 千帆数独小程序，数独九宫格，多种难度挑战，它的玩法也不复杂，首先系统会给出一面数字墙，里面排满密密麻麻的数字；

但是这些数字里面有些空格是欠缺数字的，玩家需要把所有的空格填满数字，且每行每列里面的数字1-9都不可以重复。 千帆数独，一个如此有趣又有挑战的小程序，赶紧来挑战吧！看一下自己能挑战到哪里！

3、益智之数独

这是一个有趣的数学游戏，多玩数独游戏是对我们思维的提升很有帮助哦。那么不妨一起来玩玩益智之数独小程序，这是一个很好玩的小程序哦 益智之数独小程序的玩法很简单，首先系统会给出一面数字墙，里面排满密密麻麻的数字；

但是每行每列都有数字欠缺，玩家需要根据需求把所有的空格填满，且每行每列里面的数字1-9都不可以重复，这是很考验能力的游戏哦。 益智之数独，一个很具有挑战性的小程序。

4、Magic Sudoku 的 AR 应用的 *** 作视频，用户使用这款应用可以秒解数独游戏。虽然只能用在完全空白的数独题目上，但应用本身却很好的展示了苹果三个技术框架结合后的无限潜力。

Magic Sudoku 使用苹果的图像分析软件 Vision 来读取题目，然后利用 CoreML 框架计算出答案，最后通过 ARKit 将解决方案呈现在真实的题纸上。

5、微软数独（Microsoft Sudoku）今天正式在苹果App Store上架。这款游戏于去年12月开启Soft Launch，并仅在部分国家和地区上线。今天发布的v1.2.02130更新，终于面向所有用户开放了这款益智类游戏。

单向扫看法:在第一个例子中,我们注意看一下第2宫。

我们知道,每个宫内必须包含数字9,第1宫以及第3宫中都包含数字9,并且第1宫的9位于第3行。

第3宫的9位于第2行，这也就意味着第2宫的9不能在第2行和第3行，所有第2宫的9只能放置在第2宫第1行的空格内。

2.双向扫看法:同样的技巧也可以扩展到相互垂直的行与列中。让我们想一下第3宫中1应该放在哪里。在这个例子中,第1行以及第2行已经有1了,那么第3宫中只有底部的俩个空格可以填1。不过，方格g4已经有1了，所有第g列不能再有1。

所以i3是该宫唯一符合条件填上数字1的地方。

3.寻找候选法:通常地,一个方格只能有一个数字的可能性,因为剩下的其他8个数字都已经被相关的行列宫所排除了。我们看一下下面例子中b4这个方格。b4所在的宫中已经存在了数字3，4，7，8，1和6位于同一行，5和9位于同一列，排除上述所有数字，b4只能填上2。

4数字排除法：排除法是一个相对繁杂的寻找数字的方法。我们可以从c8中的1间接推出e7和e9必须包含数字1，不管这个1在哪个方格，我们可以确认的是，第e列的数字1肯定在第8宫内，所以第2宫内中间这一列就不可能存在数字1。因此，第2宫的数字一必须填在d2处。

---