I'm trying to implement a generic Sudoku solver (with n x n puzzles). The puzzle itself is contained in the class Feld
with:
typedef size_t Point;
class Feld {
public:
// containing all the possible values in binary, eg: 7 means this could be 0,1,2
std::vector<Point> pos;
Point L0; // length of the vector pos (n^2 for a nxn puzzle)
Point L1; // sqrt(L0)
Point L2; // sqrt(L1)
Point L12; // L1*L2
...
}
One of the functions tries to find a box-line interaction. This is done here (entry point is the function M3):
bool M3core(Feld &feld, Point viv, const std::function<Point (Point,Point)> &fun,
const Point ignoreR,const std::function<Point (Point)> &offR,const Point ignoreC,const std::function<Point (Point)> &offC) {
//Reduce access
const Point L2 = feld.L2;
// Remove the unwanted values
for (Point i = 0; i < L2; i++) {
// This is part of the intersection
if (i == ignoreR) { continue; }
for (Point ii = 0, off = offR(i); ii < L2; ii++) {
viv ^= viv & feld.pos[fun(off,ii)];
}
}
// We are left with no values to compare
if (!viv) { return 0; }
// Compare
bool change = 0;
for (Point i = 0; i < L2; i++) {
// This is part of the intersection
if (i == ignoreC) { continue; }
for (Point ii = 0, off = offC(i); ii < L2; ii++) {
if (viv & feld.pos[fun(off,ii)]) {
#ifndef NDEBUG
M3COUNTER++;
printf("Found M3\n");
#endif
change = 1;
feld.pos[fun(off,ii)] &= ~viv;
}
}
}
return change;
}
bool M3(Feld &feld) {
//Reduce access
const Point L1 = feld.L1;
const Point L2 = feld.L2;
const Point L12 = feld.L12;
//col & box
for (Point boxRow = 0; boxRow < L2; boxRow++) {
for (Point boxCol = 0; boxCol < L2; boxCol++) {
for (Point inBox = 0,boxOff = boxRow*L12 + boxCol*L2 ; inBox < L2; inBox++) {
// Add the possibilities of the horizontal intersection
Point vivVer = 0;
Point vivHor = 0;
for (Point i = 0, offHor = boxOff + inBox*L1, offVer = boxOff + inBox; i < L2; i++) {
vivHor |= feld.pos[offHor + i];
vivVer |= feld.pos[offVer + i*L1];
}
// Define lambdas - this are used to calculate the coordinates to compare box - line
auto offHorBox = [=] (const Point i) { return i*L1 + boxOff; };
auto offVerBox = [=] (const Point i) { return boxOff + i; };
auto offHorLine = [=] (const Point i) { return i*L2 + inBox*L1 + boxRow*L12; };
auto offVerLine = [=] (const Point i) { return i*L12 + inBox + boxCol*L2; };
auto funHor = [=] (const Point off,const Point ii) { return off + ii; };
auto funVer = [=] (const Point off,const Point ii) { return off + ii*L1; };
// Run the core code
if (M3core(feld,vivHor,funHor,inBox,offHorBox,boxCol,offHorLine) ||
M3core(feld,vivHor,funHor,boxCol,offHorLine,inBox,offHorBox) ||
M3core(feld,vivVer,funVer,inBox,offVerBox,boxRow,offVerLine) ||
M3core(feld,vivVer,funVer,boxRow,offVerLine,inBox,offVerBox)) { return 1; }
}
}
}
return 0;
}
This does work, but the only problem is that it is quite slow.
I tried to embrace functional programming to decrease DRY, but maybe I've overdone it. I would be happy to receive any suggestion to improve performance and also readability since this certainly could also be improved.
Since it was asked, here is the file where this function is used. It can be build with make final
(or one of the other recipes. But I have to warn you that the code is poorly commented. I do not expect anybody to go trough my gibberish, this is just to give some background and a working example.