Solving The Puzzle Box using Recursive Backtracking in Python

Topher Vizcarra — Sun, 01 Nov 2020 13:30:28 +0000

My partner and I absolutely love solving puzzles as our bonding moment. This Halloween, we decided to solve online Escape Room puzzles by Enchambered. Of all the puzzles we tried that night, the one that stood out the most for me was the mind-bending Puzzle #4. If you haven't tried it, I highly suggest you give it a go - Puzzle 4 Mystery Box.

The Puzzle

The board has numbers from 1 to 9 that are scrambled and four red buttons that divide the board into four quadrants.

Shifting the numbers

When one of the red buttons is clicked, the numbers surrounding the button are shifted in clockwise order.

Goal

On the left of the board, there is a hint implying that to get the key, we need to arrange the numbers in the given order.

It took my partner 5 minutes to solve the puzzle while it took me an hour before I finally gave up. Defeated, I found myself experiencing a puzzle-hangover the next day as I try to find a solution.

While I think there has to be a strategy to solve this similar to solving a Rubik's cube, I instead went for the brute-force approach of finding a solution by using Recursive Backtracking.

Recursive Backtracking

Geeks for Geeks defines backtracking as:

a general algorithmic technique that considers searching every possible combination to solve a computational problem.

Some popular applications of this algorithm are finding solutions for Sudoku, brute-forcing passwords, and path-finding in mazes.

Meanwhile, recursion is defined as:

the process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

Hence, we will be implementing a backtracking algorithm using recursion to search for a solution that will lead us to the desired state.

I find that the most tedious part of implementing this algorithm is representing the puzzle and the operations in code. However, once that is done, writing the general algorithm that does the actual solving is not that difficult at all.

Implement recursive backtracking once and it should be easy to re-use the pattern to solve similar puzzles.

Representing the puzzle

Note: The following code snippets you will see here are implemented using Python.

Board

We can start by representing the board using 2-dimensional arrays:

initial_board = [
    [7,6,5],
    [8,4,9],
    [3,2,1]
]

solved_board = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
]

Quadrants

Now, let's divide our board into 4 quadrants:

This will be helpful for us when we're representing the button operations that rotate the numbers into code.

In terms of array indices, the groupings are:

# Quadrant 1 -> [0,0], [0,1], [1,1], [1,0]
# Quadrant 2 -> [0,1], [0,2], [1,2], [1,1]
# Quadrant 3 -> [1,0], [1,1], [2,1], [2,0]
# Quadrant 4 -> [1,1], [1,2], [2,2], [2,1]

Rotations

Let us represent the button click operation. We start by defining how to shift in Quadrant 1:

from copy import deepcopy

# Operations
def shiftQuadrant1(originalBoard):
    board = deepcopy(originalBoard)
    board[0][0], board[0][1], board[1][1], board[1][0] = board[1][0], board[0][0], board[0][1], board[1][1]
    return board

Notice that we needed to import deepcopy so that we make a copy of the board instance instead of modifying the original board.

For reference, here is the difference between shallow copy vs deep copy:

A shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original. A deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original.

Also, notice how the clockwise rotation of the numbers can easily be implemented in Python as we leverage its simplicity of swapping variable values without explicitly defining a temporary variable.

# To switch values between a and in b in Python, we do:
# a, b = b, a
# In our case, we can do the clockwise shift of numbers by:
# board[0][0], board[0][1], board[1][1], board[1][0] = board[1][0], board[0][0], board[0][1], board[1][1]

Applying the same idea to the three other buttons, we will have the following functions:

def shiftQuadrant1(originalBoard):
    board = deepcopy(originalBoard)
    board[0][0], board[0][1], board[1][1], board[1][0] = board[1][0], board[0][0], board[0][1], board[1][1]
    return board

def shiftQuadrant2(originalBoard):
    board = deepcopy(originalBoard)
    board[0][1], board[0][2], board[1][2], board[1][1] = board[1][1], board[0][1], board[0][2], board[1][2]
    return board

def shiftQuadrant3(originalBoard):
    board = deepcopy(originalBoard)
    board[1][0], board[1][1], board[2][1], board[2][0] = board[2][0], board[1][0], board[1][1], board[2][1]
    return board

def shiftQuadrant4(originalBoard):
    board = deepcopy(originalBoard)
    board[1][1], board[1][2], board[2][2], board[2][1] = board[2][1], board[1][1], board[1][2], board[2][2]
    return board

Board Comparisons

Awesome! Now let's set up other functions that will help us out with comparison:

def isSolved(board):
    return areBoardsEqual(board, solved_board)

def areBoardsEqual(board1, board2):
    return board1 == board2

Solver: Recursive Backtracking

Now, let's talk about the actual implementation of Recursive backtracking.

We start by defining our initial state. Now, from that state, we have to explore the new states that we can arrive at if we perform one of the quadrant shift operations.

If you had experience implementing a searching algorithm before, then you probably have noticed that we are actually implementing Depth-First Search algorithm.

