[Algorithm Technique] Backtracking + The Boggle Problem (Leetcode Medium)

To watch the video explaining this topic, please click here.

Backtracking

Backtracking is a technique when using recursion (DFS). The trick is:

1. Pass a variable around by reference (not by copy).
2. Edit the variable -> Make a recursive call -> Undo the edit.

​Basically, because DFS is deterministic and goes in a "depth-first" order, at each level we can edit information, which keeps the "state" of our system the way we need it to for the next level's recursive calls, and then we can undo the change we made for whenever we go back up to the previous level.

A good analogy of this is a kitchen. Pretend we have a kitchen that only one person is going to use at a time.

• Our mom owns the kitchen.
  • Our mom let's us use the kitchen.
  • We eat some cheese and crackers.
    • We let our friend use the kitchen.
    • Our friend uses some dishes.
    • Our friend washes those dishes.
    • Our friend stops using the kitchen and returns ownership to us.
  • We retake ownership of the kitchen.
    • We let our dad use the kitchen.
    • Our dad eats some cookies.
      • Our dad lets our uncle use the kitchen.
      • Our uncle turns the oven on.
      • Our uncle turns the oven off.
      • Our uncle stops using the kitchen and returns ownership to our dad.
    • Our dad buys some cookies to replace what he ate.
    • Our dad stops using the kitchen and returns ownership to us.
  • We buy cheese and crackers to replace what we ate.
  • We return ownership of the kitchen to our mom.
• Our mom gets the kitchen back in the exact condition she returned it to us.

As long as each person undoes the change they do when they return ownership to the person who let them use it, we can all use the same kitchen, instead of every person needing to have their own kitchen.

Similarly, using backtracking in DFS means we can have shared variable without having to create a new one for each recursive call. This saves time and memory.

---

[Leetcode Medium] Word Search (Boggle Problem)

Given a 2D board of tiles (letters) and a word, check if the word exists in the board.

• You may start from any tile.
• You can only travel to adjacent (up/down/left/right) tiles.
• You cannot reuse any tiles.

 (Problem on Leetcode.)

---

---

Backtracking Solution

We'll try each tile as the beginning of our traversal, and what we'll recursively do is:

1. Check if the tile is valid. (In-bounds in the board ,​and matches the character in the word.)
2. Invalidate that tile by changing it to an invalid character, like "*". (Which we know will never be in our input.)
3. Recursively check the left, right, up, and down tiles.
4. Undo the tile invalidation from step 2.
5. Return the true if this tile was the end of the word or if any of the recursive calls returned true.

The "backtracking" part of this solution is that we're changing shared state (step 2), making recursive calls, and then undoing our change for when we go back up to previous levels.

Here's pseudocode for our solution to the boggle problem:

---

Full Code (C++)

The full C++ code, which corresponds to the "Word Search" problem on Leetcode, is as follows:

​​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake