感觉解数独的算法好复杂啊

Bruce

前言：在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; //表示当前格子被标注的数字，解答高难度数独时起到辅助解答的作用

//可能还需要其他成员、方法来辅助解答

}

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

a-wing

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

小埋社区

感觉解数独的算法好复杂啊