算法基本思想：
1.数据结构，利用short来存每个格子的值。利用低位的9个bit来表示每个格子的值，如果是待确定的格子，则初始化时将最高位的bit置1，低位9个bit全部置1. 如果是已给出或推算出确定的唯一值，只要置上低位9个bit里对应的1个bit。
2.求解思路
（1）遍历每个待确定的格子S,
首先排除S所在9宫其他已确定的值，将那些值对应的bit置0。
第二，排除S所在列的其他已确定的值，将那些值对应的bit置0。
第三，排除S所在行的其他已确定的值，将那些值对应的bit置0。
（2）遍历9个9宫，遍历每个待确定格子，检查该格子的所有可能值，是否有某个可能值只在这个格子里有，而其他8个格子没有的，那么这个格子就是这个值。
（3）只要在（1）（2）中有某个格子得到唯一解，那么整个遍历结束后需要再一次执行（1）（2），直到没有任何格子的值得到唯一解。这时后有2种状态：
1就是全部求得解，打印结果，结束。
2仍然还有待确定的结果，这时就需要猜测值。
找到第一个待确定格子，将其每个可能值列出来，每个可能值拷贝一份数据，压栈，结束。
（4） 如果栈不为空，每次pop出一个拷贝，利用（1）（2）（3）来求解。
附代码如下：
SudokuParser.h
#pragma once
#include <stack>
const short unsureValue = (short) 0x81ff; // first bit and last 9 bits set to 1
const short allUnsureValue = 0x1ff; // last 9 bits set to 1
const short convertValue1 = 0x1;
const short convertValue2 = 0x2;
const short convertValue3 = 0x4;
const short convertValue4 = 0x8;
const short convertValue5 = 0x10;
const short convertValue6 = 0x20;
const short convertValue7 = 0x40;
const short convertValue8 = 0x80;
const short convertValue9 = 0x100;
const short convertData[] = {unsureValue, convertValue1, convertValue2, convertValue3, convertValue4,
convertValue5, convertValue6, convertValue7, convertValue8, convertValue9};
class SudokuData
{
public:
SudokuData() {}
SudokuData(short data[][9]);
SudokuData& operator=(const SudokuData& val);
friend class SudokuParser;
private:
short mData[9][9];
};
class SudokuParser
{
public:
SudokuParser(const SudokuData& data);
~SudokuParser();
// 求解主函数
void parse();
private:
// 返回坐标x，y的方格是否是已经有确定了的唯一值。还是有多种可能，确定的话返回1，否则返回0
int hasConfirm(int x, int y)
{
return !(mSudokuData.mData[x][y] & (1 << 16));
}
// 检查该方格所在的3x3的九格，去掉已经存在的可能值，保留最后剩下的可能值
void single3x3Check(int x, int y);
// 检查该方格所在列的九格，去掉已经存在的可能值，保留最后剩下的可能值
void singleRowCheck(int x, int y);
// 检查该方格所在行的九格，去掉已经存在的可能值，保留最后剩下的可能值
void singleColumnCheck(int x, int y);
// 检查9个 3x3的9宫，遍历每个未确定的格子，检查该格子的所有可能值，是否有某个可能值只在这个格子有，其他8个格子没有的，那么这个格子就是这个值。
int check3x3UnsureCell();
// 找到第一个未确定的格子，将其所有可能值设置上，并压栈。
void guessValue();
// 坐标x，y的格子是未确定的，将其与其所在九宫里的其他未确定格子比较，确定是否有某个值只在这个格子里有，如果有的话，那么这个格子就是这个值。同时返回1，否则返回0
int checkIfOnlyOneValue(int startx, int starty, int x, int y, short value);
// 检查是否此格子的值是只有一个唯一值
int isOnlyOneValue(short value);
// 检查此格子的值是否为0，这表示这格子没有任何可能，一般意味着此数独无解.
int isNoValue(short value);
// 检查是否所有格子都给出了唯一结果。
int isAllCleared();
// 对成员变量mSudokuData开始求解
// return value: -1 means no solution
// 0 means success
// 1 means no solution, but it need to guess value and reparse.
int parseOneData();
// 将内部变量转换成1-9的数
int convertValue(short value);
// 打印结果
void print();
private:
std::stack<SudokuData> mStack;
SudokuData mSudokuData;
int mPossibleSolutionCount;
};
SudokuParser.cpp
#include "SudokuParser.h"
#include <iostream>
using namespace std;
SudokuData::SudokuData(short data[][9])
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
mData[i][j] = convertData[data[i][j]];
}
}
}
SudokuData& SudokuData::operator=(const SudokuData& val)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
mData[i][j] = val.mData[i][j];
}
}
return *this;
}
SudokuParser::SudokuParser(const SudokuData& data)
:mPossibleSolutionCount(0)
{
mStack.push(data);
}
SudokuParser::~SudokuParser(void)
{
}
// 检查该方格所在的3x3的九格，去掉已经存在的可能值，保留最后剩下的可能值
void SudokuParser::single3x3Check(int x, int y)
{
int startx = (x / 3) * 3;
int starty = (y / 3) * 3;
for (int i = startx; i < startx + 3; i++)
{
for (int j = starty; j < starty + 3; j++)
{
if (hasConfirm(i, j))
{// 去掉已经存在的值，剩下的就是未确定的值
mSudokuData.mData[x][y] &= (~mSudokuData.mData[i][j]);
}
}
}
}
// 检查该方格所在列的九格，去掉已经存在的可能值，保留最后剩下的可能值
void SudokuParser::singleRowCheck(int x, int y)
{
for (int i = 0; i < 9; i++)
{
if (hasConfirm(i, y))
{// 去掉已经存在的值，剩下的就是未确定的值
mSudokuData.mData[x][y] &= (~mSudokuData.mData[i][y]);
}
}
}
// 检查该方格所在行的九格，去掉已经存在的可能值，保留最后剩下的可能值
void SudokuParser::singleColumnCheck(int x, int y)
{
for (int i = 0; i < 9; i++)
{
if (hasConfirm(x, i))
{// 去掉已经存在的值，剩下的就是未确定的值
mSudokuData.mData[x][y] &= (~mSudokuData.mData[x][i]);
}
}
}
// 检查9个 3x3的9宫，遍历每个未确定的格子，检查该格子的所有可能值，是否有某个可能值只在这个格子有，其他8个格子没有的，那么这个格子就是这个值。
// 返回是否有值改变过。1表示有格子的值改变过，0表示没有
int SudokuParser::check3x3UnsureCell()
{
int changed = 0;
for (int ib = 0; ib < 3; ib++)
{
for (int jb = 0; jb < 3; jb++)
{// 9个3x3单独分开遍历
for(int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (!hasConfirm(ib * 3 + i, jb * 3 + j))
{//找到每个未确定的格子，然后检查是否有某个可能值只在这个格子里有，而其他8个格子里没有，那么这个格子就是这个值
short value = mSudokuData.mData[ib * 3 + i][jb * 3 + j];
if (checkIfOnlyOneValue(ib * 3, jb * 3, ib * 3 + i, jb * 3 + j, value))
{
changed = 1;
}
}
}
}
}
}
return changed;
}
// 坐标x，y的格子是未确定的，startx, starty是此格子所在9宫的起点左边，将其与其所在九宫里的其他未确定格子比较，
// 确定是否有某个值只在这个格子里有，如果有的话，那么这个格子就是这个值。同时返回1，否则返回0
int SudokuParser::checkIfOnlyOneValue(int startx, int starty, int x, int y, short value)
{
int onlyoneValue;
for(int i = 0; i < 9; i++)
{
onlyoneValue = 1;
if (value & 1 << i) // 表示value里包含了i值，i是1-9。遍历得到该格子的可能的值，然后拿来与其他个每个格子来比较
{
for (int in = startx; in < startx + 3; in++)
{
for (int jn = starty; jn < starty + 3; jn++)
{
if (in == x && jn == y)
{// 不与本格子比较，跳过
continue;
}
if (!hasConfirm(in, jn))
{
// 如果此可能值在其他格子里有，校验失败，返回0,检查下个格子
if (mSudokuData.mData[in][jn] & 1 << i)
{
onlyoneValue = 0;
break;
}
}
}
if (!onlyoneValue)
{
// 如果此可能值在其他格子里有，校验失败，返回0,检查下个格子
break;
}
}
if (onlyoneValue)
{ // 如果只有该格子有此可能值, 设上此值，并返回1.不再检查其他值，因为每个格子只能有一个值.
mSudokuData.mData[x][y] = 1 << i;
return 1;
}
}
}
return 0;
}
// 检查是否此格子的值是只有一个唯一值
int SudokuParser::isOnlyOneValue(short value)
{// 这个有个bug，如果value是0或者0x8000，则仍然返回1.
short val = value & allUnsureValue;
val &= val - 1;
return !val;
}
// 检查此格子的值是否为0，这表示这格子没有任何可能，一般意味着此数独无解.
int SudokuParser::isNoValue(short value)
{
return !(value & allUnsureValue);
}
// 找到第一个未确定的格子，将其所有可能值设置上，并将每个可能值的数据压栈。
void SudokuParser::guessValue()
{
for(int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (!hasConfirm(i, j))
{
short val = mSudokuData.mData[i][j];
for(int k = 0; k < 9; k++)
{
if (val & 1 << k) // 表示value里包含了i值，i是1-9。
{//设置这个空格所有可能的值，都压入栈中。
mSudokuData.mData[i][j] = 1 << k;
mStack.push(mSudokuData);
}
}
return;
}
}
}
}
// 对成员变量mSudokuData开始求解
// return value: -1 means no solution
// 0 means success
// 1 means no solution, but it need to guess value and reparse.
int SudokuParser::parseOneData()
{
int changed;
do
{
changed = 0;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (!hasConfirm(i, j))//如果该项值还没确定
{
short temp = mSudokuData.mData[i][j];
//先用下面三个方法来排除未知格子的不可能值，剩下的是可能的值
single3x3Check(i, j);
singleRowCheck(i, j);
singleColumnCheck(i, j);
if (temp != mSudokuData.mData[i][j])
{ //如果值有改变，那么校验是否无解或者找到唯一解。
if (isNoValue(mSudokuData.mData[i][j]))
{// which means no solution
return -1;
}
else if (isOnlyOneValue(mSudokuData.mData[i][j]))
{//将未确定的标志去掉,标志是short的最高位的一个bit.
mSudokuData.mData[i][j] &= allUnsureValue;
}
changed = 1;
}
}
}
}
if (!changed)
{//检查每个3x3方格里是否有某个未确定的方格里有一个数只在其中一个方格里，表示那个方格的值就是那个数,
//比如a格有1，2两个可能的值，b方格里有1，2，3可能值，c方格有1，2，那么b方格的值肯定是3.
changed = check3x3UnsureCell();
}
if (!changed && !isAllCleared())
{// 使用上面的常规方法都无法求得唯一解，需要开始猜测值。
cout<<"need to guess"<<endl;
guessValue();
return 1;
}
}while(changed);
print();
mPossibleSolutionCount++;
return 0;
}
// 求解主函数
void SudokuParser::parse()
{
// 使用栈来存多种可能情况的数据，并一一求解。
while(!mStack.empty())
{
mSudokuData = mStack.top();
mStack.pop();
parseOneData();
}
cout<<"Solution Count:"<<mPossibleSolutionCount<<endl;
}
// 检查是否所有格子都给出了唯一结果。
int SudokuParser::isAllCleared()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (!hasConfirm(i, j))
{
return 0;
}
}
}
return 1;
}
// 打印结果
void SudokuParser::print()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << convertValue(mSudokuData.mData[i][j]) << " ";
}
cout<<endl;
}
cout << endl;
}
// 将内部变量转换成1-9的数
int SudokuParser::convertValue(short value)
{
switch (value)
{
case convertValue1:
return 1;
case convertValue2:
return 2;
case convertValue3:
return 3;
case convertValue4:
return 4;
case convertValue5:
return 5;
case convertValue6:
return 6;
case convertValue7:
return 7;
case convertValue8:
return 8;
case convertValue9:
return 9;
default:
return 0;
}
}
int main(int argc, char* argv[])
{
/*
short sudoku[9][9] = {
{4, 5, 1, 3, 8, 0, 6, 0, 0},
{9, 2, 6, 0, 0, 5, 0, 7, 3},
{8, 0, 7, 0, 2, 9, 0, 1, 0},
{5, 9, 0, 0, 0, 6, 2, 0, 1},
{0, 0, 4, 1, 3, 2, 0, 0, 0},
{0, 1, 0, 5, 0, 4, 0, 0, 0},
{6, 7, 0, 0, 4, 0, 3, 8, 5},
{0, 8, 0, 7, 6, 3, 4, 2, 9},
{3, 0, 9, 2, 0, 8, 1, 0, 7}
};
short sudoku[9][9] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}
};
*/
short sudoku[9][9] = {
{0, 0, 0, 0, 0, 0, 4, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{2, 1, 0, 0, 0, 0, 0, 3, 0},
{0, 5, 9, 8, 1, 3, 0, 0, 0},
{6, 0, 1, 0, 9, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 4, 0, 0, 0},
{0, 3, 0, 0, 0, 6, 0, 1, 8},
{0, 0, 0, 0, 2, 0, 9, 0, 5},
{0, 0, 6, 5, 0, 0, 0, 0, 2}
};
/*
short sudoku[9][9] = {
{0, 0, 0, 0, 3, 0, 0, 6, 5},
{4, 6, 0, 9, 5, 0, 2, 0, 0},
{0, 0, 0, 0, 8, 6, 0, 0, 4},
{0, 0, 3, 0, 7, 0, 0, 0, 6},
{0, 0, 4, 0, 9, 0, 1, 0, 0},
{5, 0, 0, 0, 1, 0, 3, 0, 0},
{2, 0, 0, 1, 4, 0, 0, 0, 0},
{0, 0, 7, 0, 6, 5, 0, 2, 8},
{6, 3, 0, 0, 2, 0, 0, 0, 0}
};
*/
SudokuData data(sudoku);
SudokuParser parser(data);
parser.parse();
cin.get();
return 0;
}
