Sliding Puzzle
Identifying Problem Isomorphism
The problem “Sliding Puzzle” can be mapped to “Open the Lock”.
Reasoning:
Both problems are based on state space search where you have to transform from an initial state to a target state with minimum moves. They use BreadthFirst Search (BFS) to solve the problem. “Open the Lock” is a simpler problem as it only involves unlocking a lock with 4 wheels where each wheel can be turned one step at a time. On the other hand, “Sliding Puzzle” is a bit more complex as it involves more potential states and movements.
This code first converts the 2D board into a string to easily represent each state. It then creates a dictionary to keep track of the minimum moves to reach each state. A queue is used to perform BFS, exploring all the possible moves from the current state. The neighbor of ‘0’ is swapped if it is valid to do so and if this new state has not been seen before, it is added to the queue and the moves dictionary. The process continues until we reach the goal state or all states have been explored (in which case the puzzle is unsolvable, and we return 1).


Decomposing large functions into smaller ones can make the code easier to understand and maintain. We could refactor the above solution as follows:


Here, we have two helper functions:
board_to_string
: This function converts the 2D board into a string representation.get_possible_moves
: This function calculates all possible moves from a given state and returns them as a list of strings.
By refactoring the code into smaller functions, we have made the main function, slidingPuzzle
, much simpler and easier to understand. Each helper function encapsulates a specific operation, which makes the code easier to debug and maintain.
Extracting operations encapsulated in comments to separate methods can increase the readability of the code. Here is the refactored version:


The previous solution was refactored into several additional smaller methods:
find_zero_index
: This method finds the index of the empty tile, i.e., ‘0’, in the current state.generate_new_states
: This method generates all possible new states from a given state and zero position.is_valid_move
: This method checks whether a particular move is valid or not.make_move
: This method generates a new state after making a move in a particular direction.
This way, each method is selfexplanatory and encapsulates a single logic unit, making the overall code more readable and maintainable.
Problem Classification
This problem is related to the domain of “Artificial Intelligence and Search Algorithms”.
Here’s a breakdown of the ‘What’ components:
Initial State: We are given a 2x3 puzzle board where there are five tiles labelled from 1 to 5 and an empty square represented by 0.
Goal State: The state of the board is considered solved if and only if the board is [[1,2,3],[4,5,0]].
Rules/Constraints: A move consists of choosing 0 and a 4directionally adjacent number and swapping it. Each value board[i][j] is unique.
Objective: The goal is to determine the least number of moves required so that the state of the board is solved.
This is a classic example of a search problem in the AI domain. Specifically, this falls under “Informed Search” as we have a specific goal state to reach. A wellknown algorithm to solve such a problem is the “A* Search Algorithm”, which uses a heuristic function to estimate the cost (i.e., number of moves) to reach the goal state from a given state.
Another way to categorize this problem is as a “Pathfinding” problem. We are looking for the shortest path (fewest moves) to transform the initial state of the puzzle board into the goal state. The problem constraints limit the possible actions at each step (i.e., the 0 can only swap with an adjacent number), which makes this a constrained pathfinding problem.
Thought Process
The problem is a classic example of a search problem. In this case, it’s similar to the famous “8puzzle” problem but with a smaller grid of size 2x3. The cue that this is a search problem comes from the fact that we are given a start state (the initial configuration of the board) and a goal state (the desired configuration of the board), and we are asked to find the least number of moves to get from the start to the goal.
Here’s a step by step thought process:
Understanding the Problem: The first step is to understand the problem and its constraints. We are given a 2x3 grid with the tiles numbered from 0 to 5. We need to find the minimum number of moves to reach the goal state [[1,2,3],[4,5,0]] by swapping 0 with its adjacent tiles.
Formulating the Problem: This is a search problem where we need to find a path from the start state to the goal state. Each state of the problem can be represented by the configuration of the board and each operation corresponds to swapping 0 with one of its adjacent tiles.
Choosing the right data structures: In order to keep track of the states we have visited and the states we need to visit, we can use a set (for storing visited states) and a queue (for storing the states to visit next).
Designing the Search Algorithm: A Breadthfirst search (BFS) algorithm can be used to explore the search space because BFS guarantees to find the shortest path in terms of the number of moves. The search ends when we reach the goal state.
Implementing the Solution: Implementation of BFS requires an understanding of how to manipulate and represent states and operations in the code.
Language Agnostic Coding Drills
 Dissect the code and identify each distinct concept it contains
