A Sudoku Teacher Using Boost Libraries

• Download STUBL source - 36.1 Kb
• Download STUBL demo project - 212 Kb

Introduction

By now, Sudoku does not need any introduction. The addictive number puzzle appears daily in newspapers on six continents (what is up with the Antarctic???), and has spawned magazines, books, electronic games, web sites, and some excellent submissions on CodeProject. My goal for this (my first) submission was twofold. First, to create software which would help my wife and son get through some of the fiendish Sudokus in a way that would make them better puzzle solvers. Second, to show use of a couple of Boost libraries which some CodeProject readers may not have used before.

Solving Sudokus

There are a variety of ways to solve Sudoku puzzles, but they fall into two categories: the way a computer might solve them, and the way a human might solve them. For computers, there is an excellent CodeProject article on using the Dancing Links algorithm to solve Sudoku. For my purposes, I need the computer to solve the puzzle like a human. My primary references for algorithms can be found in the Acknowledgements section.

Installing Boost

I used Boost library version 1.33.1 for this development. I followed the instructions provided on the Boost web site, with one exception. After downloading the Boost source, I then downloaded a pre-built bjam, which was a mistake. I was unable to build the Boost libraries. However, once I built bjam from the source I had already downloaded, the build process went smoothly.

Using Boost::Multi_Index_Container

A Sudoku puzzle is a grid of 9x9 cells. To solve the puzzle, you need to look at the cells as a row, a column, and as a block of 3x3 cells. To achieve this, I used the boost::multi_index_container.

First, I have a class which represents one of the 81 cells. Note that when the cell is created, it is passed its number. It uses that to compute its row, column, and block number.

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;
.
.
.

};

I then have a class called CellCollection which contains a boost::multi_index_container. I have an index for each of the four ways I want to access the cells: by cell number, by row, by column, or by block.

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;
.
.
.
};

Note that the index for getting a cell number is unique since each cell has its own number. And the indices for row/column/block access are non-unique since there are 9 cells per given subset. The indices are initialized in the constructor:

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));
}

Now that our indices are set up, getting a row, column, or block is easy. We simply need to select our index, choose a lower bound (the row/column/block number we want), and choose the first 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++;
}

Using Boost::Lambda and Boost::Lambda::Bind

Boost::lambda and boost::lambda::bind make it easy to iterate through a container to perform functions. For example, to get the number of cells which hold a determined answer, we have a helper function:

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

and the method:

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

Each cell knows how to take a snapshot of itself so that after running an algorithm, it can report whether it has changed. I use this in determining whether a step has completed.

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;
}

The most fundamental algorithm is to eliminate digits which have already been used from the other cells in a group (row, column, or block). Boost::lambda and boost::lambda::bind help keep the code concise:

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;
}

I also use boost::dynamic_bitset to keep track of possible digits, but I could just as easily use std::bitset as the size is known and does not change. I use boost::assign because I think it’s cool to add an element to a vector using +=. But I don’t take advantage of that library’s ability to add multiple elements in a single comma-delimited statement.

Algorithms Used

This program makes use of the following algorithms:

• Simple – Eliminate already-used digits from the same row, column, or block.
• Island – If a digit is limited to one cell in a row, column, or block, the cell must contain that digit.
• Pile Exclusion – If a group of N digits are possible in N cells, all other digits can be removed from those N squares.
• Chain Exclusion – If N cells can contain only N digits, those N digits are limited to those N cells. They can be removed from other cells.
• Box Line Reduction - If a digit in a row or column is restricted to one block, that digit can be eliminated from other rows/columns in that block.
• Pointing Pairs – This algorithm works on 3x3 blocks. If, in a given block, the only possible locations for a given digit are confined to a single row or column, that digit can not appear in that column for either of the neighboring blocks. Two blocks with this characteristic will limit the neighboring block to one row or column for that digit.
• Contradiction of Tautology – This algorithm does not run unless other algorithms have failed to yield a result. For cells which have only two possible digits, one of them is chosen as a guess and the algorithms run to see the implications of the guess. If either of the guesses results in a contradiction (a cell which has 0 possible digits), we know the other option is correct. If neither guess produces a contradiction, but results in some other cell yielding the same answer in both cases, that answer must be correct.

Using the Program

Puzzles can be input in three ways:

• Type them in, bracketed with the File->Type In Puzzle menu item so the program knows when you are done.
• Open a Sudoku file. Most formats are supported.
• Drag and drop a Sudoku file onto the main window.

When a puzzle is input, the program will perform the simplest algorithm (eliminating digits which are already contained in the same row/column/block), and identify (in a lovely pea-soup green) which squares are immediately solvable. For any square, you can:

• Type in a guess.
• Right click and see the history of that cell. This shows you what algorithm ran each time the possible digits got further reduced.
• Right click and show the answer for that cell (if the answer has been determined).

There are two modes in which to run, which are useful for learning to solve Sudoku puzzles.

1. Single Step Mode
   • Enter a puzzle.
   • Press the button to display the possible digits for each cell.
   • Press the Single Step button. Each time you press it, the program will run through a row, column, or block-based algorithm until a cell has changed (its possible digits has changed). You can then see what changed and why.
2. Answer Step Mode
   • Enter a puzzle.
   • Press the Solve Cell Step button. The program will run until at least one cell has been deduced. That cell will be highlighted. You now know that the cell can be logically deduced.

Using the Code

The training logic is in the Engine subdirectory. The puzzle is defined by calls to SetAnswer. Single steps or steps until a cell is discovered are made with this call:

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

Cell information can be retrieved with these calls:

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;

Acknowledgements

I used the following resources in gaining more knowledge on some of the more advanced Sudoku solving algorithms:

• Sudoku & Graph Theory – Algorithms for building solvers - By Eytan Suchard, Raviv Yatom, and Eitan Shapir - Dr. Dobbs Portal, Dec. 15, 2005.
• An Index of Sudoku Strategies.
• How to modify a CEdit context menu by PJ Arends.

Futures

• I have never studied graph theory, but given the title of the Dr. Dobbs article, I suspect boost::graph would be very useful for this program.
• This article is concerning the Sudoku solving engine behind the GUI. The GUI itself is a quick and dirty MFC dialog application. I may work on a more modern interface.
• There are other algorithms people use to solve Sudoku which I could still add.
• I may add a generator to STUBL.

History

• 06-19-06 - Original submission.
• 06-28-06 - Bug fixes. Changed button positions to reflect most common usage.