经典的数独游戏由9*9的方阵表示，每个位置可以填写1-9的数字，要求：
- 每行中，数字1-9都仅出现一次
- 每列中，数字1-9都仅出现一次
- 左上、上、右上、左、中、右、左下、下、右下9个3*3的小矩阵中，数字1-9都仅出现一次
数独是一款常见的益智数字游戏，无奈我智商偏低，很多数独解不下去，只有靠程序帮忙才能挽回一点尊严。
这里附带了一个2017年夏天写的C++求解数独程序，可以在几毫秒的时间里破译所谓的最难数独；由于是在一两个下午匆匆写完的，代码已经看不下去了，不过幸好思路还记得。
思路
可能性数组
基本的思路是递归+回溯。考虑一种最暴力的解法：递归地瞎蒙填数字，到所有数字填满后，根据数独规则检查是否合法，如合法则输出结果，如不合法则回溯。这样写出来的代码简洁易懂，不过性能就很坑爹了。其实，玩过数独的朋友都知道，在填写数字时，根据数独三条基本规则进行直接或间接地推导，有些位置的数字可以唯一地确定。例如：某空格所在行、列、组中已经出现了2-9这8个数字，那么这个空格只可能填1。许多简单、中级的数独都可以这样一路填完，更高级的谜题才需要若干次的瞎蒙。因此，这个程序：
- 维护一个81*9的bool型的二维数组，描述81个空格在三条基本规则的直接推导下是否可能填写数字1-9。
当某个空格只可能填写某一个数字时，我们就可以自信满满地不需要回溯地填下去；当某个空格不可能为任何数字时，我们就可以得知矛盾已经发生从而提前开始回溯；如果两者皆否，那么就需要开始瞎蒙了。
贪心猜测
其次——正如上面提到的——更高级的谜题必然需要若干次地瞎蒙才能继续填写下去（之前也有了解到，对于高难度地题目不论用多风骚地技巧也无法避免猜测）。当我们发现无法自信满满地填写任何一个数字时，就不可避免地使用递归回溯进行猜测。既然避免不了要猜，那么自然要猜到点上，程序也因此遵循了局部最优的贪心原则，即：
- 优先从可能性较少的空格开始猜。
例如，假设数独有唯一解，一个空格可能填12345五个数字，而另一个空格可能填78两个数字，那么从后者开始猜能够猜中的概率显然会大于前者。
任意阶数
9*9的经典数独是一种3阶的数独，而这个程序可以实现任意n阶的数独猜测，如16*16的4阶数独。不过，阶数提高后时间复杂度也会指数提高。
并行猜测
性能不够，并行来凑。程序使用OpenMP实现多线程。不过，目前而言仅在根部递归展开并行，又由于贪心猜测使得可猜的数字一般只有2~3个，因此并行度并不够高。
不足之处
这个程序的可能性数组仅由三条规则的直接推导得出，需要承认的是，直接推导的效力很弱，许多隐含的确定性是无法侦测到的。如果能够程序实现更加高效的间接推导，那么效率会进一步提高。
程序
是时候祭上自己看了都害怕“以前的代码”了。
头文件: SudokuKiller.hpp
#pragma once
#include <memory>
#include <vector>
using namespace std;
class SudokuKiller
{
typedef pair<unsigned int, unsigned int> Grid;
private:
inline unsigned int * InitData() {
unsigned int * data = new unsigned int[Area];
return data;
}
inline bool ** InitPossible() {
bool ** possible = new bool*[Area];
for (int i = 0; i < Area; i++) {
possible[i] = new bool[Len];
}
return possible;
}
inline Grid ** InitGrid() {
Grid ** gridData = new Grid*[GridCount];
for (int g = 0; g < GridCount; g++) {
gridData[g] = new Grid[Len];
int rs = (g % Order) * Order;
int cs = (g / Order) * Order;
int idx = 0;
for (int r = rs; r < rs + Order; r++) {
for (int c = cs; c < cs + Order; c++) {
gridData[g][idx].first = r;
gridData[g][idx].second = c;
idx++;
}
}
}
return gridData;
}
inline void DeleteData(unsigned int * data) {
delete data;
}
inline void DeletePossible(bool ** possible) {
for (int i = 0; i < Area; i++) {
delete possible[i];
}
delete possible;
}
inline void DeleteGrid(Grid ** gridData) {
for (int g = 0; g < GridCount; g++) {
delete gridData[g];
}
delete gridData;
}
inline void CopyData(unsigned int * dataNew, unsigned int * dataOld) {
memcpy(dataNew, dataOld, sizeof(unsigned int) * Area);
}
inline void CopyPossible(bool ** possibleNew, bool ** possibleOld) {
for (int i = 0; i < Area; i++) {
memcpy(possibleNew[i], possibleOld[i], sizeof(bool) * Len);
}
}
protected:
unsigned int Order;
unsigned int Len;
unsigned int Area;
unsigned int GridCount;
unsigned int * Data = nullptr;
bool ** Possible = nullptr;
Grid ** GridData = nullptr;
inline bool UpdatePossibilityByRow(unsigned int * data, bool ** possible, int r) {
//The array "p" for all elements' possibility temporarily, true as default
bool * p = new bool[Len];
memset(p, 0xFF, sizeof(bool) * Len);
//If an element is confirmed in this row, then we switch the corresponding "p" to "false"
unsigned int d;
for (int c = 0; c < Len; c++) {
d = data[r * Len + c];
if (d) {
d--;
if (p[d] == false)
return false; //We return a false here because this situation means that there're dumplicated elements in the row, which is invalid
p[d] = false;
}
}
//Then we can update "possible" refering to "p", by logical AND
for (int c = 0; c < Len; c++) {
bool anyPossible = false;
for (int i = 0; i < Len; i++) {
possible[r * Len + c][i] &= p[i];
anyPossible |= possible[r * Len + c][i];
}
if (!data[r * Len + c] && !anyPossible)
return false; //When an unconfirmed element has no possible values, it means a contradiction occurs
}
delete p;
return true;
}
inline bool UpdatePossibilityByCol(unsigned int * data, bool ** possible, int c) {
//Similar to "UpdatePossibilityByRow"
bool * p = new bool[Len];
memset(p, 0xFF, sizeof(bool) * Len);
unsigned int d;
for (int r = 0; r < Len; r++) {
d = data[r * Len + c];
if (d) {
d--;
if (p[d] == false)
return false;
p[d] = false;
}
}
for (int r = 0; r < Len; r++) {
bool anyPossible = false;
for (int i = 0; i < Len; i++) {
possible[r * Len + c][i] &= p[i];
anyPossible |= possible[r * Len + c][i];
}
if (!data[r * Len + c] && !anyPossible)
return false;
}
delete p;
return true;
}
inline bool UpdatePossibilityByGrid(unsigned int * data, bool ** possible, int g) {
//Similar to "UpdatePossibilityByRow"
int r, c;
bool * p = new bool[Len];
memset(p, 0xFF, sizeof(bool) * Len);
unsigned int d;
for (int n = 0; n < Len; n++) {
r = GridData[g][n].first;
c = GridData[g][n].second;
d = data[r * Len + c];
if (d) {
d--;
if (p[d] == false)
return false;
p[d] = false;
}
}
for (int n = 0; n < Len; n++) {
r = GridData[g][n].first;
c = GridData[g][n].second;
bool anyPossible = false;
for (int i = 0; i < Len; i++) {
possible[r * Len + c][i] &= p[i];
anyPossible |= possible[r * Len + c][i];
}
if (!data[r * Len + c] && !anyPossible)
return false;
}
delete p;
return true;
}
inline bool UpdatePossibility(unsigned int * data, bool ** possible) {
for (int i = 0; i < Len; i++) {
if (!UpdatePossibilityByRow(data, possible, i)) return false;
if (!UpdatePossibilityByCol(data, possible, i)) return false;
}
for (int i = 0; i < GridCount; i++) {
if (!UpdatePossibilityByGrid(data, possible, i)) return false;
}
return true;
}
inline void GetPossibleValues(bool ** possible, int i, vector<unsigned int> & possibleValues) {
possibleValues.clear();
for (int n = 0; n < Len; n++) {
if (possible[i][n]) {
possibleValues.push_back(n + 1);
}
}
}
inline bool Solve(unsigned int * data, bool ** possible, volatile bool & solved, int nest = 0) {
int guessIndex; //The index of an unconfirmed element with minimal possibilities, being -1 if all elements are confirmed
std::vector<unsigned int> guessValues; //The possible values of guessIndex element
bool updated; //Whether this Solve makes any difference
//Now we keeps updating "data" as well as "possible", when we find any element can be confirmed
//When a contradictory occurs, a false is returned in advance
std::vector<unsigned int> possibleValues;
do {
updated = false;
guessIndex = -1;
for (int i = 0; i < Area; i++) {
if (data[i]) continue;
GetPossibleValues(possible, i, possibleValues);
if (possibleValues.size() == 1) {
data[i] = possibleValues[0];
updated = true;
}
else {
if (guessIndex == -1) {
guessIndex = i;
guessValues = possibleValues;
}
else if (possibleValues.size() < guessValues.size()) {
guessIndex = i;
guessValues = possibleValues;
}
}
}
if (updated) {
if (!UpdatePossibility(data, possible)) return false;
}
} while (guessIndex != -1 && updated);
//If we all elements are confirmed
if (guessIndex == -1) return true;
//If we cannot solve the sudoku by the methods above, we make guesses and check them by recursion
//Note that we only need to guess one unconfirmed element at a time, since the remaining shall be done during the following recursions
bool retval = false;
if (nest == 0) {
//Guess in parallel
//We will malloc data for every thread
#pragma omp parallel for schedule(dynamic)
for (int i = 0; i < guessValues.size(); i++) {
if (solved) continue;
unsigned int * dataNext = InitData();
bool ** possibleNext = InitPossible();
CopyData(dataNext, data);
CopyPossible(possibleNext, possible);
dataNext[guessIndex] = guessValues[i];
if (UpdatePossibility(dataNext, possibleNext) && Solve(dataNext, possibleNext, solved, nest + 1)) {
#pragma omp critical
{
CopyData(data, dataNext);
CopyPossible(possible, possibleNext);
retval = true;
solved = true;
}
}
DeleteData(dataNext);
DeletePossible(possibleNext);
}
}
else {
//Guess in sequential
unsigned int * dataRaw = InitData();
bool ** possibleRaw = InitPossible();
CopyData(dataRaw, data);
CopyPossible(possibleRaw, possible);
for (int i = 0; i < guessValues.size(); i++) {
if (solved) continue;
data[guessIndex] = guessValues[i];
if (UpdatePossibility(data, possible) && Solve(data, possible, solved, nest + 1)) {
retval = true;
solved = true;
}
else {
CopyData(data, dataRaw);
CopyPossible(possible, possibleRaw);
}
}
DeleteData(dataRaw);
DeletePossible(possibleRaw);
}
return retval;
}
public:
SudokuKiller(unsigned int order = 3) {
Order = order;
Len = Order * Order;
Area = Len * Len;
GridCount = Len;
Data = InitData();
Possible = InitPossible();
GridData = InitGrid();
}
virtual ~SudokuKiller() {
DeleteData(Data);
DeletePossible(Possible);
DeleteGrid(GridData);
}
bool SetData(unsigned int * input) {
for (int i = 0; i < Area; i++) {
if (input[i] < Len + 1) {
Data[i] = input[i];
for (int n = 0; n < Len; n++) Possible[i][n] = true;
}
else {
return false;
}
}
bool valid = UpdatePossibility(Data, Possible);
return valid;
}
bool Solve(unsigned int * output) {
volatile bool solved = false;
if (Solve(Data, Possible, solved)) {
memcpy(output, Data, sizeof(unsigned int) * Area);
return true;
}
else {
return false;
}
}
};
使用: main.cpp
#include <iostream>
#include <windows.h>
#include "SudokuKiller.hpp"
//高精度计时
unsigned long long NowTicks() {
LARGE_INTEGER time;
LARGE_INTEGER frequency;
QueryPerformanceFrequency(&frequency);
QueryPerformanceCounter(&time);
return 1000 * 100 * time.QuadPart / frequency.QuadPart;
}
int main()
{
//3阶经典数独求解
SudokuKiller killer(3);
//百度百科中的“最难数独”
//https://baike.baidu.com/item/%E4%B8%96%E7%95%8C%E6%9C%80%E9%9A%BE%E6%95%B0%E7%8B%AC
unsigned int data1[81] = {
0, 0, 5, 3, 0, 0, 0, 0, 0,
8, 0, 0, 0, 0, 0, 0, 2, 0,
0, 7, 0, 0, 1, 0, 5, 0, 0,
4, 0, 0, 0, 0, 5, 3, 0, 0,
0, 1, 0, 0, 7, 0, 0, 0, 6,
0, 0, 3, 2, 0, 0, 0, 8, 0,
0, 6, 0, 5, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 3, 0,
0, 0, 0, 0, 0, 9, 7, 0, 0,
};
//另一处的“最难数独”
//https://blog.csdn.net/littlethunder/article/details/9749509
unsigned int data2[81] = {
8, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 3, 6, 0, 0, 0, 0, 0,
0, 7, 0, 0, 9, 0, 2, 0, 0,
0, 5, 0, 0, 0, 7, 0, 0, 0,
0, 0, 0, 0, 4, 5, 7, 0, 0,
0, 0, 0, 1, 0, 0, 0, 3, 0,
0, 0, 1, 0, 0, 0, 0, 6, 8,
0, 0, 8, 5, 0, 0, 0, 1, 0,
0, 9, 0, 0, 0, 0, 4, 0, 0,
};
unsigned int output[81];
unsigned long long time;
//题目1
killer.SetData(data1);
time = NowTicks();
killer.Solve(output);
std::cout << 1.0 * (NowTicks() - time) / 100 << " ms" << std::endl;
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
cout << output[r * 9 + c] << " ";
}
cout << endl;
}
cout << endl;
//题目2
killer.SetData(data2);
time = NowTicks();
killer.Solve(output);
std::cout << 1.0 * (NowTicks() - time) / 100 << " ms" << std::endl;
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
cout << output[r * 9 + c] << " ";
}
cout << endl;
}
cout << endl;
return 0;
}
输出
1.67 ms
1 4 5 3 2 7 6 9 8
8 3 9 6 5 4 1 2 7
6 7 2 9 1 8 5 4 3
4 9 6 1 8 5 3 7 2
2 1 8 4 7 3 9 5 6
7 5 3 2 9 6 4 8 1
3 6 7 5 4 2 8 1 9
9 8 4 7 6 1 2 3 5
5 2 1 8 3 9 7 6 4
4.45 ms
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2