Solver: Pseudocode

Our recursive function will have the following steps:

Base case: Is the current board in a solved state? If yes, then terminate.
Call the solver function again, but this time, explore the new states achieved after shifting to Q1, Q2, Q3, and Q4 from the current state.

Attempt #1

Putting that into code, we will have:

def solve(board, stack):
    if(isSolved(board)):
        print("Solution: ", stack)

    solve(shiftQuadrant1(board), stack + ['Q1'])
    solve(shiftQuadrant2(board), stack + ['Q2'])
    solve(shiftQuadrant3(board), stack + ['Q3'])
    solve(shiftQuadrant4(board), stack + ['Q4'])

# Calling the function with initial value setup:
solve(initial_board, [])

Looks neat, right? Not quite. There's actually a problem with our algorithm.

One, our algorithm will get stuck to one of the states since we are not tracking if we have explored a state before.

For example, the search algorithm will try doing the shift with [Q1, Q1, Q1, Q1, ...] which returns it to the prior state.

To fix this, let's keep track of all the states of the board that we have already seen. This is done by having a variable to keep track of the explored states and pass it as a function parameter every time we explore a new one.

Attempt #2

Our new and improved function will look like this:

def isBoardInPastBoardStates(board, pastBoardStates):
    for state in pastBoardStates:
        if(areBoardsEqual(board, state)):
            return True
    return False

def solve(board, stack, pastBoardStates):
    if isBoardInPastBoardStates(board, pastBoardStates):
        return

    if(isSolved(board)):
        print("Solution: ", stack)

    solve(shiftQuadrant1(board), stack + ['Q1'], pastBoardStates + [board])
    solve(shiftQuadrant2(board), stack + ['Q2'], pastBoardStates + [board])
    solve(shiftQuadrant3(board), stack + ['Q3'], pastBoardStates + [board])
    solve(shiftQuadrant4(board), stack + ['Q4'], pastBoardStates + [board])

Notice how we added isBoardInPastBoardStates function to make sure we stop considering states if they were already explored.

However, our function is not complete yet.

If you run this, the algorithm will try the following shifting sequence: [Q1, Q1, Q1, Q2, Q1, Q1, Q1, Q2, Q1, Q1, Q1, Q2...] and so on. It will explore deeper on that branch while potentially missing out other viable solutions in other branches. What's our next step then?

Iterative Deepening Depth-First Search

Iterative Deepening Depth-First Search. That's a mouthful to read. Good thing it's also known as IDS or IDDFS.

While I do remember this search algorithm from my CompSci days, I wasn't conscious that I was using it when I was writing the solution until I looked it up online.

IDDFS combines depth-first search’s space-efficiency and breadth-first search’s fast search (for nodes closer to root).

How does IDDFS work?
IDDFS calls DFS for different depths starting from an initial value. In every call, DFS is restricted from going beyond given depth. So basically we do DFS in a BFS fashion.

This algorithm helps us find better candidate solutions. We can start by setting the maximum depth to be 1, 2, 3, and so on until we find the least depth that has a solution.

For simplicity's sake, I hard-coded the depth-limit named maxMoves and noticed that it's in-depth 11 where we first found a solution.

Final attempt: IDDFS

def solve(board, stack, pastBoardStates, maxMoves):
    if(len(stack) >= maxMoves):
        return

    if(isSolved(board)):
        print("Solution: ", stack)

    if isBoardInPastBoardStates(board, pastBoardStates):
        return

    solve(shiftQuadrant1(board), stack + ['Q1'], pastBoardStates + [board], maxMoves)
    solve(shiftQuadrant2(board), stack + ['Q2'], pastBoardStates + [board], maxMoves)
    solve(shiftQuadrant3(board), stack + ['Q3'], pastBoardStates + [board], maxMoves)
    solve(shiftQuadrant4(board), stack + ['Q4'], pastBoardStates + [board], maxMoves)

maxMoves = 11
solve(initial_board, [], [], maxMoves)

maxMoves represents the limit of our depth.

Putting it all together

from copy import deepcopy

initial_board = [
    [7,6,5],
    [8,4,9],
    [3,2,1]
]

solved_board = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
]

def isSolved(board):
    return areBoardsEqual(board, solved_board)

def areBoardsEqual(board1, board2):
    return board1 == board2

# Operations
def shiftQuadrant1(originalBoard):
    board = deepcopy(originalBoard)
    board[0][0], board[0][1], board[1][1], board[1][0] = board[1][0], board[0][0], board[0][1], board[1][1]
    return board

def shiftQuadrant2(originalBoard):
    board = deepcopy(originalBoard)
    board[0][1], board[0][2], board[1][2], board[1][1] = board[1][1], board[0][1], board[0][2], board[1][2]
    return board

def shiftQuadrant3(originalBoard):
    board = deepcopy(originalBoard)
    board[1][0], board[1][1], board[2][1], board[2][0] = board[2][0], board[1][0], board[1][1], board[2][1]
    return board

