Iterative Backtracking

What is it?

It is an algorithm that tests all options for a problem. When there is a problem you go back to a previous situation. And from there you test out different options. A nice explanation can be found at opengenus .

Why?

Currently userdefined methods are not supported. So making a recursive function is a bit hard. Most recursive solutions are also possible to make using iterative proces using stacks to hold status information.

Is it an easy solution?

No. Conceptually a recursive solution is often much more elegant and the logic is more straightforward.

The basic working

How is an iteratve backtracking algorithm set up?

It is best to show

initializations

Put option 2 on stack
Put option 1 on stack

while stack [
    get last from stack
    set situation up for this option

    test valid / non valid solutions
    if not valid [
        continue (while)
    ]

    either at end [
        keep solution
        break (while)
    ][
        put option 2 on stack for next
        put option 1 on stack for next
    ]
]

write solution

A simple example program

This simple example program circulates through all binary numbers of 8 bit. It does skip some options.

Meta [
    file: binary-iteration.meta
]

MAX-LENGTH= 8
let current binary! MAX-LENGTH

; Stack keeps position and value/choice, 20 is MORE than enough(!)
let [stackposition stackvalue] binary! 20

byte! stackpointer
stackpointer: 0

increment stackpointer
poke stackposition stackpointer 1
poke stackvalue stackpointer 0
increment stackpointer
poke stackposition stackpointer 1
poke stackvalue stackpointer 1

while stackpointer [
    ; Get top of stack
    position: pick stackposition stackpointer
    value: pick stackvalue stackpointer
    decrement stackpointer

    ; Apply the value to the current position

    poke current position value

    ; Condition 1: "11" may not occur on first two positions

    if position = 1 [
        if all [1 = pick current 1
                1 = pick current 2][
            continue
        ]
    ]

    ; Condition 2: "101" may not occur on positions 2, 3 and 4

    if position = 4 [
        if all [1 = pick current 2
                1 = pick current 3
                1 = pick current 4][
            continue
        ]
    ]

    ; If at end, write the string

    either position = MAX-LENGTH [
        binary-string: ""
        for index MAX-LENGTH [
            binary-string: join/with binary-string to string! pick current index
        ]
        write/line binary-string
    ][
        ; Add next positions and options to the stack
        increment stackpointer
        poke stackposition stackpointer (position + 1)
        poke stackvalue stackpointer 0
        increment stackpointer
        poke stackposition stackpointer (position + 1)
        poke stackvalue stackpointer 1
    ]
]

That's it. For more see the Dutch Special page for Informatica Olympiade 2024-2025.