A Sudoku Teacher Using Boost Libraries

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

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


void BuildReasonText1(std::string& sText, bool bRow, int rowcol, int digit, int block1, int block2, int block3)
{
	sText = "In block ";
	sText += char ('1' + block1);
	sText += ", Digit ";
	sText += char('0'+digit);
	sText += " can only exist in ";
	if (bRow)
		sText += "row ";
	else
		sText += "column ";
	sText += char('1' + rowcol);
	sText += " therefore it cannot exist in that ";
	if (bRow)
		sText += "row ";
	else
		sText += "column ";
	sText += " in blocks ";
	sText += char ('1' + block2);
	sText += ", ";
	sText += char ('1' + block3);
}

void BuildReasonText2(std::string& sText, bool bRow, int rowcol1, int rowcol2, int digit, int block1, int block2, int block3)
{
	sText = "In blocks ";
	sText += char ('1' + block1);
	sText += ", ";
	sText += char ('1' + block2);
	sText += ", Digit ";
	sText += char('0'+digit);
	sText += " can only exist in ";
	if (bRow)
		sText += "rows ";
	else
		sText += "columns ";
	sText += char ('1' + rowcol1);
	sText += ", ";
	sText += char ('1' + rowcol2);
	sText += " therefore it cannot exist in that row in block ";
	sText += char ('1' + block3);
}


// 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 characterisitic will limit the neighboring block to one row or column for that digit.

