65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 Boost 库的数独教师

Scott A. Ross
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.73/5 (26投票s)

2006 年 6 月 19 日

7分钟阅读

viewsIcon

72970

downloadIcon

1934

一个使用 multi_index_container、lambda 和其他 Boost 库的数独老师。

Sample Image

引言

到目前为止，数独已无需介绍。这种令人上瘾的数字谜题每天都会出现在六大洲的报纸上（南极洲怎么了？？？），并催生了杂志、书籍、电子游戏、网站以及 CodeProject 上的一些优秀提交。我（首次）提交的目标有两个。首先，创建软件来帮助我的妻子和儿子以一种能让他们成为更好的谜题解决者的方式解决一些棘手的数独。其次，展示一些 CodeProject 读者可能以前没有使用过的 Boost 库。

解决数独

解决数独谜题的方法有很多种，但它们分为两类：计算机可能解决它们的方式，以及人类可能解决它们的方式。对于计算机，有一篇关于使用 Dancing Links 算法解决数独的优秀的 CodeProject 文章。为了我的目的，我需要计算机像人类一样解决谜题。我的算法主要参考资料可以在“致谢”部分找到。

安装 Boost

我使用了 Boost 库版本 1.33.1 进行开发。我遵循了 Boost 网站上提供的说明，只有一个例外。下载 Boost 源代码后，我下载了一个预构建的 bjam，这是一个错误。我无法构建 Boost 库。但是，一旦我从已经下载的源代码中构建了 bjam，构建过程就顺利进行了。

使用 Boost::Multi_Index_Container

数独谜题是一个 9x9 的单元格网格。要解决谜题，你需要将这些单元格视为一行、一列和一个 3x3 的单元格块。为了实现这一点，我使用了 boost::multi_index_container。

首先，我有一个表示 81 个单元格之一的类。请注意，当单元格创建时，会向其传递其编号。它使用该编号计算其行、列和块编号。

class SudokuCell
{
public:
    SudokuCell(int cellNo) :
        _cellNum(cellNo)
        , _row(cellNo/9)
        , _col(cellNo%9)
        , _block((cellNo/27)*3 + (cellNo%9)/3)
        , _answer(0)
.
.
.
    int GetNumber() const { return _cellNum; };
    int GetRow() const { return _row; };
    int GetCol() const { return _col; };
    int GetBlock() const { return _block; };

private:
    int _cellNum;
    int _row;
    int _col;
    int _block;
.
.
.

};

然后我有一个名为 CellCollection 的类，其中包含一个 boost::multi_index_container。我为我想访问单元格的四种方式（按单元格编号、按行、按列或按块）中的每一种都设置了一个索引。

class CellCollection
{
public:
    CellCollection(); 
    ~CellCollection();
.
.
.
    // We use a multi_index_container so we can

    // access the cells as rows, columns or blocks

    typedef boost::multi_index::multi_index_container<
        SudokuCell*,
        boost::multi_index::indexed_by<
        // sort by cell number - 0

        boost::multi_index::ordered_unique<
           boost::multi_index::const_mem_fun<SudokuCell,
           int,&SudokuCell::GetNumber> >,
        // sort by row - 1

        boost::multi_index::ordered_non_unique<
           boost::multi_index::const_mem_fun<SudokuCell,
           int,&SudokuCell::GetRow> >,
        // sort by column - 2

        boost::multi_index::ordered_non_unique<
           boost::multi_index::const_mem_fun<SudokuCell,
           int,&SudokuCell::GetCol> >,
        // sort by block - 3

        boost::multi_index::ordered_non_unique<
           boost::multi_index::const_mem_fun<SudokuCell,
           int,&SudokuCell::GetBlock> >
        > 
    > squares_set;

    // Get a row, column or block

    // Get a row, column or block

    void GetRow(int rowNum, boost::array<SudokuCell*, 9> &rowVec);
    void GetCol(int colNum, boost::array<SudokuCell*, 9> &colVec);
    void GetBlock(int blockNum, 
                  boost::array<SudokuCell*, 9> &blockVec);

private:
    // indices

