Lab 17 – Recursive Backtracking

Due by 11:59pm on November 6, 2025

This lab is all about recursive backtracking so that you’re ready to apply all of these concepts in Project 3. Download the starter files to get started lab17.zip.

Topics

Recursive Backtracking

So far, you’ve seen how recursion can help break a problem into smaller subproblems. Sometimes, recursion isn’t just about solving one subproblem at a time—it’s about exploring all possible paths toward a solution, even backing up and trying a different path if the first one doesn’t work. This idea is called recursive backtracking.

Backtracking is a powerful technique often used in problems that ask:

Can I find a solution?
How many solutions are there?
What’s one way to solve this puzzle?

Here’s the general idea:

Try a choice.
Recursively explore the consequences of that choice.
If it leads to a solution, great!
If it doesn’t lead to a solution, undo the choice and try something else.

This “try → explore → undo” cycle makes it perfect for problems like:

Finding a path through a maze.
Solving a Sudoku puzzle.
Placing queens on a chessboard.
Searching for words in a grid.

A Simple Example

Let’s say we want to count how many different ways we can climb a ladder with n rungs if we can take either 1 or 2 steps at a time. This problem is a good warmup for recursive thinking, and the recursive structure looks similar to backtracking, but it doesn’t need to “undo” steps since all paths are valid.

def count_ways(n):
    if n == 0:
        return 1
    if n < 0:
        return 0
    return count_ways(n - 1) + count_ways(n - 2)

This function tries two choices (take 1 or 2 steps), and adds up the number of ways each choice can lead to a solution.

When Backtracking Shines

Now let’s say not all choices are valid. For example:

You’re in a grid of letters, trying to spell a word by moving up/down/left/right, but you can’t reuse the same square twice.
You’re solving a puzzle with constraints (like no two pieces can overlap).

This is where backtracking becomes important. At each step, we try a move, check if it’s allowed, and if it doesn’t lead to a solution, we back up and try something else.

Required Questions

You’re given a 2D list of single uppercase letters and a target word. Your task is to write a recursive function to determine if the word can be constructed by starting at any cell and moving to adjacent cells (up/down/left/right) — no diagonals, and you can’t reuse the same cell twice.

Here’s a sample grid (test_files/grid1.txt):

CAT
RRE
DOG

You should be able to find “CAR”, “CAT”, and “DOG”, but not “CART” (not enough R’s).

Q1 – Load the Grid

Write a function to read a file like test_files/grid1.txt and convert it into a 2D list of characters. Each line contains uppercase letters.

Example:

[
 ['C', 'A', 'T'],
 ['R', 'R', 'E'],
 ['D', 'O', 'G']
]

Write a function load_grid(filename) that:

Takes a file path
Returns a 2D list of letters

The function signature should be as follows:

def load_grid(filename):
    ...

Important
Make sure that you name your function load_grid() or the autograder will be unable to give you an accurate score.

You can test it with:

pytest -vv test_lab17.py::test_load_grid

Q2 – Recursive Search

Write a recursive function that searches for a word in the grid. Your function should:

Start at any cell that matches the first letter.
Move up/down/left/right to the next matching letter.
Keep track of visited cells so you don’t reuse them.
Return True if the word is found, False otherwise.

Your function signature should look like:

def exists(grid, word):
    ...

Important
Make sure that you name your function exists() or the autograder will be unable to give you an accurate score.

You may want to use a helper like:

def search_from(grid, word, row, col, visited):
    ...

You can test your function with:

pytest -vv test_lab17.py::test_exists_1
pytest -vv test_lab17.py::test_exists_2

Hints

Use a 2D boolean array for tracking your visited cells.

Be careful with edge conditions: don’t go off the grid!

When backtracking, make sure to unmark the cell as visited.

Submission

Submit your word_search.py file to Gradescope through Canvas.

Lab 17 - Recursive Backtracking