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