bool PointingPairsAndTriples(CSudokuBlock* blocks, std::vector<std::string> &vHistory, bool bStep)
{
	std::string sText;

    int startRow = 0;
    int startCol = 0;

    // check for block interations (rows and columns)
	bool bStopAfterStep = false;
	for (int blockNum = 0; blockNum < 9; blockNum += 3)
    {
		if (bStopAfterStep)
			break;
        for (int digit=1; digit <=9; ++digit)
        {
			if (bStopAfterStep)
				break;

            // For the specified digit, we now know, for this row of 3 blocks, which row
            // the digit can exist in

            // If it can only exist in 1 row for any of these, it can't exist in that row for
            // the others

			int keyblock = 0;			// the block that is used to eliminate digits in other block(s)
			int otherBlock1 = 0;		// the block which we are going to eliminate the digit from that row
			int otherBlock2 = 0;		// the other block which we are going to eliminate the digit from that row
			boost::dynamic_bitset<> *prc1;
			boost::dynamic_bitset<> *prc2;
			boost::dynamic_bitset<> *prc3;

			for (int rc=0; rc<2; ++rc)	// once for rows, once for columns
			{
				if (bStopAfterStep)
					break;
				boost::dynamic_bitset<> *digitsRowOrCol1;
				boost::dynamic_bitset<> *digitsRowOrCol2;
				boost::dynamic_bitset<> *digitsRowOrCol3;

				int block1, block2, block3;

				if (rc == 0)	// rows
				{
					block1 = blockNum;
					block2 = blockNum+1;
					block3 = blockNum+2;
					digitsRowOrCol1 = blocks[block1].GetRowsAllowingDigit(digit);
					digitsRowOrCol2 = blocks[block2].GetRowsAllowingDigit(digit);
					digitsRowOrCol3 = blocks[block3].GetRowsAllowingDigit(digit);
				}
				else	// columns
				{
					block1 = blockNum/3;
					block2 = blockNum/3 + 3;
					block3 = blockNum/3 + 6;
					digitsRowOrCol1 = blocks[block1].GetColsAllowingDigit(digit);
					digitsRowOrCol2 = blocks[block2].GetColsAllowingDigit(digit);
					digitsRowOrCol3 = blocks[block3].GetColsAllowingDigit(digit);
				}

				for (int loop=0; loop<3; ++loop)
				{
					switch (loop)
					{
						case 0:
							prc1 = digitsRowOrCol1;
							prc2 = digitsRowOrCol2;
							prc3 = digitsRowOrCol3;
							keyblock = block1;
							otherBlock1 = block2;
							otherBlock2 = block3;
							break;
						case 1:
							prc1 = digitsRowOrCol2;
							prc2 = digitsRowOrCol1;
							prc3 = digitsRowOrCol3;
							keyblock = block2;
							otherBlock1 = block1;
							otherBlock2 = block3;
							break;
						case 2:
							prc1 = digitsRowOrCol3;
							prc2 = digitsRowOrCol1;
							prc3 = digitsRowOrCol2;
							keyblock = block3;
							otherBlock1 = block1;
							otherBlock2 = block2;
							break;
					}
					if ((*prc1).count() == 1)
					{
						// it can't be in the same row for the other two blocks in the row
						int line = (*prc1).to_ulong() / 2;
						BuildReasonText1(sText, (rc == 0), line, digit, keyblock, otherBlock1, otherBlock2);

						if (rc == 0)
						{
							if (blocks[otherBlock1].EliminateDigitForRow(line, digit, sText))
							{
								vHistory += sText;
								if (bStep)
								{
									bStopAfterStep = true;
									break;
								}
							}

							if (blocks[otherBlock2].EliminateDigitForRow(line, digit, sText))
							{
								vHistory += sText;
								if (bStep)
								{
									bStopAfterStep = true;
									break;
								}
							}
						}
						else
						{
							if (blocks[otherBlock1].EliminateDigitForCol(line, digit, sText))
							{
								vHistory += sText;
								if (bStep)
								{
									bStopAfterStep = true;
									break;
								}
							}

							if (blocks[otherBlock2].EliminateDigitForCol(line, digit, sText))
							{
								vHistory += sText;
								if (bStep)
								{
									bStopAfterStep = true;
									break;
								}
							}
						}
					}

					if ((*prc1).count() == 2)
					{
						int line1 = -1;
						int line2 = -1;
						for (int lineBit=0; lineBit<3; ++lineBit)
						{
							if ((*prc1)[lineBit] == 1)
							{
								if (line1 == -1)
									line1 = lineBit;
								else
									line2 = lineBit;
							}
						}
						if (((*prc2).count() == 2) && ((*prc2) == (*prc1)))
						{
							BuildReasonText2(sText, (rc == 0), line1, line2, digit, keyblock, otherBlock1, otherBlock2);

							// the digit can not be in either of these two columns in block 3
							for (int lineBit=0; lineBit<3; ++lineBit)
							{
								if ((*prc1)[lineBit] == 1)
								{
									if (rc == 0)
									{
										if (blocks[otherBlock2].EliminateDigitForRow(lineBit, digit, sText))
										{
											vHistory += sText;
											if (bStep)
											{
												bStopAfterStep = true;
												break;
											}
										}
									}
									else
									{
										if (blocks[otherBlock2].EliminateDigitForCol(lineBit, digit, sText))
										{
											vHistory += sText;
											if (bStep)
											{
												bStopAfterStep = true;
												break;
											}
										}
									}
								}
							}
						}
						else if (((*prc3).count() == 2) && ((*prc3) == (*prc1)))
						{
							BuildReasonText2(sText, (rc == 0), line1, line2, digit, keyblock, otherBlock2, otherBlock1);

							// the digit can not be in either of these two columns in block 2
							for (int lineBit=0; lineBit<3; ++lineBit)
							{
								if ((*prc1)[lineBit] == 1)
								{
									if (rc == 0)
									{
									if (blocks[otherBlock1].EliminateDigitForRow(lineBit, digit, sText))
										{
											vHistory += sText;
											if (bStep)
											{
												bStopAfterStep = true;
												break;
											}
										}
									}
									else
									{
									if (blocks[otherBlock1].EliminateDigitForCol(lineBit, digit, sText))
										{
											vHistory += sText;
											if (bStep)
											{
												bStopAfterStep = true;
												break;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
    }

   return true;
}