    squares_set::nth_index<0>::type& sort_by_number;
    squares_set::nth_index<1>::type& sort_by_row;
    squares_set::nth_index<2>::type& sort_by_col;
    squares_set::nth_index<3>::type& sort_by_block;
.
.
.
};

请注意，获取单元格编号的索引是唯一的，因为每个单元格都有自己的编号。而行/列/块访问的索引是非唯一的，因为每个给定子集中有 9 个单元格。这些索引在构造函数中初始化。

CellCollection::CellCollection() :
    sort_by_number(Squares.get<0>())
    , sort_by_row(Squares.get<1>())
    , sort_by_col(Squares.get<2>())
    , sort_by_block(Squares.get<3>())
{
    for (int i=0; i<81; ++i)
        Squares.insert_(new SudokuCell(i));
}

现在我们的索引已设置好，获取一行、一列或一个块就很容易了。我们只需选择我们的索引，选择一个下限（我们想要的行/列/块编号），然后选择前 9 个。

void CellCollection::GetRow(int rowNum, 
                     boost::array<SudokuCell*, 9> &rowVec)
{
    squares_set::nth_index_iterator<1>::type it1= 
                     sort_by_row.lower_bound(rowNum);
    for (int j=0; j<9; ++j)
        rowVec[j] = *it1++;
}

void CellCollection::GetCol(int colNum, 
     boost::array<SudokuCell*, 9> &colVec)
{
    squares_set::nth_index_iterator<2>::type it1= 
                     sort_by_col.lower_bound(colNum);
    for (int j=0; j<9; ++j)
        colVec[j] = *it1++;
}

void CellCollection::GetBlock(int blockNum, 
     boost::array<SudokuCell*, 9> &blockVec)
{
    squares_set::nth_index_iterator<3>::type it1= 
             sort_by_block.lower_bound(blockNum);
    for (int j=0; j<9; ++j)
        blockVec[j] = *it1++;
}

使用 Boost::Lambda 和 Boost::Lambda::Bind

Boost::lambda 和 boost::lambda::bind 使迭代容器以执行函数变得容易。例如，要获取包含确定答案的单元格数量，我们有一个辅助函数

int CountSuccessfulAnswer(SudokuCell* pElm)
{
    return ((pElm->Answer() != 0) ? 1 : 0);
}

和方法

int CellCollection::NumAnswers()
{
    int numAnswers = 0;
    for_each(Squares.begin(), Squares.end(), numAnswers += 
        boost::lambda::bind(CountSuccessfulAnswer, boost::lambda::_1));
    return numAnswers;
}

每个单元格都知道如何为自己拍摄快照，以便在运行算法后，它可以报告它是否已更改。我使用它来确定某个步骤是否已完成。

void CellCollection::TakeSnapshot()
{
    for_each(Squares.begin(), Squares.end(),  
        boost::lambda::bind(&SudokuCell::TakeSnapshot, 
                            boost::lambda::_1));
}

// cell changed from the last snapshot

// (number of possible digits changed

//  for at least 1 cell

bool CellCollection::CellChanged()
{
    bool cellChanged = false;
    for_each(Squares.begin(), Squares.end(), cellChanged |=  
        boost::lambda::bind(&SudokuCell::Changed, 
                            boost::lambda::_1));
    return cellChanged;
}

最基本的算法是从组（行、列或块）中的其他单元格中消除已经使用的数字。Boost::lambda 和 boost::lambda::bind 有助于保持代码简洁

int Sudoku::ClearUsedDigits(boost::array<SudokuCell*, 9> & group, 
                            std::string& sReason)
{
    int cellsCleared = 0;
    boost::dynamic_bitset<> usedDigits(10);

    // Find the digits which have been

    // taken (are already used) in this group

    for_each(group.begin(), group.end(), 
        boost::lambda::bind(MarkTakenDigits, 
                   boost::lambda::_1, &usedDigits));

    // Set those bits for each element in our group

    for_each(group.begin(), group.end(), cellsCleared += 
        boost::lambda::bind(&Sudoku::RemoveTakenDigits, 
          this, boost::lambda::_1, &usedDigits, &sReason));

    return cellsCleared;
}

