Generic Sudoku solver might have too many iterations

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 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 &fun,
const Point ignoreR,const std::function &offR,const Point ignoreC,const std::function &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 = boxRowL12 + boxColL2 ; inBox < L2; inBox++

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.

StackExchange Code Review Q#59225, answer score: 2