正文

数独程序(sudoku boy 2)设计报告2008-05-07 01:52:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/34871.html

分享到:

因为一些原因,又把原来写过的数独程序重新翻出来改写。有朋友说原来的就写得不错了,还要改,我改的目的主要是想实践一下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;
}

下一步,进行电算推导。

阅读(7738) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册