数独求解器在某些游戏中挂起
Sudoku solver hangs for some games
我已经编写了 Donald Knuth Algorithm X for solving exact cover problems and applied it to Sudoku for the purpose of solving Project Euler Problem 96. My code is a translation from Python into C++ of Ali Assaf's implementation 相同算法的实现。
我的版本解决了此 text file 中包含的大部分网格，但它在网格 06 上挂起。
Grid 06
100920000
524010000
000000070
050008102
000000000
402700090
060000000
000030945
000071006
我已经使用了一堆探索性的 cout 语句，但我一直无法找出导致程序挂起的原因。
如果您需要更多信息才能理解我的代码，请告诉我。
#include <algorithm>
#include <array>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
bool solve(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<int>* solution);
void select_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r);
void deselect_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r);
// square boxes only
static const int BOX_SIZE = 3; // standard sudoku grid
static const int SIZE = BOX_SIZE*BOX_SIZE;
int main() {
int top_left_sum = 0;
// initialize the sparse matrix representation of the sudoku problem
map<int, set<int>> C; // constraints/columns
for (int i = 0; i < 4*SIZE*SIZE; i++) {
C[i] = set<int>();
}
map<int, array<int, 4>> R; // subsets/rows
for (int i = 0; i < SIZE*SIZE*SIZE; i++) {
// i is the subset index and encodes location and number on grid
int index = i/SIZE;
int row = i/(SIZE*SIZE);
int column = (i/SIZE) % SIZE;
int box = BOX_SIZE*(row/BOX_SIZE) + column/BOX_SIZE;
int value = i % SIZE;
// there are 4 constaints satisfied by each number placement
array<int, 4> subset;
// insert the keys of constraints that subset satisfies
subset[0] = (index); // row-column
subset[1] = (SIZE*SIZE + SIZE*row + value); // row-number
subset[2] = (2*SIZE*SIZE + SIZE*column + value); // column-number
subset[3] = (3*SIZE*SIZE + SIZE*box + value); // box-number
R.insert(pair<int, array<int, 4>>(i, subset));
for (auto c : subset) {
C[c].insert(i);
}
}
ifstream ifs("../sudoku.txt");
string line;
while (getline(ifs, line)) {
if (line[0] == 'G') {
map<int, set<int>> X = C;
map<int, array<int, 4>> Y = R;
vector<int> solution;
for (int i = 0; i < SIZE; i++) {
getline(ifs, line);
for (int j = 0; j < SIZE; j++) {
if (line[j] != '0') {
int r = SIZE*SIZE*i + SIZE*j + line[j] - '1';
solution.push_back(r);
vector<set<int>> cs;
select_row(&X, &Y, &cs, r);
}
}
}
solve(&X, &Y, &solution);
sort(solution.begin(), solution.end());
top_left_sum += 100*(solution[0] % SIZE + 1)
+ 10*(solution[1] % SIZE + 1)
+ solution[2] % SIZE + 1;
// display solution
for (size_t i = 0; i < solution.size(); i++) {
if (i % 9 == 0) cout << endl;
cout << solution[i] % 9 + 1 << ' ';
} cout << endl << endl;
}
}
ifs.close();
cout << top_left_sum << endl;
return 0;
}
bool solve(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<int>* solution) {
if ((*X).empty()) return true;
// find the column with the minimum number of nonzero elements
map<int, set<int>>::iterator c_min = (*X).begin();
for (map<int, set<int>>::iterator c = ++(*X).begin();
c != (*X).end(); ++c) {
if ((*c).second.size() < (*c_min).second.size()) {
c_min = c;
}
}
// for each row pointed to by c_min, call solve recursively
for (auto r : (*c_min).second) {
(*solution).push_back(r);
vector<set<int>> cs;
select_row(X, Y, &cs, r);
if (solve(X, Y, solution)) return true;
deselect_row(X, Y, &cs, r);
(*solution).pop_back();
}
return false;
}
void select_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r) {
for (auto j : (*Y)[r]) {
for (auto i : (*X)[j]) {
for (auto k : (*Y)[i]) {
if (k != j) (*X)[k].erase(i);
}
}
(*cs).push_back((*X)[j]);
(*X).erase(j);
}
return;
}
void deselect_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r) {
for (array<int, 4>::reverse_iterator j = (*Y)[r].rbegin();
j != (*Y)[r].rend(); ++j) {
(*X)[*j] = (*cs).back();
(*cs).pop_back();
for (auto i : (*X)[*j]) {
for (auto k : (*Y)[i]) {
if (k != *j) (*X)[k].insert(i);
}
}
}
return;
}
正如 PaulMackenzie 所指出的，我的代码的问题是我擦除的对象仍然具有指向它们的初始化指针，特别是我在 [=12= 中迭代的集合 (*c_min).second 中的整数] 函数。
我通过复制 (*c_min).second 并遍历该副本来解决此问题。
求解函数的固定版本如下所示：
bool solve(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<int>* solution) {
if ((*X).empty()) return true;
// find the column with the minimum number of nonzero elements
map<int, set<int>>::iterator c_min = (*X).begin();
for (map<int, set<int>>::iterator c = ++(*X).begin();
c != (*X).end(); ++c) {
if ((*c).second.size() < (*c_min).second.size()) {
c_min = c;
}
}
set<int> c = (*c_min).second; // ADDED LINE
// for each row pointed to by c_min, call solve recursively
for (auto r : c) { // CHANGED LINE
(*solution).push_back(r);
vector<set<int>> cs;
select_row(X, Y, &cs, r);
if (solve(X, Y, solution)) return true;
deselect_row(X, Y, &cs, r);
(*solution).pop_back();
}
return false;
}
我已经编写了 Donald Knuth Algorithm X for solving exact cover problems and applied it to Sudoku for the purpose of solving Project Euler Problem 96. My code is a translation from Python into C++ of Ali Assaf's implementation 相同算法的实现。
我的版本解决了此 text file 中包含的大部分网格，但它在网格 06 上挂起。
Grid 06
100920000
524010000
000000070
050008102
000000000
402700090
060000000
000030945
000071006
我已经使用了一堆探索性的 cout 语句，但我一直无法找出导致程序挂起的原因。
如果您需要更多信息才能理解我的代码，请告诉我。
#include <algorithm>
#include <array>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
bool solve(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<int>* solution);
void select_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r);
void deselect_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r);
// square boxes only
static const int BOX_SIZE = 3; // standard sudoku grid
static const int SIZE = BOX_SIZE*BOX_SIZE;
int main() {
int top_left_sum = 0;
// initialize the sparse matrix representation of the sudoku problem
map<int, set<int>> C; // constraints/columns
for (int i = 0; i < 4*SIZE*SIZE; i++) {
C[i] = set<int>();
}
map<int, array<int, 4>> R; // subsets/rows
for (int i = 0; i < SIZE*SIZE*SIZE; i++) {
// i is the subset index and encodes location and number on grid
int index = i/SIZE;
int row = i/(SIZE*SIZE);
int column = (i/SIZE) % SIZE;
int box = BOX_SIZE*(row/BOX_SIZE) + column/BOX_SIZE;
int value = i % SIZE;
// there are 4 constaints satisfied by each number placement
array<int, 4> subset;
// insert the keys of constraints that subset satisfies
subset[0] = (index); // row-column
subset[1] = (SIZE*SIZE + SIZE*row + value); // row-number
subset[2] = (2*SIZE*SIZE + SIZE*column + value); // column-number
subset[3] = (3*SIZE*SIZE + SIZE*box + value); // box-number
R.insert(pair<int, array<int, 4>>(i, subset));
for (auto c : subset) {
C[c].insert(i);
}
}
ifstream ifs("../sudoku.txt");
string line;
while (getline(ifs, line)) {
if (line[0] == 'G') {
map<int, set<int>> X = C;
map<int, array<int, 4>> Y = R;
vector<int> solution;
for (int i = 0; i < SIZE; i++) {
getline(ifs, line);
for (int j = 0; j < SIZE; j++) {
if (line[j] != '0') {
int r = SIZE*SIZE*i + SIZE*j + line[j] - '1';
solution.push_back(r);
vector<set<int>> cs;
select_row(&X, &Y, &cs, r);
}
}
}
solve(&X, &Y, &solution);
sort(solution.begin(), solution.end());
top_left_sum += 100*(solution[0] % SIZE + 1)
+ 10*(solution[1] % SIZE + 1)
+ solution[2] % SIZE + 1;
// display solution
for (size_t i = 0; i < solution.size(); i++) {
if (i % 9 == 0) cout << endl;
cout << solution[i] % 9 + 1 << ' ';
} cout << endl << endl;
}
}
ifs.close();
cout << top_left_sum << endl;
return 0;
}
bool solve(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<int>* solution) {
if ((*X).empty()) return true;
// find the column with the minimum number of nonzero elements
map<int, set<int>>::iterator c_min = (*X).begin();
for (map<int, set<int>>::iterator c = ++(*X).begin();
c != (*X).end(); ++c) {
if ((*c).second.size() < (*c_min).second.size()) {
c_min = c;
}
}
// for each row pointed to by c_min, call solve recursively
for (auto r : (*c_min).second) {
(*solution).push_back(r);
vector<set<int>> cs;
select_row(X, Y, &cs, r);
if (solve(X, Y, solution)) return true;
deselect_row(X, Y, &cs, r);
(*solution).pop_back();
}
return false;
}
void select_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r) {
for (auto j : (*Y)[r]) {
for (auto i : (*X)[j]) {
for (auto k : (*Y)[i]) {
if (k != j) (*X)[k].erase(i);
}
}
(*cs).push_back((*X)[j]);
(*X).erase(j);
}
return;
}
void deselect_row(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<set<int>>* cs, int r) {
for (array<int, 4>::reverse_iterator j = (*Y)[r].rbegin();
j != (*Y)[r].rend(); ++j) {
(*X)[*j] = (*cs).back();
(*cs).pop_back();
for (auto i : (*X)[*j]) {
for (auto k : (*Y)[i]) {
if (k != *j) (*X)[k].insert(i);
}
}
}
return;
}
正如 PaulMackenzie 所指出的，我的代码的问题是我擦除的对象仍然具有指向它们的初始化指针，特别是我在 [=12= 中迭代的集合 (*c_min).second 中的整数] 函数。
我通过复制 (*c_min).second 并遍历该副本来解决此问题。
求解函数的固定版本如下所示：
bool solve(map<int, set<int>>* X, map<int, array<int, 4>>* Y,
vector<int>* solution) {
if ((*X).empty()) return true;
// find the column with the minimum number of nonzero elements
map<int, set<int>>::iterator c_min = (*X).begin();
for (map<int, set<int>>::iterator c = ++(*X).begin();
c != (*X).end(); ++c) {
if ((*c).second.size() < (*c_min).second.size()) {
c_min = c;
}
}
set<int> c = (*c_min).second; // ADDED LINE
// for each row pointed to by c_min, call solve recursively
for (auto r : c) { // CHANGED LINE
(*solution).push_back(r);
vector<set<int>> cs;
select_row(X, Y, &cs, r);
if (solve(X, Y, solution)) return true;
deselect_row(X, Y, &cs, r);
(*solution).pop_back();
}
return false;
}