我还使用 boost::dynamic_bitset 来跟踪可能的数字，但我也可以很容易地使用 std::bitset，因为大小是已知的并且不会改变。我使用 boost::assign 是因为我觉得用 += 向向量添加元素很酷。但我没有利用该库以单个逗号分隔语句添加多个元素的功能。

使用的算法

该程序使用以下算法

  • 简单 – 从同一行、列或块中消除已经使用的数字。
  • 孤岛 – 如果一个数字在一行、列或块中仅限于一个单元格，则该单元格必须包含该数字。
  • 堆排除 – 如果一组 N 个数字在 N 个单元格中是可能的，则所有其他数字可以从这 N 个方块中删除。
  • 链式排除 – 如果 N 个单元格只能包含 N 个数字，则这 N 个数字仅限于这 N 个单元格。它们可以从其他单元格中删除。
  • 箱线缩减 - 如果一行或一列中的数字被限制在一个块中，则该数字可以从该块中的其他行/列中消除。
  • 指向对 – 此算法作用于 3x3 块。如果在给定块中，给定数字的唯一可能位置仅限于单行或单列，则该数字不能出现在相邻块的该列中。具有此特征的两个块会将相邻块的该数字限制为一行或一列。
  • 矛盾推论 – 除非其他算法未能产生结果，否则此算法不会运行。对于只有两个可能数字的单元格，其中一个被选作猜测，然后运行算法以查看猜测的含义。如果任何一个猜测导致矛盾（一个有 0 个可能数字的单元格），我们知道另一个选项是正确的。如果两个猜测都没有产生矛盾，但在两种情况下都导致其他单元格产生相同的答案，则该答案必须是正确的。

使用程序

谜题可以通过三种方式输入

  • 在“文件->输入谜题”菜单项的括号内输入它们，以便程序知道您何时完成。
  • 打开一个数独文件。支持大多数格式。
  • 将数独文件拖放到主窗口上。

输入谜题后，程序将执行最简单的算法（消除已包含在同一行/列/块中的数字），并识别（用可爱的豌豆汤绿色）哪些方块是立即可解的。对于任何方块，您可以

  • 输入猜测。
  • 右键单击并查看该单元格的历史记录。这显示了每次可能的数字进一步减少时运行的算法。
  • 右键单击并显示该单元格的答案（如果答案已确定）。

有两种运行模式，它们对于学习解决数独谜题很有用。

  1. 单步模式
    • 输入一个谜题。
    • 按下按钮显示每个单元格的可能数字。
    • 按下“单步”按钮。每次按下它时，程序都会运行基于行、列或块的算法，直到某个单元格发生变化（其可能的数字发生变化）。然后您可以看到什么发生了变化以及为什么。
  2. 答案步进模式
    • 输入一个谜题。
    • 按下“解决单元格步进”按钮。程序将运行，直到至少一个单元格被推断出来。该单元格将被突出显示。您现在知道该单元格可以通过逻辑推断出来。

Using the Code

训练逻辑在 Engine 子目录中。谜题通过调用 SetAnswer 定义。通过此调用进行单步或直到发现单元格的步进

bool TakeStep(std::vector<int> &changedCells, 
              bool bStepUntilAnswer = false);

可以通过这些调用检索单元格信息

int GetAnswer(int sqNum) const;
bool IsDigitPossible(int sqNum, int digit) const;
int GetPossibilities(int squareNum, std::vector<int>& Possibilities) const;
void GetReasons(int sqNum, std::vector<std::string>& reasons) const;

致谢

我在获取一些更高级的数独解决算法方面的更多知识时使用了以下资源

特点

  • 我从未研究过图论，但鉴于 Dr. Dobbs 文章的标题，我怀疑 boost::graph 对这个程序会非常有用。
  • 本文是关于 GUI 背后的数独求解引擎。GUI 本身是一个快速而简单的 MFC 对话框应用程序。我可能会开发一个更现代的界面。
  • 人们还使用其他数独求解算法，我仍然可以添加。
  • 我可能会在 STUBL 中添加一个生成器。

历史

  • 06-19-06 - 首次提交。
  • 06-28-06 - 错误修复。更改按钮位置以反映最常见用法。
© . All rights reserved.