A Sudoku Teacher Using Boost Libraries

// PileAndChain.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 "PileAndChain.h"
#include <boost/dynamic_bitset.hpp>
#include <boost/assign/std/vector.hpp> // for 'operator+=()'

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


// The terms pile exclusion and chain exclusion were taken from the Dr. Dobbs article 
// entitled "Sudoku & Graph Theory" by Eytan Suchard, Raviv Yatom, and Eitan Shapir

// Pile Exclusion - If n digits are possible in only n squares, than all other digits can be removed from 
// those n squares

// operate is a row or column or block of 3x3 cells
int PileExclusion(boost::array<SudokuCell*, 9>& operate, std::string sReason, std::vector<std::string> &vHistory, bool bStep)
{
	std::string sText;
	int pilesFound = 0;

	// First make an array of ints where each value = the number of times that digit (index)
	// appears on a possible digit list.
	// For example, if digitCount[5] = 3, then in our operate vector, only 3 squares can possibly
	// contain the digit 5
	int digitCount[10] = {0,0,0,0,0,0,0,0,0,0};

	for (int index=0; index<9; ++index)	// for each square in our vector
	{
		for (int digit=1; digit<=9; ++digit)	// for each possible digit
			if (operate[index]->Answer() == 0)	// don't count finished squares
			{
				if ((*(operate[index]->GetPossibleDigits()))[digit])
					digitCount[digit]++;
			}
	}

	boost::dynamic_bitset<> possiblePileExclusionDigits(10);
	boost::dynamic_bitset<> pileExclusionCheck(10);

	// Now check to see for cases where N numbers are possible in N squares
	// We'll look for pile exclusion from 2-7
	bool bStopAfterStep = false;

	for (int pEx = 2; pEx <= 7; ++pEx)
	{
		if (bStopAfterStep)
			break;
		possiblePileExclusionDigits.reset();
		for (int digit=1; digit <= 9; ++digit)
		{
			if (digitCount[digit] == pEx)
			{
				possiblePileExclusionDigits[digit] = 1;
			}
		}
		if (possiblePileExclusionDigits.count() == pEx)
		{
			sText = sReason;
			sText += "Pile: Digits ";
			GetStringFromBitList(&possiblePileExclusionDigits, sText);
			sText += " are possible in cells ";


			pileExclusionCheck.reset();
			// we have a possible pile exclusion situation.  The question is, are all of
			// our digits available in the pEx squares?
			int iAllDigits = 0;
			for (int index=0; index<9; ++index)	// for each square in our vector
			{
				if (operate[index]->Answer() == 0)	// don't count finished squares
				{
					pileExclusionCheck = (possiblePileExclusionDigits & (*(operate[index]->GetPossibleDigits())));
					if (pileExclusionCheck.count() == pEx)
					{
						sText += char('1' + index);
						sText += " ";
						iAllDigits++;
					}
				}
			}
			if (iAllDigits == pEx)	// YES, we have pile exclusion
			{
				sText += " - those cells can ONLY contain those digits";
				// remove any other digits
				for (int index=0; index<9; ++index)	// for each square in our vector
				{
					if (operate[index]->Answer() == 0)	// don't count finished squares
					{
						pileExclusionCheck = (possiblePileExclusionDigits & (*(operate[index]->GetPossibleDigits())));
						if (pileExclusionCheck.count() == pEx)
						{
							std::string sAdditionalInfo;
							sAdditionalInfo = "        Pile Exclusion: ";
							if (operate[index]->LimitPossibleDigits(&possiblePileExclusionDigits, sAdditionalInfo))
							{
								pilesFound++;
								vHistory += sText;
								vHistory += sAdditionalInfo;
								if (bStep)
								{
									bStopAfterStep = true;
									break;
								}
							}
						}
					}
				}
			}
		}
	}

	return pilesFound;
}



// Chain Exclusion - If the number of squares which can contain any n digits is n, those n digits
// can be removed from other squares in the group (row, column or block).
int ChainExclusion(boost::array<SudokuCell*, 9>& operate, std::string sReason, std::vector<std::string> &vHistory, bool bStep)
{
	struct SIndexBits
	{
		int index;
		boost::dynamic_bitset<>* possibleDigits;
		SudokuCell* pElm;
	};
	SIndexBits siStruct;
	std::vector<SIndexBits> siVect;

	std::string sText;
	int chainsFound = 0;

	// Fill up our vector of structs with only the cells which have not been solved
	for (int index=0; index<9; ++index)	// for each cell in our vector
	{
		if (operate[index]->Answer() == 0)
		{
			siStruct.index = index;
			siStruct.possibleDigits = operate[index]->GetPossibleDigits();
			siStruct.pElm = operate[index];
			siVect += siStruct;
		}
	}

	int num_cells = (int)siVect.size();

	boost::dynamic_bitset<> possibleDigits;

	bool bStopAfterStep = false;

	for (int j=0; j<num_cells; ++j)
	{
		if (bStopAfterStep)
			break;
		for (int k=j+1; k<num_cells; ++k)
		{
			if (bStopAfterStep)
				break;
			possibleDigits = (*(siVect[j].possibleDigits)) | (*(siVect[k].possibleDigits));
			if (possibleDigits.count() == 2)
			{
				// chain exclusion, no other cells can have these 2 digits
				// exclude
				for (int x=0; x<num_cells; ++x)
				{
					if (x!=j && x!=k)	// don't shoot the messenger
					{
						sText = sReason;
						sText += "Chain: Digits ";
						GetStringFromBitList(&possibleDigits, sText);
						sText += " must be limited to cells ";
						sText += char('1' + j);
						sText += " and ";
						sText += char('1' + k);
						if (siVect[x].pElm->RemoveTakenDigits(&possibleDigits, sText))
						{
							chainsFound++;
							vHistory += sText;
							if (bStep)
							{
								bStopAfterStep = true;
								break;
							}
						}
						// our struct could be updated here, but that would throw our for loop logic out of whack
						// Better to keep going.
					}
					bStopAfterStep = true;
					break;
				}
			}
			for (int l=k+1; l<num_cells; ++l)
			{
				if (bStopAfterStep)
					break;
				possibleDigits = (*siVect[j].possibleDigits) | (*siVect[k].possibleDigits);
				possibleDigits |= (*siVect[l].possibleDigits);
				if (possibleDigits.count() == 3)
				{
					// chain exclusion, no other cells can have these 3 digits
					// exclude
					for (int x=0; x<num_cells; ++x)
					{
						if (x!=j && x!=k && x!=l)	// don't shoot the messenger
						{
							sText = sReason;
							sText += "Chain: Digits ";
							GetStringFromBitList(&possibleDigits, sText);
							sText += " must be limited to cells ";
							sText += char('1' + j);
							sText += ", ";
							sText += char('1' + k);
							sText += " and ";
							sText += char('1' + l);
							if (siVect[x].pElm->RemoveTakenDigits(&possibleDigits, sText))
							{
								chainsFound++;
								vHistory += sText;
								if (bStep)
								{
									bStopAfterStep = true;
									break;
								}
							}
							// our struct could be updated here, but that would throw our for loop logic out of whack
							// Better to keep going.
						}
					}
				}

			}
		}
	}

	return chainsFound;
}