Solve with Backtracking

In a maze, walking until you hit a wall is not failure. It tells you that path does not work. You step back to the last junction and pick a different turn.

That step back is backtracking. Computers use it for puzzles, games and planning routes.

Use the maze solver lab. Watch the explorer mark tried paths, retreat when blocked, and try another branch.

Without memory you might walk in circles forever. Mark cells you already tried so you do not repeat the same mistake.

A stack of choices helps. Push each junction you enter. Pop when you backtrack. The top of the stack is where you try the next option.

You will meet stacks again in later CS topics. Here they are just a pile of places to revisit.

Backtracking fits puzzles with many choices and clear dead ends: sudoku, word searches in a letter grid, or finding a path through a maze when the first try hits a wall.

It can be slow if choices explode, but it is easy to understand and often good enough for small cases.

Next you will plan on paper before typing any code, combining break-down, trace and search habits.