Sudoku Part 2

In the previous part, I outlined what the plan was. In this part, we’ll be stepping into some code.

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.1: https://github.com/Wallyza/sudoku/tree/v0.0.1

How to run the code

I’ve coded it up in .Net 6, I was too lazy to install 7. To run it you’ll have to install the SDK which can be found here: https://dotnet.microsoft.com/en-us/download/dotnet/6.0 along with installation instructions. Once it’s installed and you’ve cloned the repo, just navigate to the Sudoku project folder and run dotnet run.

What the code does

This is still a very rudimentary version. It starts by filling out a valid 9-grid and then it shuffles the columns and rows around. This way it’s randomized but valid. It then proceeds to remove 40 of those numbers and replaces them with 0 (blanks). Finally, it outputs (in a rather lazy fashion) the 9-grid to the terminal.

What it doesn’t do

It doesn’t check the number of solutions. That means there are potentially multiple solutions to the puzzle or that the user would have to guess. As discussed in the previous post, puzzles should only have one solution and the user should not have to guess.

Some code bits

I shifted most of the logical code into its own static class for the time being. It’s not overly deterministic so I’ll move it to an instanced class instead soon enough. The class consists of 4 methods:

public static int[,] Generate()
    {
        // Step 1: Create Grid
        var grid = new int[9, 9];
        
        // Step 2: Fill in numbers
        for (var row = 0; row < 9; row++)
        {
            for (var col = 0; col < 9; col++)
            {
                grid[row, col] = (row * 3 + row / 3 + col) % 9 + 1;
            }
        }

        // Step 3: Shuffle rows and columns
        ShuffleRows(grid);
        ShuffleColumns(grid);

        // Step 4: Remove cells to create puzzle
        RemoveCells(grid);

        return grid;
    }

This function takes goes through each cell in the 9-grid and applies a simple mathematical equation to ensure we create a valid grid.

If we have a valid grid we can shuffle rows and columns (as long as they remain within their respective 3-grids).

    private static void ShuffleRows(int[,] grid)
    {
        var random = new Random();
        for (var block = 0; block < 3; block++)
        {
            for (var i = 0; i < 2; i++)
            {
                var row1 = random.Next(3) + block * 3;
                var row2 = random.Next(3) + block * 3;
                for (var col = 0; col < 9; col++)
                {
                    (grid[row1, col], grid[row2, col]) = (grid[row2, col], grid[row1, col]);
                }
            }
        }
    }

    private static void ShuffleColumns(int[,] grid)
    {
        var random = new Random();
        for (var block = 0; block < 3; block++)
        {
            for (var i = 0; i < 2; i++)
            {
                var col1 = random.Next(3) + block * 3;
                var col2 = random.Next(3) + block * 3;
                for (var row = 0; row < 9; row++)
                {
                    (grid[row, col1], grid[row, col2]) = (grid[row, col2], grid[row, col1]);
                }
            }
        }
    }

Notice how everything happens in a factor of 3, the intention is to ensure we don’t move anything outside of its original 3-grid which would otherwise invalidate the 9-grid.

I was originally unsure how I would randomize the 9-grid but it helped when I reminded myself that even though the puzzle spans the entire 9-grid, there’s still a compartmentalized puzzle in each 3-grid. You can shuffle the rows in a 3-grid as long as you shuffle all the 3-grids in the same row in the same manner.

Lastly we have this:

    private static void RemoveCells(int[,] grid)
    {
        var random = new Random();
        for (var i = 0; i < 40; i++)
        {
            var row = random.Next(9);
            var col = random.Next(9);
            if (grid[row, col] != 0)
            {
                grid[row, col] = 0;
            }
            else
            {
                i--;
            }
        }
    }

This makes it a puzzle, even if it’s bad one right now. All we’re doing is removing 40 numbers. So, out of 81 cells, nearly half of them is removed. This might sound like a lot but the reality is that it’s actually quite easy.

Note that it doesn’t check for the number of solutions yet and it’s kind of a static difficulty. Once we have that in place we can pass an argument to adjust the difficulty.

Coming up

In the next post, I want to discuss how would be best to programmatically solve a puzzle.

Waldemar Muhl