Click here to Skip to main content
12,622,291 members (35,394 online)
Click here to Skip to main content

Stats

53.3K views
1.7K downloads
59 bookmarked
Posted

A Sudoku Teacher Using Boost Libraries

, 7 Jul 2006
A Sudoku teacher using multi_index_container, lambda, and other Boost libraries.
// CellCollection.cpp
//
// Copyright 2006 Scott A. Ross
// thrownbybabe@yahoo.com
//
// 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 "stdafx.h"

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp> 
#include <vector>
#include <sstream>
#include "CellCollection.h"
#include "SudokuElement.h"
#include "SBlock.h"
#include "SudokuUtils.h"
#include <boost/assign/std/vector.hpp> // for 'operator+=()'
#include <boost/assign/std/vector.hpp> // for 'operator+=()'


using namespace std;
using namespace boost::assign; // bring 'operator+=()' into scope

//////////////////////////////////////
//////////////////////////////////////
//
// Helper functions for boost::lambda
// usage
//
//////////////////////////////////////
//////////////////////////////////////

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

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

void CollectChangedCells(SudokuCell* pElm, std::vector<int>* pvInts)
{
	if (pElm->Changed())
		pvInts->push_back(pElm->GetNumber());
}


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


CellCollection::~CellCollection()
{
	for (sqIter = Squares.begin(); sqIter != Squares.end(); ++sqIter)
		delete (*sqIter);
}


//////////////////////////////////////
//////////////////////////////////////
//
// Short Methods which use boost::lambda
// and boost::lambda::bind
//
//////////////////////////////////////
//////////////////////////////////////


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


bool CellCollection::Complete() const
{
	return (NumAnswers() == 81);
}


int CellCollection::GetAnswer(int sqNum) const
{
	squares_set::nth_index_iterator<0>::type it1= sort_by_number.lower_bound(sqNum);
	int answer = (*it1)->Answer();
    return answer;
};

bool CellCollection::SetAnswer(int sqNum, int answer, std::string sReason)
{
	squares_set::nth_index_iterator<0>::type it1= sort_by_number.lower_bound(sqNum);
	return (*it1)->SetAnswer(answer, sReason);
};

void CellCollection::ClearAnswer(int sqNum)
{
	squares_set::nth_index_iterator<0>::type it1= sort_by_number.lower_bound(sqNum);
	return (*it1)->ClearAnswer();
};

void CellCollection::GetReasons(int sqNum, std::vector<std::string>& reasons) const
{
	squares_set::nth_index_iterator<0>::type it1= sort_by_number.lower_bound(sqNum);
	(*it1)->GetReasons(reasons);
};

//////////////////////////////////////
//////////////////////////////////////
//
// Methods involving possible digits
// for a given cell
//
//////////////////////////////////////
//////////////////////////////////////

bool CellCollection::IsDigitPossible(int sqNum, int digit) const
{
	squares_set::nth_index_iterator<0>::type it1= sort_by_number.lower_bound(sqNum);

	return (*it1)->DigitIsPossible(digit);
}


int CellCollection::GetPossibilities(int squareNum, std::vector<int>& Possibilities) const
{
	squares_set::nth_index_iterator<0>::type it1= sort_by_number.lower_bound(squareNum);

	int answer = GetAnswer(squareNum);

	if (answer != 0)
		return answer;
	else
	{
		boost::dynamic_bitset<>* squarePossibleDigits;

		squarePossibleDigits = (*it1)->GetPossibleDigits();

		for (int digit=1; digit <=9; ++digit)
		{
			if ((*squarePossibleDigits)[digit])
				Possibilities += digit;
		}
		return 0;
	}
}

int CellCollection::GetPossibilitiesString(int squareNum, std::string& strPos) const
{
	squares_set::nth_index_iterator<0>::type it1= sort_by_number.lower_bound(squareNum);

	int answer = GetAnswer(squareNum);

	if (answer != 0)
		return answer;
	else
	{
		boost::dynamic_bitset<>* squarePossibleDigits;

		squarePossibleDigits = (*it1)->GetPossibleDigits();

		for (int digit=1; digit <=9; ++digit)
		{
			if ((*squarePossibleDigits)[digit])
				strPos += char('0' + digit);
			else
				strPos += ' ';
		}
		return 0;
	}
}



//////////////////////////////////////
//////////////////////////////////////
//
// Access our multi-index-container
// as a row, column or 3x3 block
//
//////////////////////////////////////
//////////////////////////////////////
    void CellCollection::GetRow(int rowNum, boost::array<SudokuCell*, 9> &rowVec) const
	{
		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) const
	{
		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) const
	{
		squares_set::nth_index_iterator<3>::type it1= sort_by_block.lower_bound(blockNum);
		for (int j=0; j<9; ++j)
			blockVec[j] = *it1++;
	};

	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() const
	{
		bool cellChanged = false;
		for_each(Squares.begin(), Squares.end(), cellChanged |=  
			boost::lambda::bind(&SudokuCell::Changed, boost::lambda::_1));
		return cellChanged;
	}

	void CellCollection::GetChangedCells(std::vector<int> &vChangedCells) const
	{
		for_each(Squares.begin(), Squares.end(),  
			boost::lambda::bind(&CollectChangedCells, boost::lambda::_1, &vChangedCells));
	}

	int CellCollection::GetChangedCellCount() const
	{
		int count = 0;
		for_each(Squares.begin(), Squares.end(), count += 
			boost::lambda::bind(&CountChangedCells, boost::lambda::_1));
		return count;
	}

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

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

	bool CellCollection::GotContradictions() const
	{
		bool bContradictions = false;
		for_each(Squares.begin(), Squares.end(),  
			bContradictions |= boost::lambda::bind(&SudokuCell::Contradiction, boost::lambda::_1));
		return bContradictions;
	}

	void CellCollection::SetTautologies(std::string &sText) const
	{
		for_each(Squares.begin(), Squares.end(),  
			boost::lambda::bind(&SudokuCell::CheckTautology, boost::lambda::_1, sText));
	}

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



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.

License

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

Share

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

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