paint-brush
An Introduction to Backtracking in Rubyby@Tresor-bireke
760 reads
760 reads

An Introduction to Backtracking in Ruby

by Tresor birekeMay 8th, 2020
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems notably constrain satisfaction problems. It incrementally builds candidates to the solutions, abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. In this blog post, we are going to take a look at what is backtracking and how to implement it using ruby. We will be given a tow input where the first number is the desired sum and the remaining is an array of numbers.

Company Mentioned

Mention Thumbnail

Coin Mentioned

Mention Thumbnail
featured image - An Introduction to Backtracking in Ruby
Tresor bireke HackerNoon profile picture

in this blog post, we are going to take a look at what is backtracking and how to implement it using ruby

First thing first what is backtracking? according to wikipedia Backtracking is a general algorithm for finding all (or some) solutions to some computational problem notably constrain satisfaction problems that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

To understand what backtracking is let's take a problem and try to solve it using backtracking.

we will be given a tow input where the first number is the desired sum and the remaining is an array of numbers. Determine if the array or any of its sub-arrays can be summed to get the exact sum

analyzing the above problem here are the steps we want to follow to solve the problem

    1. Implement the recursive function to find all the possible sub-arrays recursively.
    2.  Follow backtracking strategy and implement required base-cases to process each recursive level.
    3. subtract the first element of every sub-array to the sum and return true if the sum is 0 and return false if the sum is less than 0 or the array is empty.

    since our steps seem complete let's take a sample case

    def exact_sum?(sum, arr)
    return true if sum==0
    return false if sum < 0 || arr.empty?
    exact_sum?(sum - arr[0], arr[1,arr.length])
    end
    
    puts exact_sum?(12, [1, 2, 3, 4, 5]);
    # expected result => true
    # actual resut => false

    looking at the input you can see that if you remove 3 from the array and try to sum it you will get 12 but why do we get false? well the answer is that our above still recursive so we need to make it backtracking and the way to do that is by checking both cases where we include the first element and when we don't

    By doing that here's how the flow of our algorithm should look like

    let's include a variable K representing our sum and see how it would work

    let's implement that in our previous algorithm

    def exact_sum?(sum, arr)
    return true if sum==0
    return false if sum < 0 || arr.empty?
    # now we are checking both cases
    exact_sum?(sum - arr[0], arr[1,arr.length]) || exact_sum?(sum, arr[1,arr.length])
    end
    
    puts exact_sum?(12, [1, 2, 3, 4, 5]);
    # => true

    by adding a or statement the algorithm will be checking both cases and will become a backtracking algorithm but this still a little bit confusing let's print the values to fully understand the flow of our algorithm

    # the algorithm start
    [1, 2, 3, 4, 5]12
    # check for the first condition : 12-1 is not less than 0 so we subtract it from the sum
    [2, 3, 4, 5]11
    # check again 11-2 > 0 is true so we proceed
    [3, 4, 5]9
    # same thing here
    [4, 5]6
    # here 2-5 will return false so we go back to the parent call([4,5]6) and try to exclude the first case without touching the sum
    [5]2
    # we still get false because the array will be empty and the sum will be 1 so go back to the ancestor call([3,4,5]9)and exclude the first element without touching the sum
    [5]6
    # 9-4 > 0 is true so we proceed
    [4, 5]9
    # 5-5 is 0 so we return true
    [5]5
    true

    And Voila!!! just with those few lines of code we have implemented a backtracking algorithm.

    Thank you for reading If you have any question or suggestion contact me on Twitter