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)
``````

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

`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 `if`s that terminate `eliminate` before the recursive call is wrong.

1 Like