sidef-scripts/Game solvers/sudoku_solver_backtracking.sf

#!/usr/bin/ruby

# Solve Sudoku puzzle (recursive 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_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 (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
}

# 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))
    }
}

if (solve_sudoku(sudoku_board)) {
    display_grid(sudoku_board.flat)
}
else {
    say "No solution exists."
}