Sudoku Solver in Go

This document outlines the implementation of a Sudoku solver using Go programming language. The solver uses the backtracking algorithm to fill in the correct digits for a partially filled Sudoku grid.

Program Structure

The program is divided into several sections:

1. Data Representation: The Sudoku board is represented as a 2D array (9×9 grid).
2. Validation: A helper function checks whether a move is valid according to the rules of Sudoku.
3. Backtracking Algorithm: The solver attempts to fill each empty cell with a number, backtracking when an invalid configuration is found.
4. Main Function: Initializes the board and calls the solver function.

Go Code Implementation

package main

import (
    "fmt"
)

// Sudoku board is represented as a 2D array of integers
var board [9][9]int = [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},
}

// isValid checks whether placing num at position (row, col) is valid.
func isValid(board [9][9]int, row, col, num int) bool {
    // Check the row
    for i := 0; i < 9; i++ {
        if board[row][i] == num {
            return false
        }
    }

    // Check the column
    for i := 0; i < 9; i++ {
        if board[i][col] == num {
            return false
        }
    }

    // Check the 3x3 sub-grid
    startRow := (row / 3) * 3
    startCol := (col / 3) * 3
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            if board[startRow+i][startCol+j] == num {
                return false
            }
        }
    }

    return true
}

// solveSudoku tries to solve the Sudoku using backtracking.
func solveSudoku(board *[9][9]int) bool {
    for row := 0; row < 9; row++ {
        for col := 0; col < 9; col++ {
            if board[row][col] == 0 {
                for num := 1; num <= 9; num++ {
                    if isValid(*board, row, col, num) {
                        board[row][col] = num
                        if solveSudoku(board) {
                            return true
                        }
                        board[row][col] = 0 // Backtrack if the current choice didn't work
                    }
                }
                return false // No valid number can be placed in this cell
            }
        }
    }
    return true // Solved the board
}

// printBoard prints the Sudoku board in a human-readable format
func printBoard(board [9][9]int) {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            fmt.Printf("%d ", board[i][j])
        }
        fmt.Println()
    }
}

func main() {
    fmt.Println("Initial Sudoku board:")
    printBoard(board)
    
    if solveSudoku(&board) {
        fmt.Println("\nSolved Sudoku board:")
        printBoard(board)
    } else {
        fmt.Println("\nNo solution exists!")
    }
}

Explanation of the Code

1. Data Representation

The Sudoku board is represented by a fixed-size 2D array of integers (`[9][9]int`). Each cell on the board either contains a number from 1 to 9 or 0 if it’s an empty cell that needs to be filled.

2. The `isValid` Function

This function checks if a number can be placed in a specific cell `(row, col)` without violating Sudoku rules. It performs the following checks:
– The number does not already exist in the same row.
– The number does not already exist in the same column.
– The number does not already exist in the 3×3 sub-grid containing the cell.

3. The `solveSudoku` Function

This function is the core of the backtracking algorithm. It:
– Iterates through each cell on the board.
– For every empty cell (`0`), tries every number from 1 to 9.
– If the number is valid (checked using the `isValid` function), it places the number and recursively attempts to solve the rest of the board.
– If a solution is found, it returns `true`; otherwise, it backtracks by resetting the current cell and trying the next number.

4. The `printBoard` Function

This function simply prints the board in a human-readable format.

5. The `main` Function

The main function initializes the board with a sample puzzle, prints the initial state, and attempts to solve the puzzle using the `solveSudoku` function. If a solution is found, it prints the solved board; otherwise, it indicates that no solution exists.

Conclusion

This Sudoku solver uses the backtracking algorithm to find the solution for a given board. It is a common and effective approach to solving constraint satisfaction problems like Sudoku. The Go code provided here can be further modified to include additional features like reading from user input or solving multiple puzzles in sequence.