Sudoku Valid Arangements Permutations Enumerator

Question

I wondered if anyone has any ideas to make this cleaner or more efficient. Mostly this was an exercise to generate the data once (So speed really isn't too important, but I'd love to see what techniques you could think of) This is an algorithm I derived and implemented without external guidance of any kind, so I'm asking for guidance now.

This does give the output I am expecting, I validated it with a recursive implementation that I made first.

I'm thinking this might be helpful in validating solutions, or in generating new boards.

For the Sudoku table:

--1 --- ---
--- 1-- ---
--- --- --1
--- -1- ---
1-- --- ---
--- --- 1--
--- --- -1-
--- --1 ---
-1- --- ---

1 would be represented by the array: 238316751. In the first 9 cell box, the 1 is at position 2 in the array of that box.

///This outputs the valid pointers
///for example 327742830 is valid, a number could be in pos 3 of cell 0, 2 in cell 1, etc
///  So arrays are compatable when no columns have the same number in them
///  A starting board with a high number of compatable arrays would be very difficult i believe
public IEnumerable<string> OutputArrayPoints()
{
    return OutputArrayPoints(new int[9]);
}
//Will contain the cell indexes that are not excluded by other cells already
int[][] ToCheck = new int[9][];
//Pointers to the current cell indexes in use
int[] ToCheckPointers = new int[9];

//arrayPoints will contain the current value to return
//Really it should be equal to loop through ToCheck[c][ToCheckPointers[c]]
public IEnumerable<string> OutputArrayPoints(int[] arrayPoints)
{
    //This loop is basically a depth first search
    //ToCheck gets filled with possible values for each cell,
    //  and the lowest pointer gets incremented until it runs out,
    //  then moves up a cell to go down a different path
    for (int c = 0; c >= 0; /*++c*/)
    {
        if (c == 8 && ToCheck[c] != null && ToCheckPointers[c] < ToCheck[c].Length)
        {
            //Should be a valid solution, yield it
            yield return GetResult(arrayPoints);
            ++ToCheckPointers[c];
        }
        else if (c < 9 && ToCheck[c] != null && ToCheckPointers[c] < ToCheck[c].Length)
        {
            //Fill this cell of arrayPointers, and move to the next
            arrayPoints[c] = ToCheck[c][ToCheckPointers[c]];
            ++c;
        }
        else if (ToCheck[c] != null && ToCheckPointers[c] == ToCheck[c].Length)
        {
            //ToCheck at this level has been fully processed, clear it out
            ToCheck[c] = null;

            //Step up a cell to start processing the next
            --c;
            //if c is less than 0, we have gone through every option
            if (c == -1) yield break;
            //Increase the pointer I'm pointing at
            ++ToCheckPointers[c];
        }
        else if (c < 9 && ToCheck[c] == null)
        {
            //Fill any empty ones
            ToCheck[c] = CellsToCheck(arrayPoints, c).ToArray();
            ToCheckPointers[c] = 0;

            //lazy? (could this be in a cleaner spot? or do I need to store arrayPoints at all?):
            arrayPoints[c] = ToCheck[c][ToCheckPointers[c]];

            if (c < 8) ++c;
        }
    }
}

//Return the cells that are possible given the other positions taken
IEnumerable<int> CellsToCheck(int[] arrayPoints, int depth)
{
    int rowSkip1 = (depth % 3) > 0 ? arrayPoints[depth - 1] / 3 : -1;
    int rowSkip2 = (depth % 3) > 1 ? arrayPoints[depth - 2] / 3 : -1;
    int colSkip1 = depth > 2 ? arrayPoints[depth - 3] % 3 : -1;
    int colSkip2 = depth > 5 ? arrayPoints[depth - 6] % 3 : -1;

    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            if ((rowSkip1 != i && rowSkip2 != i)
                && (colSkip1 != j && colSkip2 != j)) yield return j + i*3;
        }
    }
}
//Return a string representation
string GetResult(IEnumerable<int> cells)
{
    return string.Join("", cells.Select(i => i.ToString()).ToArray());
}

Answer 1

• You have some "Magic Numbers". If you wanted to work with a different grid size you'd have to replace 9 at many different places. Find the relationships between your hard-coded numbers and declare them as const. For example, const int Size = 9; and const int Box = 3;

• I like that you are using yield

• Your code is quite hard to understand, even with your comments. This can have something to do with your variable names probably. ToCheck for example, if that is checking rows, columns, values, what kind of values, etc. is not clear at all from the name. From what I understand, you are sometimes considering the array indexes as index of a 3x3 grid, and sometimes as a row/column. That's confusing for me.

• Instead of using integer arrays, you could use Set<int>.

• int[][] ToCheck and int[] ToCheckPointers should be local variables inside the OutputArrayPoints method, they do not seem to be used outside it.

• As you are not incrementing the c variable on every iteration, I would use a while (c >= 0) rather than for.

• Slightly related is my Code Review question for a Sudoku Solver, it might give you an idea of how things can be organized into a more object-oriented approach

• All things considered, I must say that your code seems to be quite fast. I am quite sure it can be made faster but it's hard to tell how exactly because of the lack of clarity of the code.

Answer 2

The loop in OutputArrayPoints has several redundant conditions. Introducing a bit of nesting will allow easier refactoring later:

if (c == 8 && ToCheck[c] != null && ToCheckPointers[c] < ToCheck[c].Length)
{ /* */ }
else if (c < 9 && ToCheck[c] != null && ToCheckPointers[c] < ToCheck[c].Length)
{ /* */ }
else if (ToCheck[c] != null && ToCheckPointers[c] == ToCheck[c].Length)
{ /* */ }
else if (c < 9 && ToCheck[c] == null)
{ /* */ }

Can turn into:

if (ToCheck[c] == null)
{
    if (c < 9)
    { /* */ }
}
else
{
    if (ToCheckPointers[c] == ToCheck[c].Length)
    { /* */ }
    else
    {
        if (ToCheckPointers[c] < ToCheck[c].Length)
        {
            if (c == 8)
            { /* */ }
            else if (c < 9)
            { /* */ }
        }
    }
}

One reason for doing this, is that the order of the conditions does matter. When c == 8 evaluates to false, the rest of the condition isn't even evaluated, so the code jumps right to if (c < 9 && ToCheck[c] != null... - if ToCheck[c] == null, then ToCheckPointers[c] < ToCheck[c].Length will not be evaluated.

Nested conditions are annoying, but they're less annoying and more efficient than redundant conditions (you can probably gain a couple of milliseconds by doing this). The good thing though, is that it's easy to extract a method out of nested conditions. Much easier than out of redundant conditions.

---

I've noticed you're systematically doing ++n or --n to increment or decrement. When the pre-increment/decrement isn't warranted by an assignment operation, I find n++ and n-- to be more readable.

---

string GetResult(IEnumerable<int> cells)
{
    return string.Join("", cells.Select(i => i.ToString()).ToArray());
}

Minor nitpick, but rather than hard-coding a "" here, I'd use string.Empty, which makes the intent more explicit.