Generic Sudoku solver might have too many iterations

Question

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.

• Tobias Hermann: Have you used a profiler to check where most of the CPU is used?
• magu_: @Dobi. To be honest not really. I did try it with very sleep but without success (see comment @ stackoverflow.com/questions/18969178/…). I did however time the function by including respectively excluding it. As well as the fact that it needs L2^6 access on pos is a bit woring for me.
• Tobias Hermann: Under windows the combination of visual c++ express and very sleepy works for me. Under Linux I use g++ and sysprof. Perhaps one of these combinations is an option for you? Otherwise it would be good if you could make a minimal example that can be compiled and run with the problem you posted. This way we could reproduce it and try to improve the performance.
• magu_: @Dobi. I added the whole source file

Answer 1

Is it possible that the reason why the performance is bad is because solving a Sudoku puzzle is an NP-complete problem? So even if you squeeze cycles out of a loop iteration, the number of loop iterations might be the problem.

Wikipedia has a good discussion on this. The article also mentions the Dancing Links algorithm which might be more efficient. You might also want to read this Stack Overflow question regarding that algorithm and Sudoku.

• magu_: Hm, yes and no. Of course I will not be able to solve a problem to big. My algorigthm is currently able to solve any 16x16 grid I could find and easier 25x25 grids in less than 10''. I did try the dancing link algorigthm in the very beginning, but it was slower than going trough the vectors, even if they are empty. Thank you very much on the Wiki link. This is quite interessting.

Answer 2

The code you have posted is very difficult to understand.

What are L0, L1,..? Why is a length defined of type "Point"? What do the arguments of M3core represent? They seem to have nothing to do with a box and a line.

That said is very difficult to give help... it is useful to understand the algorithm to optimize it.

As regards the performance I would first compare your solution to a simple brute force algorithm to see if you are on good track. I have the impression that you are trying to use methods which are for human solving and require strategy and intuition which are difficult to code.

• magu_: Hm, okey sorry about that, I try to give some more explenations. Lx are of type Point since its equal to size_t. I should have it made size_t for simpler understanding. The lambda functions are used to calculate the position of the vectors of pos. My complete program does implement some functions like this accompanied by a brute force method. This methods are just used to decrease the amount of possibilities I have to get through with the brute force method. I did in fact use algorithm for humans and not for computers, so there is surely some room to improve...