Click here to Skip to main content
13,092,725 members (72,547 online)
Click here to Skip to main content


59 bookmarked
Posted 19 Jun 2006

A Sudoku Teacher Using Boost Libraries

, 7 Jul 2006
A Sudoku teacher using multi_index_container, lambda, and other Boost libraries.
// CellCollection.h
// Copyright 2006 Scott A. Ross
// You are hereby granted permission to use this software for non-commercial use.
// This software is provided "as is" with no expressed
// or implied warranty.  I accept no responsibility or liability for any
// damage or loss of business that this software may cause.

#include <vector>

#include "SudokuElement.h"
#include "SBlock.h"
#include "PileAndChain.h"
#include "PointingPairs.h"

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp> 
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/assign/std/vector.hpp> // for 'operator+=()'
#include <boost/array.hpp>

class CellCollection

	enum SudokuCollectionType
		sct_Row = 0,
		sct_Col = 1,
		sct_Square = 2

	// Methods indicating state
	bool Complete() const;	// all cells have been filled in
	int NumAnswers() const;	// number of cells which have been determined

	// Methods related to setting/getting the answer for a cell (if one has been determined)
	int GetAnswer(int sqNum) const;
	bool SetAnswer(int sqNum, int answer, std::string sReason);
	void ClearAnswer(int sqNum);

	void GetReasons(int sqNum, std::vector<std::string>& reasons) const;

	// methods for maintaining the dynamic bitset indicating which digits are still possible for
	// a given cell
	// returns 0 and a list of possibilities or returns a digit if the square is already solved
	bool IsDigitPossible(int sqNum, int digit) const;
	int GetPossibilities(int squareNum, std::vector<int>& Possibilities) const;
	int RemoveTakenDigits(SudokuCell* pElm, boost::dynamic_bitset<>* pUsedDigits, std::string* sReason);
	int GetPossibilitiesString(int squareNum, std::string& strPos) const;

	// We use a multi_index_container so we can access the cells as rows, columns or blocks
	typedef boost::multi_index::multi_index_container<
		// 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;

	squares_set& Grid() { return Squares; };

	// Get a row, column or block
    void GetRow(int rowNum, boost::array<SudokuCell*, 9> &rowVec) const;
    void GetCol(int colNum, boost::array<SudokuCell*, 9> &colVec) const;
    void GetBlock(int blockNum, boost::array<SudokuCell*, 9> &blockVec) const;

	void TakeSnapshot();
	bool CellChanged() const;
	void GetChangedCells(std::vector<int> &vChangedCells) const;
	int  GetChangedCellCount() const;
	void SaveState();
	void RestoreState();
	bool GotContradictions() const;
	void SetTautologies(std::string &sText) const;
	void SetAsideAnswer();

	// indexes
	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;

	squares_set Squares;
	squares_set::iterator sqIter;



By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Scott A. Ross
Web Developer
United States United States
I live in Minnesota with my wife and son, having moved here from Montana. I enjoy creating software which benefits people, and I am fortunate to have a job where I am able to do that.
I enjoy reading, hunting and fishing, any sport with a racquet or paddle, and rooting for the New England Patriots.
In addition to my full-time job, I founded Rohawk, LLC which creates software for Christian churches.

You may also be interested in...

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170813.1 | Last Updated 7 Jul 2006
Article Copyright 2006 by Scott A. Ross
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid