local buffer = require "pluto:buffer"

class sudoku
    private grid, solved

    -- Use 0-based indexing for the grid.
    function __construct(rows)
        if #rows != 9 or !rows:checkall(|r| -> #r == 9) then
            error("Grid must be 9 x 9")
        end
        self.grid = {}
        for i = 0, 8 do
            for j = 0, 8 do self.grid[9 * i + j] = rows[i + 1][j + 1] end
        end
        self.solved = false
    end

    private function check_validity(v, x, y)
        for i = 0, 8 do
            if self.grid[y * 9 + i] == v  or self.grid[i * 9 + x] == v then
                return false
            end
        end
        local start_x = (x // 3) * 3
        local start_y = (y // 3) * 3
        for i = start_y, start_y + 2 do
            for j = start_x, start_x + 2 do
                if self.grid[i * 9 + j] == v then return false end
            end
        end
        return true
    end

    private function place_number(pos)
        if self.solved then return end
        if pos == 81 then
            self.solved = true
            return
        end
        if self.grid[pos] > "0" then
            self:place_number(pos + 1)
            return
        end
        for n = 1, 9 do
            if self:check_validity(tostring(n), pos % 9, pos // 9) do
                self.grid[pos] = tostring(n)
                self:place_number(pos + 1)
                if self.solved then return end
                self.grid[pos] = "0"
            end
        end
    end

    function solve()
        print($"Starting grid:\n\n{self}")
        self:place_number(0)
        print(self.solved ? $"Solution:\n\n{self}" : "Unsolvable!")
    end

    function __tostring()
        local sb = new buffer()
        for i = 0, 8 do
            for j = 0, 8 do
                sb:append(self.grid[i * 9 + j] .. " ")
                if j == 2 or j == 5 then sb:append("| ") end
            end
            sb:append("\n")
            if i == 2 or i == 5 then sb:append("------+-------+------\n") end
        end
        return sb:tostring()
    end
end

local rows = {
    "850002400",
    "720000009",
    "004000000",
    "000107002",
    "305000900",
    "040000000",
    "000080070",
    "017000000",
    "000036040"
}
new sudoku(rows):solve()