ERROR: LoadError: StackOverflowError:

General Usage
1

I am trying to implement this algorithm of python for solving sudoku in Julia, but I am getting

ERROR: LoadError: StackOverflowError:
Stacktrace:
     [1] eliminate(values::Dict{String, String}, s::String, d::Char)
       @ Main c:\Users\dell\Desktop\FMDA\sud.jl:60
     [2] assign(values::Dict{String, String}, s::String, d::Char)
       @ Main c:\Users\dell\Desktop\FMDA\sud.jl:76
     [3] eliminate(values::Dict{String, String}, s::String, d::Char)
       @ Main c:\Users\dell\Desktop\FMDA\sud.jl:64
--- the last 2 lines are repeated 13750 more times ---
 [27504] assign(values::Dict{String, String}, s::String, d::Char)
       @ Main c:\Users\dell\Desktop\FMDA\sud.jl:76
 [27505] parse_grid(grid::String)
       @ Main c:\Users\dell\Desktop\FMDA\sud.jl:86
 [27506] solve(grid::String)
       @ Main c:\Users\dell\Desktop\FMDA\sud.jl:107

I am not able to debug it. I have started learning Julia few days back. Here is my code

function cross(A,B)
    [i*j for i in A for j in B]
end

digits = "123456789"
rows = "ABCDEFGHI"
cols = digits
squares = cross(rows, cols)

unitlist = (vcat(vcat([cross(rows, c) for c in cols],
            [cross(r, cols) for r in rows]) ,
            [cross(rs, cs) for rs in ("ABC", "DEF", "GHI") for cs in ("123", "456", "789")]))

units = Dict((s=> [u for u in unitlist if s in u]) for s in squares)

peers = Dict()
for s in squares
    unit_set = Set()
    for unit in units[s]
        for square in unit
            if square != s
                push!(unit_set,square)
            end
        end
    end
    peers[s]=unit_set
end

function test()
    @assert length(squares)==81
    @assert length(unitlist)==27
end
test()

function grid_values(grid)
    chars = [c for c in grid if c in digits || c in "0."]
    @assert length(chars)==81
    Dict(zip(squares,chars))
end

function eliminate(values,s,d)
    if ~(d in values[s])
        return values
    end

    values[s]=replace(values[s],d=>" ")
    if length(values[s])==0
        return false

    elseif length(values)==1
        d2=values[s]
        if ~ all(eliminate(values,s2,d2) for s2 in peers[s])
            return false
        end
    end

    for u in units[s]
        dplaces = [s for s in u if d in values[s]]
        if length(dplaces)==0
            return false
        elseif length(dplaces)==1
            if ~ assign(values,dplaces[1],d)
                return false
            end
        end
    end

    return values
end

function assign(values,s,d)
    other_values = replace(values[s],d=>" ")
    for d2 in other_values
        if length(eliminate(values,s,d2))==0
            return false
        end
    end
    return values
    
end
function parse_grid(grid)
    values = Dict((s=>digits) for s in squares)
    for (s,d) in grid_values(grid)
        if d in digits && length(assign(values,s,d))==0
            return false
        end
    end

    return values
end

function display(values)
    width = 1+max(length(values[s]) for s in squares)
    line="+".join(["-"*(width*3)]*3)
    for r in rows
        println("".join(values[r+c].center(width)))
        if r in "CF"
            println(line)
        end
    println()
    end
end

function solve(grid)
    search(parse_grid(grid))
end

function some(seq)
    for e in seq
        if e 
            return e
        end
    end
    return false
end

function search(values)
    if length(values)==0 
        return false
    end
    if all(length(values[s])==1 for s in squares)
        return values
    end
    l_min = 100 
    s_min=""
    for s in squares
        if length(values[s])<=l_min
            s_min=s
        end
    end
    some(search(assign(values,s_min,d)) for d in values[s_min])
end

grid1="4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
happy = solve(grid1)
print(happy)
2

Just a guess: did you mean ! instead of bitwise not ~?

3

StackOverflow problems often happen because you have a function that calls itself but there is no “reduction” between the values it receives and the values that it pass to call itself. The function call become an infinite loop (but as each call consumes a little of the stack it is interrupted when the finite stack is exhausted). In your case, it seems like eliminate calls itself with values that does not get closer to a stop condition at each call, or that one of the ifs that terminate eliminate before the recursive call is wrong.

1 Like