# Stuck using backtracking

**URL:** <https://discourse.julialang.org/t/stuck-using-backtracking/107222>\
**Category:** New to Julia\
**Tags:** question\
**Created:** [December 6, 2023, 3:15pm UTC](https://discourse.julialang.org/t/stuck-using-backtracking/107222 "2023-12-06T15:15:44Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![bombusfragrans](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bombusfragrans/32/42685_2.png) [@bombusfragrans](https://discourse.julialang.org/u/bombusfragrans)\
**Post date:** [December 6, 2023, 3:15pm UTC](https://discourse.julialang.org/t/stuck-using-backtracking/107222/1 "2023-12-06T15:15:44Z")

</div>

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](https://en.wikipedia.org/wiki/Backtracking):

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

```julia
# 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!

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 6, 2023, 3:20pm UTC](https://discourse.julialang.org/t/stuck-using-backtracking/107222/2 "2023-12-06T15:20:28Z")

</div>

> [@bombusfragrans](#):
>
> ```julia
> 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)
> 
> ```

I think you still want to return `v` here, just without the last element. i.e.:

```julia
v[end] == 5 && (pop!(v); return v)

```

You might have to change the `while` condition too, to `isempty` or something like that.

---

<div class="post-metadata">

**Author:** ![bombusfragrans](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bombusfragrans/32/42685_2.png) [@bombusfragrans](https://discourse.julialang.org/u/bombusfragrans)\
**Post date:** [December 15, 2023, 9:15am UTC](https://discourse.julialang.org/t/stuck-using-backtracking/107222/3 "2023-12-15T09:15:04Z")

</div>

Many thanks!  
`v[end] == 5 && (pop!(v); return nothing)`  
did the trick!