Sudoku Solver in Excel using C# and Excel-DNA

Introduction

There is no shortage of Sudoku solvers implemented in all possible languages. But I could not find one that works in Excel. This article describes how to build Sudoku solver and generator in C# and expose it to Excel using Excel-DNA. The solver/generator algorithm is very basic and easy to follow.

Background

Excel is perfect for working with numbers arranged on the grid, so adding ability to generate and solve Sudoku puzzles is fairly straightforward. The solver is implemented in C# and exported to Excel with the help of Excel-DNA library.

Using the Code

The following Excel functions have been implemented for solving Sudoku puzzles.

1. acq_sudoku_generate - generates a random Sudoku puzzle. Takes an optional seed as an argument. if seed is not specified, it uses computer ticks as a seed. The function produces 9x9 matrix, and therefore needs to be entered in Excel as an array formula (Ctrl+Shift+Enter)
2. acq_sudoku_solve - solves Sudoku puzzle. Takes 9x9 Sudoku puzzle as an input argument and produces solved 9x9. Needs to be entered in Excel as an array formula (Ctrl+Shift+Enter).
3. acq_sudoku_solution_count - Returns a number of possible solutions to the specified puzzle. Normally, there should be only one solution, but if you manually remove digits from the puzzle, number of possible solutions goes up. The function stops counting solutions after 1024 are found.

Puzzle generator is implemented in ACQ.Math.Sudoku.Generate. We call it from Excel wrapper function by first checking the seed argument. Generate function produces 9 x 9 array. Elements equal to zero in this array represent empty Sudoku cells. Since we don't want Excel to show zeros, we convert int array to array of objects and replace zeros with empty strings.

[ExcelFunction(Description = "Generate Sudoku puzzle", IsThreadSafe = true)]
public static object[,] acq_sudoku_generate(object seed)
{
    int[,] grid;
    if (seed != null && seed is double)
    {
        grid = ACQ.Math.Sudoku.Generate((int)(double)seed);
    }
    else
    {
        grid = ACQ.Math.Sudoku.Generate();
    }
    
    object[,] result = new object[grid.GetLength(0), grid.GetLength(1)];
    for (int i = 0; i < grid.GetLength(0); i++)
    {
        for (int j = 0; j < grid.GetLength(1); j++)
        {
            if (grid[i, j] == 0)
                result[i, j] = String.Empty;
            else
                result[i, j] = grid[i, j];
        }
    }
    return result;
}

Solving is done in ACQ.Math.Sudoku with a very primitive recursive algorithm. The function returns all the solutions up to specified maximum (1 in the code below). ExcelHelper.BoxArray converts int[,] into object[,]. If now solutions are found, ExcelError.ExcelErrorNull is returned. The function does not check that solution is unique.

[ExcelFunction(Description = "Solve Sudoku puzzle", IsThreadSafe = true)]
public static object[,] acq_sudoku_solve(object[,] grid)
{
    const int size = 9;
    int[,] sudoku = acq_sudoku_convertgrid(grid, size);
    if (sudoku != null)
    {
        List<int[,]> solutions = new List<int[,]>();
        ACQ.Math.Sudoku.Solve(sudoku, solutions, 1);
        if (solutions.Count > 0)
        {
            return ExcelHelper.BoxArray(solutions[0]);
        }
    }   
    return ExcelHelper.CreateArray(1, 1, ExcelError.ExcelErrorNull);
}

Code for the function that returns a number of possible Sudoku solutions is shown below. The implementation is almost identical to acq_sudoku_solve. This function can be used to track your progress when you are solving Sudoku puzzle manually in Excel. The number of possible solutions becomes zero when you make a mistake.

[ExcelFunction(Description = "Count solutions to Sudoku puzzle", IsThreadSafe = true)]
public static int acq_sudoku_solution_count(object[,] grid)
{
    const int size = 9;
    const int max_count = 1024;
    int[,] sudoku = acq_sudoku_convertgrid(grid, size);
    int count = 0;
    if (sudoku != null)
    {
        List<int[,]> solutions = new List<int[,]>();
        ACQ.Math.Sudoku.Solve(sudoku, solutions, max_count);
        count = solutions.Count;                
    }
    return count;
}

The algorithm used for solving Sudoku puzzle, is simple recursion. There are much better algorithms out there, therefore it is not listed here (search code for ACQ.Math.Sudoku.Solve for more details).

Puzzle generation is a little more interesting. On the first step, Knuth shuffle (a.k.a. the Fisher-Yates shuffle) is used to fill diagonal 3 x 3 blocks (as shown in Figure below). These blocks are independent and therefore can be filled randomly. Then puzzle is solved and numbers are randomly removed from the puzzle while there is still a unique solution.

The latest version is available at https://github.com/ratesquant/ACQ.

Acknowledgment

This ACQ add-in is based on Excel-DNA https://exceldna.codeplex.com/. Thanks to Govert van Drimmelen (creator of Excel-DNA) for making it happen.