Create Sudoku Solver with Excel VBA

Creating a Sudoku Solver in Excel using VBA is a great way to practice algorithm design and automation. Here’s a detailed breakdown of how to build the solver in Excel VBA:

Overview:

The Sudoku puzzle consists of a 9×9 grid, where some cells are pre-filled with numbers, and others are empty (represented by zeroes or blanks). The solver will try to fill the empty cells by following these rules:

1. Each row must contain the numbers 1 to 9 without repetition.
2. Each column must contain the numbers 1 to 9 without repetition.
3. Each of the nine 3×3 sub-grids must contain the numbers 1 to 9 without repetition.

The VBA code will employ a backtracking algorithm to solve the puzzle, trying different numbers for empty cells and backtracking if it reaches an invalid state.

Steps to Implement the Solver in VBA:

1. Prepare the Worksheet

In your Excel worksheet, set up a 9×9 grid where the Sudoku puzzle will be displayed. You can represent the puzzle using a simple range like A1:I9, where each cell corresponds to a number in the puzzle.

2. Open the VBA Editor

Press Alt + F11 to open the Visual Basic for Applications (VBA) editor. In the editor, go to Insert → Module to create a new module where you will paste the VBA code.

3. Write the Sudoku Solver Code

Here’s the detailed VBA code for the Sudoku Solver using a backtracking algorithm:

Sub SolveSudoku()
    ' Define variables
    Dim sudoku(1 To 9, 1 To 9) As Integer
    Dim row As Integer, col As Integer
    Dim i As Integer, j As Integer   
    ' Read the Sudoku puzzle from the worksheet into the sudoku array
    For row = 1 To 9
        For col = 1 To 9
            sudoku(row, col) = Cells(row, col).Value
        Next col
    Next row   
    ' Call the recursive solver function
    If Solve(sudoku) Then
        ' Write the solved Sudoku puzzle back to the worksheet
        For row = 1 To 9
            For col = 1 To 9
                Cells(row, col).Value = sudoku(row, col)
            Next col
        Next row
        MsgBox "Sudoku Solved!"
    Else
        MsgBox "No solution exists."
    End If
End Sub

Function Solve(ByRef sudoku() As Integer) As Boolean
    ' This function attempts to solve the Sudoku using a backtracking algorithm
    Dim row As Integer, col As Integer
    Dim num As Integer   
    ' Find the next empty cell (0 represents an empty cell)
    If Not FindEmptyCell(sudoku, row, col) Then
        ' No empty cell found, puzzle is solved
        Solve = True
        Exit Function
    End If   
    ' Try all numbers from 1 to 9
    For num = 1 To 9
        ' Check if the number is valid for this cell
        If IsValid(sudoku, row, col, num) Then
            ' Assign the number to the cell
            sudoku(row, col) = num           
            ' Recursively attempt to solve the rest of the puzzle
            If Solve(sudoku) Then
                Solve = True
                Exit Function
            End If
            ' Backtrack if no solution was found
            sudoku(row, col) = 0
        End If
    Next num   
    ' No valid number was found, backtrack
    Solve = False
End Function

Function FindEmptyCell(ByRef sudoku() As Integer, ByRef row As Integer, ByRef col As Integer) As Boolean
    ' This function finds the next empty cell in the Sudoku puzzle (represented by 0)
    For row = 1 To 9
        For col = 1 To 9
            If sudoku(row, col) = 0 Then
                FindEmptyCell = True
                Exit Function
            End If
        Next col
    Next row
    FindEmptyCell = False
End Function

Function IsValid(ByRef sudoku() As Integer, row As Integer, col As Integer, num As Integer) As Boolean
    ' This function checks if a number is valid for a given cell (row, col) in the Sudoku puzzle   
    ' Check if the number already exists in the row
    Dim i As Integer
    For i = 1 To 9
        If sudoku(row, i) = num Then
            IsValid = False
            Exit Function
        End If
    Next i   
    ' Check if the number already exists in the column
    For i = 1 To 9
        If sudoku(i, col) = num Then
            IsValid = False
            Exit Function
        End If
    Next i   
    ' Check if the number already exists in the 3x3 subgrid
    Dim startRow As Integer, startCol As Integer
    startRow = Int((row - 1) / 3) * 3 + 1
    startCol = Int((col - 1) / 3) * 3 + 1
    For i = startRow To startRow + 2
        For j = startCol To startCol + 2
            If sudoku(i, j) = num Then
                IsValid = False
                Exit Function
            End If
        Next j
    Next i  
    ' The number is valid if it isn't in the row, column, or subgrid
    IsValid = True
End Function

Explanation of the Code:

1. Sub SolveSudoku: This is the main subroutine that reads the Sudoku puzzle from the Excel worksheet, calls the recursive Solve function, and then writes the solved puzzle back to the worksheet.
2. Function Solve: This is the recursive backtracking function that solves the Sudoku puzzle. It tries to fill the empty cells one by one by placing numbers 1-9 and checking if they are valid. If a number leads to an invalid state, it backtracks (removes the number and tries the next one).
3. Function FindEmptyCell: This function searches for the next empty cell (0) in the puzzle. It returns True if an empty cell is found, and False if the puzzle is completely filled.
4. Function IsValid: This function checks if placing a given number in a specific cell is valid. It checks the row, column, and 3×3 subgrid to ensure no duplicates.

5. Using the Solver:

• Enter your Sudoku puzzle in the range A1:I9 (9×9 grid). Use 0 or leave the cells empty for the puzzle’s blanks.
• Run the macro by pressing Alt + F8, selecting SolveSudoku, and clicking Run.
• The solver will fill in the grid and display a message box when the puzzle is solved or if no solution exists.

6. Handling Edge Cases:

• If the puzzle has no solution (e.g., due to an invalid initial configuration), the solver will display a message saying « No solution exists. »
• Ensure that the input puzzle follows the basic rules of Sudoku to avoid inconsistencies or invalid states.

Conclusion:

This code utilizes the backtracking algorithm, a common approach to solving constraint satisfaction problems like Sudoku. It systematically tries potential solutions, backtracking when it encounters an invalid state, until it finds a valid solution or concludes that no solution exists.