Sudoku Week-End Challenge - Brute-Force Recursive solver

This is part of my attempt at the Week-End Challenge #3. The overall problem is larger than will fit in one question. This is a well-contained subset of my larger program.

The goal of this part is to brute-force all possible (if any) solutions to a puzzle. The input to this algorithm is a 2-dimensional array representing the Sudoku grid. This array is processed so that, at each point in the array, there is a 'set' of 'possible' digits. For example, at a position (r,c) in the grid, if there is the set of values [ 1, 2, 3 ] it would mean that, at position (r,c) the puzzle could possibly be a 2, 3, or 4. (The solution assumes a zero-based counting system, whereas traditional Sudoku's use a 1-based counting system).

If the set of digits at (r,c) contains just a single value then the assumption is that the cell at that position is 'solved'.

It is assumed that the input grid is 'consistent' with the rules of Sudoku.... that a solved value occurs only once in any row/column/block combination, and that no solved value appears anywhere in the 'potential' set of values for any other cell in the same row/column/block.

I have tried numerous algorithms for forcing a solution, and this is the fastest I tried (by a long shot), but the algorithm is complicated....

I have a tendency to reduce problems down to primitive-value manipulation, and that tends to make solutions harder to read (even though they may be faster).

What I would like is suggestions for how to improve this code by expressing the algorithm more clearly (make the code look more like the algorithm) while not horribly impacting the performance. In other words, I do not believe there are significantly faster algorithms, but performance is not everything!

I have tried to describe the algorithm in the code. Additionally, I have a 'main method' which supplies a pre-constructed Sudoku puzzle in the required input format. The actual example puzzle is the same as the one in this week's challenge.

The algorithm:

``

buildFollowing

The logic of this this function is difficult to follow. Part of it is because of your insistence on very short names (rb, cb, etc.) with comments breaking up the flow of the code; as a rule of thumb, if you need a comment to describe what a variable does, you should probably make the name longer. Internal comments should almost always describe why, not what.

I'd consider something like this:

/**
 * Compute a list of all indices **after** the one corresponding to
 * row and col that are not already solved.
 *
 * Requires that available has already been initialized.
 */
private int[] buildFollowing(int row, int col) {
    int[] following = new int[dimension * 3];
    int numFollowers = 0;
    // Get all followers in this row.
    for (int c = col + 1; c  1) {
            following[numFollowers++] = candidate;
        }
    }
    // Get all followers in this column.
    for (int r = row + 1; r  1) {
            following[numFollowers++] = candidate;
        }
    }
    // Get followers in the same block.
    int blockDimension = (int) Math.sqrt(dimension);
    int lastColInBlock = ((col % blockDimension) + 1) * blockDimension - 1;
    int lastRowInBlock = ((row % blockDimension) + 1) * blockDimension - 1;
    for (int r = row + 1; r  1) {
                following[numFollowers++] = candidate;
            }
        }
    }
    return Arrays.copyOf(following, numFollowers);
}

This function is divided into "paragraphs," where the purpose of each block is clear. rb and cb are renamed to lastRowInBlock and lastColInBlock, and they're not declared until they're used.

recurse

Why is the for loop counting down instead of up? When I see that pattern, I expect that there's a reason for it, but there doesn't seem to be here. As with buildFollowing, this function suffers a bit from superfluous comments and oddly named variables. Let me take a crack:

/**
 * Recursively solve the Sudoku puzzle.
 *
 * @param solutions All solutions found so far.
 * @param unknownIndex The current element of unknown we're solving on.
 * @param partialSolution This array contains the partial solution selected
 *     so far for all cells prior to unknowns[unknownIndex]; the solution
 *     for cell (i / dimension, i % dimension) is
 *     available[partialSolution[i]].
 * @param stillAvailable (stillAvailable[i] & (1  solutions, int unknownIndex,
        int[] partialSolution, int[] stillAvailable) {
    if (unknownIndex >= unknowns.length) {
        solutions.add(buildSolution(partialSolution));
        return;
    }
    int index = unknowns[unknownIndex];
    for (int a = 0; a < available[index.length]; a++) {
        int candidate = available[a];
        long appliedConstraints = applyConstraints(
            index, candidate, stillAvailable);
        if (appliedConstraints < 0) {
            // No solution is possible with this cell set to candidate.
            continue;
        }
        partialSolution[index] = a;
        recurse(solutions, index + 1, partialSolution, stillAvailable);
        removeConstraints(
                index, candidate, stillAvailable, appliedConstraints);
    }
}

I'll leave the implementation of applyConstraints and removeConstraints as an exercise to the reader, but the contract of applyConstraints is that it returns a negative number iff any following cell is left with no possible value; otherwise it returns a long that encodes which elements of stillAvailable were modified.

Notice how the comment describing the workings of the algorithm is made unnecessary by using well-named helper functions; the code makes the algorithm clear.

Minor Issues

• The comment describing followings should include an example to make it easier to understand. On that note, you should put the description of followings in one place; right now it's split between the declaration and the initialization.

• tmpunknowns complicates the logic in your constructor to save a few tens of bytes. I'm reasonably sure that it doesn't even help with cacheline pressure, as I doubt that the entire array is pulled into the L1 cache when accessing a signle elements. If you decide to keep it, you should move the copy from tmpunknowns to unknowns up to immediately after the initialization of tmpunknowns; as it is, you're separating related pieces of code, which makes it more difficult to understand.

• It's bad practice to check in commented-out code (I refer here to your // System.out.println(..., //Arrays.copyOf(resetmask..., etc.

• In my experience, local variables are only declared final if they are to be used in inner classes. So, e.g., in solve when you declare combination or freedoms to be final, I look for the inner class where they're used. Idiomatic Java doesn't have the same sense of const-correctness that C++ has.

• I suspect that making bitmasks a method instead of an array will make your optimized code faster; the compiler can inline the functi

StackExchange Code Review Q#37425, answer score: 10