Here are the distinct coding concepts found in this code:
Variable initialization and assignment: This is fundamental to any programming language. It’s about declaring variables and assigning them values.
Data structure: This involves using data structures to hold values. In this code, we use lists and dictionaries.
Iterables and loops: This concept is about iterating over collections of elements using loops, like the
for
loop or while loop.String manipulation: This concept involves manipulating strings, like converting an integer to a string, joining strings, or accessing a character at a specific index in a string.
Functions/Methods: This involves defining and calling functions or methods. Functions or methods are blocks of reusable code that perform a particular action.
Control flow: This is about making decisions in the code using control flow structures like
ifelse
statements.Breadthfirst search (BFS): This is an algorithm for traversing or searching tree or graph data structures.
Order these coding concepts or drills in order of increasing difficulty
 Variable initialization and assignment
 Control flow
 Iterables and loops
 Data structure
 String manipulation
 Functions/Methods
 Breadthfirst search (BFS)
The above order is set according to the usual learning curve of a beginner coder, starting from basic variable assignments to more complex data structure manipulation and BFS usage.
 Describe the problemsolving approach that would lead from the problem statement to the final solution
The problem can be approached using the BreadthFirst Search (BFS) algorithm, which is widely used in graphbased problems.
First, we need to convert our given 2D grid into a string representation. This string will be the starting state of our problem.
Our goal is to reach the state where the string is “123450”.
BFS begins from the start state and explores all the neighboring states at the present depth prior to moving on to nodes at the next depth level.
For each state, generate all possible states and push them into the queue to be processed, if they haven’t been processed before.
While processing each state, if we reach our target state, we return the number of moves it took to get there, as that would be the shortest number of moves.
If we can’t reach the goal state after processing all possible states, then we return 1 as the puzzle is unsolvable.
Each of the coding drills identified contributes to different parts of the solution. Control flow, variable initialization, and assignment are used throughout the solution. String manipulation and data structures are used to transform the board and to store the states and their distances. Functions/methods are used to encapsulate repeated tasks. And finally, BFS is the main algorithm used to solve the problem.
Targeted Drills in Python
Pythonbased coding drills for each identified concept
 Variable initialization and assignment
1 2 3 4 5 6 7
# variable initialization x = 5 print(x) # output: 5 # variable assignment x = 10 print(x) # output: 10
 Control flow
1 2 3 4 5
x = 10 if x > 5: print("x is greater than 5") # output: x is greater than 5 else: print("x is not greater than 5")
 Iterables and loops
1 2 3 4
# using for loop to iterate over a list my_list = [1, 2, 3, 4, 5] for i in my_list: print(i)
 Data structure
1 2 3 4 5
# list my_list = [1, 2, 3, 4, 5] # dictionary my_dict = {'apple': 1, 'banana': 2}
 String manipulation
1 2 3 4 5 6 7 8 9
my_str = '123' # convert a string to a list my_list = list(my_str) print(my_list) # output: ['1', '2', '3'] # convert a list to a string my_str = ''.join(my_list) print(my_str) # output: '123'
 Functions/Methods
1 2 3 4
def my_func(x, y): return x + y print(my_func(3, 4)) # output: 7
 Breadthfirst search (BFS)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
# Assuming a graph is a dictionary where the keys are the nodes and the values are lists of connected nodes. graph = { 'A' : ['B','C'], 'B' : ['D', 'E'], 'C' : ['F'], 'D' : [], 'E' : ['F'], 'F' : [] } visited = [] # List for visited nodes. queue = [] # Initialize a queue def bfs(visited, graph, node): # Function for BFS visited.append(node) queue.append(node) while queue: # Creating loop to visit each node m = queue.pop(0) print (m, end = " ") for neighbour in graph[m]: if neighbour not in visited: visited.append(neighbour) queue.append(neighbour) # Driver Code bfs(visited, graph, 'A') # Returns A B C D E F
Problemspecific concepts
 Converting 2D board into a string representation
1 2 3
board = [[1, 2, 3], [4, 0, 5]] board_str = ''.join(str(num) for row in board for num in row) print(board_str) # output: '123405'
 Generating all possible moves from a given state (assuming board is a list of characters representing the state)
1 2 3
moves = [(1, 0), (1, 0), (0, 1), (0, 1)] # up, down, left, right zero_index = board.index('0') zero_row, zero_col = div
mod(zero_index, 3)
for dx, dy in moves:
new_row, new_col = zero_row + dx, zero_col + dy
if 0 <= new_row < 2 and 0 <= new_col < 3: # Check if the move is within the board
new_board = list(board)
new_board[zero_index], new_board[new_row*3 + new_col] = new_board[new_row*3 + new_col], new_board[zero_index]
print(new_board)
```
 Integrating the pieces
Once all drills are understood, they can be integrated into a cohesive solution. First, you would initialize your variables (the starting state, queue, and visited set). Then, using a while loop, you would dequeue a state from the queue, check if it’s the target, and if not, generate all valid neighboring states (using the problemspecific concepts drill). For each valid neighboring state that you haven’t visited before, you add it to the visited set and enqueue it with a distance one greater than the current state. You continue this process until you either reach the target state (at which point you return its distance) or exhaust all states (return 1).