Last time, I wrote a fairly simple Sudoku puzzle generator. The only problem was that we had no way of determining solution uniqueness. So for the next part, that’s exactly what I want to do.

Feel free to follow along at https://github.com/Wallyza/sudoku. I’ll also be tagging the repo as I go so that what you’re reading is aligned with what you see in the code. Today’s tag is 0.0.2: https://github.com/Wallyza/sudoku/tree/v0.0.2

Why uniqueness is important

If a puzzle doesn’t have a unique solution, the ambiguity will likely end up in the player being stuck in a position where they’d need to guess. Personally, I want to solve puzzles using logic, elimination, and inference. Guessing reminds me of the very difficult Winmine puzzles back in the day, it’s not a good experience.

How to attain uniqueness

We need to constantly solve the puzzle we are creating and ensure that there is only 1 solution as we go about it.

To solve the puzzle, I could think of two methods:

Method 1 - Elimination

By taking the grid and looking at all possibilities and then eliminating them until we have only singular possibilities in some cells we can infer those are the numbers that belong in those cells.

After entering the numbers, we eliminate them again and keep going until a point where we don’t have singular options any more.

The elimination part is quite tricky because it’s not just about looking at the existing numbers on the grid but also about where the possibilities lie. An example would be if you had a row and you know in positions 4 and 6 you could only have the numbers 2 or 4, which means you can remove 2 and 4 from all other possibilities in the row.

You get many catches like this when eliminating and a tricky puzzle will put you in just such pitfalls.

This is quite difficult to code though, it becomes a near rule-based system.

Method 2 - Recursion with backsteps

This is kind of a brute force approach as follows:

  1. Find the first cell containing a 0 on the grid.
  2. Try numbers 1-9 until you find a “safe” one.
  3. If you have a safe one, find the next cell that contains a 0 and do the same.
  4. Keep doing so until you reach the end (add one possible solution) or you cannot find a safe one (this is not a valid solution).
  5. Backstep to the previous value and try the next number.

Simple enough and there is a set amount of work that needs to be done, I chose this approach.

Let’s look at the code

There’s only one piece of code worth looking at I think:

private bool Solve(int row, int col, ref int numSolutions)
    {
        // If we've reached the end of the grid, we've found a solution
        if (row == 9)
        {
            numSolutions++;
            return true;
        }

        // If the current cell is already filled in, move on to the next cell
        if (_grid[row, col] != 0)
        {
            return TrySolveNextCell(row, col, ref numSolutions);
        }

        // Try filling in the current cell with each possible value
        for (var val = 1; val <= 9; val++)
        {
            if (IsSafe(row, col, val))
            {
                _grid[row, col] = val;

                // Recursively solve the rest of the puzzle
                if (TrySolveNextCell(row, col, ref numSolutions) && numSolutions > 1)
                {
                    return true;
                }

                // If we haven't found a solution, backtrack and try a different value
                _grid[row, col] = 0;
            }
        }

        // If we've tried every possible value for the current cell and none of them work, backtrack
        return false;
    }

This is the above algorithm put to code. We end up having to call this every time we remove a cell, this ensures that we are allowed to remove that cell without compromising the solution’s uniqueness.

What’s next?

Next up I want to make the puzzles look more pleasing. I intend to accomplish this by simply removing cells in a symmetrical fashion.