最近想学学算法，无意中从书中看到对一些小游戏的分析和算法实现，其实也是蛮有意思的。
今天我们来讲一讲数独。
首先我们来简单介绍下数独的规则。
数独
标准的数独是一个由99个1-9数字组成的矩阵，其中矩阵中的数字需满足：
1）每个数字所在的每一行、每一列的数字都不能重复。
2）每个数字所在的33矩阵的数字都不能重复。
3）所填的数字范围需为1-9的整数
以下图片来源：http://sudoku.baike.com/article-75231.html
数独谜面
数独谜底
数独的规则并不复杂，从算法实现的角度，我们可以从两个角度思考数独的实现：
一、数独的谜面生成；
二、给定数独谜面的破解
本篇文章讨论角度一，即谜面的生成，后续将会继续讨论数独引发的相关角度思考。
接下来我们来讨论如何生成数独谜面。
我们可以知道，数独矩阵可以看成是3*3个小的以9个数字为单位的小矩阵组成的矩阵，同一个小矩阵数字不重复。倘若我们将小矩阵的每一行或者每一列作为一个单位，该单位所在的行或者列其实可以看成小矩阵其他行或者列的排列组合。
如下图所示：
数独分解示意.png
当然这是一种不算太严谨的方法，数独中其实并没有以小矩阵行或列为单位（3个数字为一单位）的单位内的数字必须固定的限制，因此我们这种生成数独的方法其实只有9！种生成数独谜面的可能。
这种生成数独的方法不能生成所有可能的数独谜面，但是生成的数独谜面是满足数独规则的，后续我们将会探讨其他生成数独的方法。
基于数独的规则以及我们发现的规律，我们可以用以下方式生成数独。
1）随机生成一个3*3的数字矩阵，以该矩阵作为中心矩阵
2）以中心矩阵的行为单位，交换行，要求每一行9个数字满足不重复规则，生成中心矩阵的左右两个3*3矩阵
3）以中心矩阵的列为单位，交换列，要求每一列9个数字满足不重复规则，生成中心矩阵的上下两个3*3矩阵
4）以步骤 3）生成的矩阵为依据，继续以行为单位，交换行，生成剩下的矩阵
以下为算法思路示例图:
数独生成1.png
数独生成2.png
数独生成3.png
数独生成4.png
代码实现：
https://github.com/Belingda/SudokuHtmlGame/blob/master/RealNum.py
写了一个简易的数独游戏：
http://belindayang.com.cn:5000/
后续会继续更新
网友评论