Sudoku coding challenge

Coding challenges

Software developers love challenges. After all, programming is basically one big puzzle.

At Quba we like to run coding challenges for a bit of fun. You learn something doing them, but learn more seeing how other people did it - there are always multiple solutions to the same problem.

What is sudoku?

The challenge on this occasion was solving sudoku puzzles. For the unitiated sudoku is made up of a 9x9 grid, totalling 81 cells, and the numbers 1-9 must be placed within each cell using the following rules:

• Rule 1 - Each row must contain the numbers from 1 to 9, without repetitions
• Rule 2 - Each column must contain the numbers from 1 to 9, without repetitions
• Rule 3 - The digits can only occur once per block (nonet)
• Rule 4 - The sum of every single row, column, and nonet must equal 45

The puzzles start with a number of cells filled in, and the challenge is to fill the remaining cells.

For example:

The challenge

As this is a coding challenge it needs to involve some coding :-) The wording was quite succinct:

There’s 50k sudoku to solve, how quickly can you do it?

For this challenge a skeleton .NET core command line project had been setup with only 2 files:

• CSV containing 50k sudoku boards (both the puzzle and the solution for validation purposes)
• Program.cs with a timer (shown below)

The idea is the stopwatch is used to calculate the time taken to solve the puzzles. As with other challenges, proof of the puzzles actually being solved by validating with the CSV was also required.

Note: for fairness each entry was run 5 times and an average taken to account for different background resource usage.

Solutions

From all of the entries the quickest time achieved was < 2 seconds to solve all 50k puzzle boards. There is always scope to improve this, but the purpose of this post is to detail some of the learnings.

Release is better than debug

It may be an obvious statement, but running the solution in release mode was 100% quicker than running it in debug mode. This is because release mode is an optimised version, and does not load all of the symbols required for debugging.

Embedded resource

It was more efficient to include the CSV file as an embedded resource in the project rather than load it in at runtime. This method includes it as an asset that is included within the compiled version of the code, so the program can access it from memory rather than having to load it in via a stream at run time.

Lack of a mathematical solution

The interesting thing about sudoko is that because it is a logic puzzle, there is no direct algorithm or mathematical formula to solve it. More information on the techniques can be found at https://en.wikipedia.org/wiki/Sudoku_solving_algorithms

This means that multiple logic steps must be implemented in code. As the entrants had limited time the common way was to brute force the board (i.e. try every permutation until one fit). This is probably a bit on the harsh side as there was more finesse use than just pure brute force, but the sentiment still fits.

In this example backtracking (a type of brute force) is used along with recursion to fill the board:

static bool SolveSudoku(int[,] grid)
{
   for (int row = 0; row < 9; row++) // Iterate over each row in the grid
   {
       for (int col = 0; col < 9; col++) // Iterate over each column in the grid
       {
           if (grid[row, col] == 0) // If a cell is empty
           {
               for (int num = 1; num <= 9; num++) // Try numbers 1-9
               {
                   if (IsValid(grid, row, col, num)) // Check if the number is valid
                   {
                       grid[row, col] = num; // Place the number since it is valid

                        if (SolveSudoku(grid)) // Recursively solve rest of grid since we have our valid number
                           return true; // If solved, return true

                        grid[row, col] = 0; // Backtrack if not solved and try the next number
                   }
               }
               return false; // No valid number found, trigger backtracking
           }
       }
   }
   return true; // All cells filled, puzzle solved
}

Memory allocation

Using a StringBuilder is normally more efficient than simply using a string. It was also found that outputting the value of the StringBuilder in one go at the end (rather than after each board was solved) was much more efficient.

This also allows for memory to be preallocated for extra efficiency.

 // Aggregate all outputs into a single StringBuilder to minimize Console.Write calls
var finalOutput = new StringBuilder(outputBag.Count * 256); // Preallocate for efficiency

Multithreading

Firing multiple threads concurrently increased the efficiency. This means that multiple puzzles can be solved in parallel, and the program does not have to wait for one to be solved to move onto the next.

Luckily .NET has a ready made thread safe option for this in the form of:

Parallel.ForEach(lines, line =>

Final thoughts

Working on this challenge allowed us to use techniques that we may not use in every day development, and they provide a great way to collaborate on learning new skills.

There are likely to be many more ways to make the program even faster, but for now we move onto a new challenge.

If you would like to the source code to do it yourself, or think you can do it quicker, we'd love to hear from you.

Look out for the next challenge coming soon.