Introduction

Sudoku is a popular number puzzle that challenges players to fill a 9×9 grid with numbers such that each row, column, and 3×3 sub-grid contains all digits from 1 to 9 exactly once. Solving Sudoku puzzles programmatically is an interesting problem in computer science, often solved using backtracking algorithms. This program demonstrates how to solve Sudoku puzzles using Go (Golang).

Objective

The objective of this program is to create a Sudoku solver in Go that uses a backtracking algorithm to find solutions to valid Sudoku puzzles. The program is designed to take a partially filled 9×9 grid as input and return the solved grid.

Code

        package main

        import (
            "fmt"
        )

        const gridSize = 9

        func main() {
            // Example Sudoku puzzle (0 represents empty cells)
            puzzle := [9][9]int{
                {5, 3, 0, 0, 7, 0, 0, 0, 0},
                {6, 0, 0, 1, 9, 5, 0, 0, 0},
                {0, 9, 8, 0, 0, 0, 0, 6, 0},
                {8, 0, 0, 0, 6, 0, 0, 0, 3},
                {4, 0, 0, 8, 0, 3, 0, 0, 1},
                {7, 0, 0, 0, 2, 0, 0, 0, 6},
                {0, 6, 0, 0, 0, 0, 2, 8, 0},
                {0, 0, 0, 4, 1, 9, 0, 0, 5},
                {0, 0, 0, 0, 8, 0, 0, 7, 9},
            }

            fmt.Println("Original Sudoku Puzzle:")
            printGrid(puzzle)

            if solveSudoku(&puzzle) {
                fmt.Println("\nSolved Sudoku Puzzle:")
                printGrid(puzzle)
            } else {
                fmt.Println("\nNo solution exists for the given Sudoku puzzle.")
            }
        }

        func solveSudoku(grid *[9][9]int) bool {
            row, col, empty := findEmptyCell(grid)
            if !empty {
                return true // No empty cells, puzzle solved
            }

            for num := 1; num <= 9; num++ {
                if isValid(grid, row, col, num) {
                    grid[row][col] = num

                    if solveSudoku(grid) {
                        return true
                    }

                    grid[row][col] = 0 // Backtrack
                }
            }

            return false
        }

        func findEmptyCell(grid *[9][9]int) (int, int, bool) {
            for row := 0; row < gridSize; row++ {
                for col := 0; col < gridSize; col++ {
                    if grid[row][col] == 0 {
                        return row, col, true
                    }
                }
            }
            return -1, -1, false
        }

        func isValid(grid *[9][9]int, row, col, num int) bool {
            // Check row
            for x := 0; x < gridSize; x++ {
                if grid[row][x] == num {
                    return false
                }
            }

            // Check column
            for x := 0; x < gridSize; x++ {
                if grid[x][col] == num {
                    return false
                }
            }

            // Check 3x3 box
            startRow, startCol := row-row%3, col-col%3
            for i := 0; i < 3; i++ {
                for j := 0; j < 3; j++ {
                    if grid[startRow+i][startCol+j] == num {
                        return false
                    }
                }
            }

            return true
        }

        func printGrid(grid [9][9]int) {
            for _, row := range grid {
                for _, val := range row {
                    if val == 0 {
                        fmt.Print(". ")
                    } else {
                        fmt.Printf("%d ", val)
                    }
                }
                fmt.Println()
            }
        }

Explanation

This program uses the backtracking algorithm to solve the Sudoku puzzle. Here is the structure of the program:

1. Input: A 9×9 grid with empty cells represented by 0s.
2. findEmptyCell: Locates the next empty cell in the grid.
3. isValid: Checks whether placing a number in a specific cell is valid according to Sudoku rules.
4. solveSudoku: Recursively tries numbers in empty cells and backtracks if a solution is not found.
5. printGrid: Prints the grid in a human-readable format.

How to Run

1. Install Go from the official Go website.
2. Copy the code into a file named sudoku_solver.go.
3. Run the program using the command:

                   go run sudoku_solver.go
   

4. Observe the original and solved Sudoku grids in the terminal output.