玩了把比较简单阶段的数独，截个图留个纪念吧
九宫格数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次
那么如何写一个关于数独游戏的程序呢？以下的内容来自《编程之美》
关键的问题是：
使用什么样子的数据结构来存储数独游戏中的各种元素？
如何的生成一个初始的局面？
(1)数据结构定义
把每一个小的格子抽象成一个对象，记录格子所在的行号和列号，取值,以及该格子所对应的取值的范围(用于深度优先搜索)
#define SIZE 9
class Cell
{
public:
ArrayList GetValidValueList();//获得当前的格合法的取值范围
void PickNextValidValue();//获得下一个可能的取值，保存在value中
void Clear();
private:
int x;//行号
int y;//列号
int value;//取值
ArrayList ValidList;//该格子所对应的可能的取值的范围(用于回溯)
ArrayListIterator currentValueIter;//表示当前的取值在ValidList中的位置,用于取下一个的值
bool IsProcessed;//表示是否是回溯到该格(true)，还是第一次进行相应的处理(false)
};
整个棋盘表示为Cell m_cells[SIZE][SIZE];
(2)生成初始界面算法
(A)深度优先遍历
首先生成一个完整和合法的解，然后随机的去掉格中的一些数字。
从(0,0)开始，对于每一个没有处理的格子，首先调用GetValidValueList(),来获取当前的格子的可能的取值的范围，并从中选取一个作为当前的格子的值，接着搜索下一个格子。在搜索的过程中，如果出现某一个格子没有可行的值，则回溯，修改前一个格子的取值。直到所有的格子都能找到相应的可行解。
bool GenerateValidMatrix()
{
Coord coCurrent;//当前的处理的对象
coCurrent.x = 0;
coCurrent.y = 0;
while(true)
{
Cell c = m_cells[coCurrent.x,coCurrent.y];
c.x = coCurrent.x;
c.y = coCurrent.y;
ArrayList al;
if(!c.IsProcessed)
{
c.GetValidValueList();
}
if(c.ValidList.Count > 0)//合法的取值的范围大于0
{
c.PickNextValidValue();//在ValidList中选择一个可能的取值
if(c.x == SIZE - 1 && c.y == SIZE - 1)
{
break;//生成完毕
}
else
{
coCurrent = NextCoord(coCurrent);//向前搜索，处理下一个结点
}
}
else//当前的格子中不存在合法的取值
{
if(c.x == 0 && c.y == 0)
{
return false;
}
else
{
c.Clear();//清空当前格子中的ValidList将IsProcessed设置成false
coCurrent = PreCoord(coCurrent);//回溯处理前一个格子
}
}
}
reuturn true;
}
(B)置换法
先随机生成一个宫(9个格)，通过置换行、置换列的方法实现，但是生成的数独不完全，只能生成9！个合法的数独。
阅读(3162) | 评论(1) | 转发(0) |
