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.

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.

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.