数独基本完成

数独小程序实在半个月前突发奇想开发写的,直到昨天才基本完成,编码时间大概就只有10几个小时,中间一直都偷懒没有弄。

说到数独,自己的算法就是深度优先搜索+每个坐标先取可能解,通过这些可能解组成一个树,然后进行回溯/剪枝,最后得出数独解,也即生成一个数独,然后通过困难级数对这个解进行挖坑,抹去某些坐标的数字,显示给用户。其中的核心数据结构就是树节点:

typedef struct tree_struct {
    // 该节点的值
    int data;
    // 子节点的数量
    int child_count;
    // 该节点的x轴
    int x;
    // 该节点的y轴
    int y;
    // 该节点在父级子节点中的位置
    int position;
    // 该节点的父节点
    struct tree_struct *parent;
    // 该节点的子节点数组
    struct tree_struct *childs[9];
} tree_node;

算法上大体如此,不过不满意的地方就是存放数独解使用了一个全局变量int SUDOKU[9][9],后续优化方案是改成一个结构体来存放,这样如果要生成多个数独,也不会捉襟见肘了。

在这个前面编码的基础上,昨天抽时间又写了一个PHP扩展,可以直接生成数独数据返回一个PHP的二维数组,也算是对PHP扩展进行了一个基本的熟悉,不过说起来感觉挺难用的,ZEND_API不够友好。。

下面的工作就是抽时间在扩展的基础上,做一个webgame数独出来,其中要用到HTML5。所以又要占用PTMPHP的一部分时间了,唉,最近一直在挖坑,一个一个填吧。

blog comments powered by Disqus