sidef-scripts/Game solvers/sudoku_solver_stack.sf

#!/usr/bin/ruby

# Solve Sudoku puzzle (iterative solution // stack-based).

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_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(board) {

    var stack = [board]

    while (stack) {

        var current_board = stack.pop
        var (row, col) = find_empty_location(current_board)

        if (!defined(row) && !defined(col)) {
            return current_board
        }

        for num in (1..9) {
            if (is_valid(current_board, row, col, num)) {
                var new_board = current_board.map { .clone }
                new_board[row][col] = num
                stack << new_board
            }
        }
    }

    return nil
}

# 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 false

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

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 {
    say "No solution exists."
}