• ACG

    前言:在Google Play上下载了一个数独小游戏,玩了几把之后开始思考怎么利用程序解数独。
    感觉用程序算法来实现还是挺复杂的。
    首先要把9*9的数独矩阵表示出来,需要在数独类中维护一个9*9的二维向量,每个九宫格用一个含有9个Cell实例的向量存放,并且提供一个优先级队列,用来存放数独的计算任务,以及提供一些进行操作的接口

    Class Sodoku
    {
    public:
        Sodoku(); //默认构造函数
        Sodoku(const Sodoku &sodoku); //根据给定的已经填充一部分的数独生成一个数独实例的构造函数
        ~Soduku(); //析构函数
    
    private:
        std::vector< std::vector<Cell> >; //用来存放数独的81个格子,不使用int表示是因为高难度数独中每个格子的状态难以确定,需要添加一些标注辅助解谜
        std::priority_queue<Cell>; //优先级队列,用来根据每个格子被解出的预期存放格子,并在解谜算法中进行遍历
    
    protected:
        void run(); //用来开启一个新线程,高难度数独解起来很慢,所以最好采取多线程的方式进行处理
        void deal(Cell c); //用来遍历优先级队列并更改格子状态的函数,解谜算法的重点
        void insert(Cell c, int n); //将数字插入格子的算法
        void mark(Cell c, int n); //对格子进行标注的算法,解答高难度数独时需要用到
        void remove_from_queue(Cell c); //当一个格子状态被确定后(即填入数字后),将格子从优先级队列中移除的算法
    
    //可能还有其他必需的成员函数或成员,用来辅助解答
    
    }
    

    表示单个格子的Cell类,至少需要存放这个格子填入的数字,这个格子的标注,以及这个格子的状态(是否被遍历等)

    Class Cell
    {
    public:
        Cell(); //默认构造函数
        Cell(int n); //根据数字直接构造出一个填好数字的单元格
        ~Cell(); //析构函数
    
    private:
        int digit; //表示填入这个格子的数字
        bool is_visit; //表示该格子是否已被遍历
        std::list<int> marks; //表示当前格子被标注的数字,解答高难度数独时起到辅助解答的作用
    
    //可能还需要其他成员、方法来辅助解答
    
    } 
    

    之后,剩下的就是利用排除法等解答数独的方法实现具体的接口了,不过我能力和时间有限,暂时就不写具体实现了
    总体来说,解答数独本身算法实现已经较难了,如果想高效实现,估计需要相当好的逻辑思维以及算法和数据结构知识


  • 算法解数独其实是个经典问题。。。