因为一些原因，又把原来写过的数独程序重新翻出来改写。有朋友说原来的就写得不错了，还要改，我改的目的主要是想实践一下C++，尤其是设计方面。 1 面向对象吗？ 不知道原来的程序算不算面向对象，一个类，比如class sudoku，有构造函数，求解函数，显示函数，等等，但是总是觉得有些乱，一但有了新的需求，整个代码就看起来像盘散沙。 经过这次的实践，我总结出来的规律是，一个类的设计，要使接口最小化，就是说接口集最小，接口数目最少，为了做到这一点，对类本身就要求，只完成功能上最小单位的部分，一个类，要么封装一些数据（容器），要么封装一个数据（元素），要么做一件事情（功能），容器类，只要设计元素的访问方法，元素类只要一个最小数据结构本身（不包括帮助函数算法的辅助数据结构），数据结构的算法留给专门的类设计（功能）。如何融合它们，数据+算法，干净的数据+干净的算法，用帮助函数，别小看写在类外面的帮助函数，有时候它们比成员函数好用得多，成员函数要么设计得好，要么就是累赘。而帮助函数可以看成是粘合剂，把用户的使用和数据＋算法很好的接合起来，同时，又容易改写。还有，容器的设计包含迭代器的设计，这可以为算法更好的抽象出来，算法面向迭代器，迭代器组织数据关系。算法的设计体现在，用仿函数做嵌入式，比如sudoku的构造函数，你可以写这样一个初始化函数： sudoku::init(char* str){...} 实现的时候，就会问，用什么样的格式初始化呢？这样吧： 4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........ 但是有的人做的数独软件就不是这样，比如 400030000000600800000000001000050090080000600070200000000102700503000040900000000 那就不好了，你又要重载一个，这样做就相当于，为你的软件增添了‘规则’，而规则越多，越使接口复杂化。解决方法，1，可以是为专门的数据写适配器，把自己的数据定为标准；2，将这件事情，移给高层解决，用仿函数在外面完成。像下面这样： class init_functor{public: template<std::size_t dim> void operator()(sudoku<dim> &s, char *str) { typedef typename sudoku<dim>::iterator iterator; typedef typename sudoku<dim>::const_iterator const_iterator; const_iterator it_end = s.end(); for(iterator it=s.begin();it!=it_end;++it,++str) { if(*str == '.') it->value = 0; else it->value = *str - '0'; } }}; sudoku<3> s; display_functor display; init_functor init; init(s,"4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........"); display(s); resolve(s,any,display); 这样可以更灵活，不同的数据形式，不过是不同的仿函数罢了。 2，类结构 主要分这么几个类： sudoku_cell 数独里一个格子里表达的数据类型，它包括一个value字段（格子里填好的数），一个candidate[]数组（候选数表），一个cnt_cand值（候选数个数）。它是一个简单的struct； sudoku_matrix 整个数独容器，只提供元素访问方式和迭代器接口，特殊一点的包括行迭代器begin_row()，列迭代器begin_column()和宫迭代器begin_block()。 sudoku_iterator迭代器，*后就是sudoku_cell类型，除了基本的操作外，特殊一点的包括类似的行、列和宫开始迭代器。 sudoku_resolver数独求解器，关联一个sudoku_matrix的引用，对每一个求出的解调用外面传进来的仿函数。求解模式有四种，all全部解，any找到一个就停止，only找到二个就停止，roll_back是否滚回模式，滚回模式就是指解完后滚回到一开始求解的状态，而不是已经填好的状态。它们是可以相加的模式，其中roll_back只对any和only有作用，all自然是滚回的。 sudoku_generator数独生成器，关联一个sudoku_matrix的引用，对每一个生成的数独调用外面传进来的仿函数。目前是在sudoku_resolver之上实现的。 一个测试程序如下： #include <cstdlib>#include <iostream>#include "sudoku" using namespace std; class display_functor{public: template<std::size_t dim> void operator()(sudoku<dim> &s) { typedef typename sudoku<dim>::iterator iterator; typedef typename sudoku<dim>::const_iterator const_iterator; static int cnt = 0; static const std::size_t dim2 = dim*dim; cout<<"No."<<(++cnt)<<endl; const_iterator it_end = s.end(); for(int row=0;row<dim2;++row) { for(iterator it=s.begin_row(row);it!=it_end;++it) { if(0 == it->value) { cout<<"."; } else { cout<<it->value; } } cout<<endl; } }}; class init_functor{public: template<std::size_t dim> void operator()(sudoku<dim> &s, char *str) { typedef typename sudoku<dim>::iterator iterator; typedef typename sudoku<dim>::const_iterator const_iterator; const_iterator it_end = s.end(); for(iterator it=s.begin();it!=it_end;++it,++str) { if(*str == '.') it->value = 0; else it->value = *str - '0'; } }}; int main(int argc, char *argv[]){ sudoku<3> s; display_functor display; init_functor init; init(s,"4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........"); display(s); resolve(s,any,display); generate_seed(s,70); // 随机生成一个具有70个已填数的数独,作为种子 generate_child(s,60,all,display); // 连续生成由s挖去一定格子,60个已填数的全部数独,对每个数独调用display if(is_only(s)) // 判断解是否唯一 { cout<<"是经典唯一数独"<<endl; } resolve(s,any,display); // 求解s的任一个解 system("PAUSE"); return EXIT_SUCCESS;} 下一步，进行电算推导。
评论