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
solverfunction 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. 🐟
Top comments (1)
Just awesome! gonna try it for my BitAim Application blog. Appropriated!