Use Backtracking to find all Palindromic Bitlists of a given length in Python

In this tutorial, we are going to take up the task of finding all the palindromic bitlists of a given length ‘n’ using the backtracking approach in Python. For this purpose, we first need to know what bitlists are.

A bitlist, as is evident from the name, is a list of bits or binary digits, i.e. 0 and 1. So any list of 0’s and 1’s is a bitlist. 

Thus, a palindromic bitlist is a bitlist that is also a palindrome, i.e., it is the same in both directions, forward and backward.

Now let’s talk about the approach that we are going to take, i.e.backtracking.

What is Backtracking?

The backtracking approach is a way of solving different kinds of problems by building upon the solution with every feasible option, i.e., removing the options that do not meet our required conditions. 

A general approach for backtracking is as follows:

• Find a representation of partial solutions such that all valid options to be augmented to a partial solution can be identified as well as when a partial solution becomes a complete solution.
• The task now is to find all the solutions that can be reached from a partial solution to a complete solution via a series of valid decisions.
• Construct all complete solutions via partial solutions using recurrence relation: sols(part)=sols(part+[a1])+…+sols(part+[ak]) where [a1,…,ak] are all valid options to augment part. 

For any backtracking problem, the general implementation in Python would look like this:

def solutions(completed, options, partial=[]):
    if completed(partial):
        return [partial]
    else:
        res = []
        for o in options(partial):
            augmented = partial+[o]
            res += solutions(completed, options, augmented)
        return res

def problem_to_be_solved(n):
    def options(partial):
        # options to be implemented
    def complete(partial): return len(partial) == n

    return solutions(complete, options)

In the above code, the only thing that needs to be implemented is the options function. The above code works in the following manner:

1. It starts off with an empty partial solution, 
2. It keeps building upon the partial solution using the options function which defines what solutions are feasible and removes the options that do not meet our requirement.
3. As soon as the partial solution meets the ‘completed’ requirement, it is appended to our final ‘solutions’.

How to find all palindromic bitlists of a given length using Backtracking?

For our task, we’ll use the above general implementation itself and define our ‘options’ function like this:

1. If the length of our partial solution is less than half the given length ‘n’ (in case of even ‘n’/ +1 in case of odd ‘n’): then we have both our options 0 and 1 feasible to be added to the partial solution.
2. Otherwise, we can only use the bit that was at the index [n-len(partial)-1], (for example: for n = 3, and partial = [0,0] we can’t use ‘1’ for the next element as it will not satisfy our condition of palindromic bitlists).

Implementing the code in Python

def solutions(completed, options, partial=[]):
    if completed(partial):
        return [partial]
    else:
        res = []
        for o in options(partial):
            augmented = partial+[o]
            res += solutions(completed, options, augmented)
        return res

def palindromic_bitlists(n):
    def options(partial):
        if len(partial)<n//2+n%2:
            return [0,1]
        return [partial[n-len(partial)-1]]
    def complete(partial): return len(partial) == n

    return solutions(complete, options, [])

Let’s run an example:

palindromic_bitlists(5)

Output:

[[0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 0, 0, 0, 1], [1, 0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 1, 1, 1, 1]]

Thank you for sparing your valuable time in order to read this article. You can check out other articles as well:

• Magic Square Identification in Python
• Find all Bridges of a Graph in Python