def shiftQuadrant4(originalBoard):
    board = deepcopy(originalBoard)
    board[1][1], board[1][2], board[2][2], board[2][1] = board[2][1], board[1][1], board[1][2], board[2][2]
    return board

def isBoardInPastBoardStates(board, pastBoardStates):
    for state in pastBoardStates:
        if(areBoardsEqual(board, state)):
            return True
    return False

attempt = 0
def solve(board, stack, pastBoardStates, maxMoves):
    global attempt
    attempt = attempt + 1

    if(len(stack) >= maxMoves):
        return

    if(isSolved(board)):
        print("Attempt: ", attempt, "Solution: ", stack)

    if isBoardInPastBoardStates(board, pastBoardStates):
        return

    solve(shiftQuadrant1(board), stack + ['Q1'], pastBoardStates + [board], maxMoves)
    solve(shiftQuadrant2(board), stack + ['Q2'], pastBoardStates + [board], maxMoves)
    solve(shiftQuadrant3(board), stack + ['Q3'], pastBoardStates + [board], maxMoves)
    solve(shiftQuadrant4(board), stack + ['Q4'], pastBoardStates + [board], maxMoves)

maxMoves = 11
solve(initial_board, [], [], maxMoves)

Running the code above, we arrive with the following solutions:

Attempt # 2472679 Solution:  ['Q2', 'Q4', 'Q3', 'Q4', 'Q1', 'Q3', 'Q1', 'Q3', 'Q2', 'Q3']
Attempt # 3452929 Solution:  ['Q3', 'Q3', 'Q4', 'Q1', 'Q2', 'Q2', 'Q2', 'Q3', 'Q3', 'Q1']
Attempt # 3467708 Solution:  ['Q3', 'Q3', 'Q4', 'Q2', 'Q1', 'Q1', 'Q3', 'Q3', 'Q1', 'Q2']
Attempt # 3621688 Solution:  ['Q3', 'Q4', 'Q2', 'Q1', 'Q3', 'Q1', 'Q3', 'Q2', 'Q1', 'Q3']
Attempt # 4340258 Solution:  ['Q4', 'Q2', 'Q3', 'Q1', 'Q1', 'Q2', 'Q1', 'Q3', 'Q1', 'Q3']

Solving the puzzle

Here's a GIF that solves the puzzle following the solutions found by our code:

Optimisation: Concurrency

Our code ran for almost 40 seconds to find 5 solutions. One way to improve its speed is by leveraging concurrency as it will enable us to explore multiple states in parallel, and consolidate all solutions discovered at the end.

If you want to access the raw code, you can find it in Github.

Thanks for reading!

If you know how to solve this problem logically, feel free to leave a comment. Happy solving!

PS. This article is not sponsored by Enchambered, but I do want to give them a huge shout out for building the Escape Room puzzles that I have thoroughly enjoyed solving with my friends.

Fin. 🐟

Routing to EC2 without EIP

Topher Vizcarra — Thu, 18 Jun 2020 16:08:52 +0000

TL;DR

Explicitly define that the aws_instance associates a public IP address and then create a Route 53 A record that points to the instance's public IP:


resource "aws_route53_record" "www" {
  zone_id = "..." # PlaceHosted zone ID here

  name    = "foo_subdomain"
  type    = "A"
  ttl     = "300"
  records = ["${aws_instance.foo.public_ip}"]
}

resource "aws_instance" "foo" {
  ...
  associate_public_ip_address = true
  ...
}
...

Where's the load balancer?

Ideally, you want to have a scalable setup where every service is containerised, put them in a private VPC, setup load balancer to handle public requests, and then setup routing for the requests to the services. Unfortunately, I had a setup where I was forced to create a pet server instead of cattle in a herd.

I needed to host a network management tool that required old-school ways of setting up and heavily relying on the state of the disk. To make my life harder it only worked for Ubuntu and it even required me to do a few custom configuration to make it work on the latest distro. 🤷 Luckily, the instance is unlikely to have insane traffic so I am not forced to setup a load balancer to handle scaling issues.

Since the software itself made it hard to containerise it, I needed to do some compromises. I made sure to harden the instance such as setting up the security group to restrict access to our office IP, and I only allowed shell access through AWS Session Manager. To improve fault-tolerance we setup Data Lifecycle Manager to take snapshots of the instance's EBS volume in regular intervals.

Why not use Elastic IPs (EIPs)?

To differentiate public IPs from EIPs:

Public IP addresses are dynamic - i.e. if you stop/start your instance you get reassigned a new public IP.

Elastic IPs get allocated to your account, and stay the same - it's up to you to attach them to an instance or not. You could say they are static public IP addresses.

EIPs are great for keeping a consistent public IP address. It works for use cases where you need to change the instances behind the IP.

For my use case, I don't really care if the public IP changed since I don't intend to change the instance every time. If it does change, I'll simply run terraform again to update the Route53 record with the new public IP of the instance.