sidef-scripts/Game solvers/sudoku_solver_iterative.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 12 February 2024
# https://github.com/trizen

# Fast algorithm to solve a Sudoku puzzle (iterative solution).

func is_valid(board, row, col, num) {

    # Check if the number is not present in the current row and column
    for i in ^9 {
        if ((board[row][i] == num) || (board[i][col] == num)) {
            return false
        }
    }

    # Check if the number is not present in the current 3x3 subgrid
    var (start_row, start_col) = (3*idiv(row, 3), 3*idiv(col, 3))

    for i in ^3, j in ^3 {
        if (board[start_row + i][start_col + j] == num) {
            return false
        }
    }

    return true
}

func find_empty_locations(board) {

    var locations = []

    # Find all empty positions (cells with 0)
    for i in ^9, j in ^9 {
        if (board[i][j] == 0) {
            locations << [i, j]
        }
    }

    return locations
}

func find_empty_location(board) {

    # Find an empty position (cell with 0)
    for i in ^9, j in ^9 {
        if (board[i][j] == 0) {
            return (i, j)
        }
    }

    return (nil, nil)  # If the board is filled
}

func solve_sudoku_fallback(board) {

    var (row, col) = find_empty_location(board)

    if (!defined(row) && !defined(col)) {
        return true  # Puzzle is solved
    }

    for num in (1..9) {
        if (is_valid(board, row, col, num)) {
            # Try placing the number
            board[row][col] = num

            # Recursively try to solve the rest of the puzzle
            if (__FUNC__(board)) {
                return true
            }

            # If placing the current number doesn't lead to a solution, backtrack
            board[row][col] = 0
        }
    }

    return false  # No solution found
}

func solve_sudoku(board) {

    loop {
        var empty_locations = find_empty_locations(board) || break

        var found = false

        # Solve easy cases
        for i,j in empty_locations {
            var(count=0, value=0)
            for n in (1..9) {
                is_valid(board, i, j, n) || next
                break if (++count > 1)
                value = n
            }
            if (count == 1) {
                board[i][j] = value
                found ||= true
            }
        }

        next if found

        # Solve more complex cases
        var stats = []
        for i,j in empty_locations {
            stats[i][j] = (1..9 -> grep{|n| is_valid(board, i, j, n) })
        }

        var cols = []
        var rows = []
        var subgrid = []

        for i,j in empty_locations {
            stats[i][j].each {|v|
                cols[j][v] := 0 ++
                rows[i][v] := 0 ++
                subgrid[3*idiv(i,3)][3*idiv(j,3)][v] := 0 ++
            }
        }

        for i,j in empty_locations {
            stats[i][j].each {|v|
                if ((cols[j][v] == 1) ||
                    (rows[i][v] == 1) ||
                    (subgrid[3*idiv(i,3)][3*idiv(j,3)][v] == 1)
                ) {
                    board[i][j] = v
                    found ||= true
                }
            }
        }

        next if found

        # Give up and try brute-force
        solve_sudoku_fallback(board)
        return board
    }

    return board
}

# Example usage:
# Define the Sudoku puzzle as a 9x9 list with 0 representing empty cells
var sudoku_board = %n(
    2 0 0  0 7 0  0 0 3
    1 0 0  0 0 0  0 8 0
    0 0 4  2 0 9  0 0 5

    9 4 0  0 0 0  6 0 8
    0 0 0  8 0 0  0 9 0
    0 0 0  0 0 0  0 7 0

    7 2 1  9 0 8  0 6 0
    0 3 0  0 2 7  1 0 0
    4 0 0  0 0 3  0 0 0
).slices(9)

sudoku_board = %n(
    0 0 0  8 0 1  0 0 0
    0 0 0  0 0 0  0 4 3
    5 0 0  0 0 0  0 0 0

    0 0 0  0 7 0  8 0 0
    0 0 0  0 0 0  1 0 0
    0 2 0  0 3 0  0 0 0

    6 0 0  0 0 0  0 7 5
    0 0 3  4 0 0  0 0 0
    0 0 0  2 0 0  6 0 0
).slices(9) if true

sudoku_board = %n(
    8 0 0  0 0 0  0 0 0
    0 0 3  6 0 0  0 0 0
    0 7 0  0 9 0  2 0 0

    0 5 0  0 0 7  0 0 0
    0 0 0  0 4 5  7 0 0
    0 0 0  1 0 0  0 3 0

    0 0 1  0 0 0  0 6 8
    0 0 8  5 0 0  0 1 0
    0 9 0  0 0 0  4 0 0
).slices(9) if false

sudoku_board = %n(
    0 0 1  0 6 0  0 5 9
    0 0 0  0 0 3  0 2 0
    0 6 0  0 8 0  0 0 0

    4 0 0  0 0 0  5 0 0
    0 2 0  0 0 0  0 0 0
    0 7 0  2 0 0  4 8 0

    8 0 0  0 0 0  9 0 5
    7 0 0  6 0 9  0 3 0
    0 0 5  0 0 0  0 4 0
).slices(9) if false

func display_grid(grid) {
    for i in ^grid {
        print "#{grid[i]} "
        print " "  if ( 3 -> divides(i+1))
        print "\n" if ( 9 -> divides(i+1))
        print "\n" if (27 -> divides(i+1))
    }
}

var solution = solve_sudoku(sudoku_board)

if (solution) {
    display_grid(solution.flat)
}
else {
    warn "No unique solution exists."
}