sidef-scripts/Game solvers/sudoku_solver.sf

#!/usr/bin/ruby

# Recursive brute-force Sudoku solver.

# See also:
#   https://rosettacode.org/wiki/Sudoku
#   https://en.wikipedia.org/wiki/Sudoku

func check(i, j) is cached {
    var (id, im) = i.divmod(9)
    var (jd, jm) = j.divmod(9)

    jd == id && return true
    jm == im && return true

    (id//3 == jd//3) &&
    (jm//3 == im//3)
}

var lookup = []
for i in (^81), j in (^81) {
    lookup[i][j] = check(i, j)
}

func solve_sudoku(callback, grid) {

    var digits = @(1..9)

    func {
        grid.each_kv {|i,v|

            v && next
            var t = Set(grid.grep_kv {|j| lookup[i][j] }...)

            digits.each {|d|
                t.has(d) && next
                grid[i] = d
                __FUNC__()
                grid[i] = 0
            }

            return nil
        }

        callback(grid)
    }()
}

func display_grid(grid) {
    say "Solution:"
    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 sudoku_board = %n(
    5 3 0  0 2 4  7 0 0
    0 0 2  0 0 0  8 0 0
    1 0 0  7 0 3  9 0 2

    0 0 8  0 7 2  0 4 9
    0 2 0  9 8 0  0 7 0
    7 9 0  0 0 0  0 8 0

    0 0 0  0 3 0  5 0 6
    9 6 0  0 1 0  3 0 0
    0 5 0  6 9 0  0 1 0
)

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
) 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
) if false

solve_sudoku(display_grid, sudoku_board)