Hello.
To improve my skills I am experimenting with backtracking as a potential approach to solve a verbal arithmetic (alphametics) puzzle.
As a starting point I tried to develop a simple implementation of a backtracking algorithm as described on the Wikipedia:
# just for testing purposes the backtracking should guess a sequence of numbers containing no duplicates (here: `[5,3,1]`)
# the procedures / functions are named (abbreviated) according to the nomenclature on the Wikipedia page
# the 'reject' procedure:
# "returns true only if the partial candidate [sequence] is not worth completing"
# here: rejects sequences with duplicates (prunes branches)
r(v::Vector) = !allunique(v)
# the 'accept' procedure:
# "returns true if a candidate [sequence] is a solution"
a(v::Vector) = v == [5,3,1] # to keep it simple just a comparison of a candidate sequence against a predetermined solution
# the 'first' procedure:
# "generates the first extension of a candidate [sequence]"
f(v::Vector) = length(v) == 3 ? nothing : append!(v,0) # to keep it small the solution can consist of max. 3 numbers (a.k.a. 'n')
# the 'next' procedure:
# "generates the next alternative extension of a candidate [sequence]"
function n(v::Vector)
v[end] == 5 && return nothing # again, to keep it small the range of possible numbers is restricted to 0-5 (a.k.a. 'm'; 'first' / `f()` sets lower boundary)
v[end] += 1
return v
end
# the main 'backtracking' procedure:
# numbered `@show()` (1-3) to be able to follow along
function bt(v::Vector)
@show((1, v))
r(v) && return
a(v) && return "bingo"
s = f(v)
@show((2, s))
while !isnothing(s) # same results with `s != nothing`
bt(s)
s = n(s)
@show((3, s))
end
end
bt([])
The procedure does not find a solution and returns nothing.
The outputs of @show show that the backtracking enters the first ‘subtree/branch’ and then terminates early before even exploring other ‘subtrees/branches’ like [1,...], [2,...], [3,...], etc or even [0,2,...], [0,3,...], etc… (seems like the while loop does not continue)
# outputs of `@show` (1-3):
(1, v) = (1, Any[])
(2, s) = (2, Any[0])
(1, v) = (1, Any[0])
(2, s) = (2, Any[0, 0])
(1, v) = (1, Any[0, 0])
(3, s) = (3, Any[0, 1])
(1, v) = (1, Any[0, 1])
(2, s) = (2, Any[0, 1, 0])
(1, v) = (1, Any[0, 1, 0])
(3, s) = (3, Any[0, 1, 1])
(1, v) = (1, Any[0, 1, 1])
(3, s) = (3, Any[0, 1, 2])
(1, v) = (1, Any[0, 1, 2])
(2, s) = (2, nothing)
(3, s) = (3, Any[0, 1, 3])
(1, v) = (1, Any[0, 1, 3])
(2, s) = (2, nothing)
(3, s) = (3, Any[0, 1, 4])
(1, v) = (1, Any[0, 1, 4])
(2, s) = (2, nothing)
(3, s) = (3, Any[0, 1, 5])
(1, v) = (1, Any[0, 1, 5])
(2, s) = (2, nothing)
(3, s) = (3, nothing)
(3, s) = (3, nothing)
(3, s) = (3, nothing)
What am I doing wrong? I guess, it is probably something obvious, but even after considerable time experimenting I am not able to see it. (e.g. I do not understand why the while loop would exit early.)
I would gratefully appreciate if someone could kindly point me in the right direction.
I apologize should this be the wrong channel for this kind of questions. I consider myself still being fairly new to Julia.
Also my searches on backtracking did not return something that I would have associated with a potential (if only a partial) solution to my confusion.
Thanks for your time in advance!