因为一些原因，又把原来写过的数独程序重新翻出来改写。有朋友说原来的就写得不错了，还要改，我改的目的主要是想实践一下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........
但是有的人做的数独软件就不是这样，比如
400030000
000600800
000000001
000050090
080000600
070200000
000102700
503000040
900000000
那就不好了，你又要重载一个，这样做就相当于，为你的软件增添了‘规则’，而规则越多，越使接口复杂化。解决方法，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;
}
下一步，进行电算推导。
评论