Step 5 of 6
Paths through a grid
Grids are everywhere in puzzles and games: mazes, word searches, maps. Backtracking on a grid follows a path one cell at a time, trying each neighbor in turn. The one rule that makes it work: a path mustn't step on a cell it's already using, or it would walk in circles forever.
Unlike BFS in the graphs module, where a cell was marked "seen" once and for all, here a cell is only off-limits while it's part of the current path. When the search backs out of a cell, it unmarks it, because a different path may use that cell later. Mark on the way in, unmark on the way out: the same choose/un-choose pattern, applied to the grid itself.
This program counts every simple path (no cell used twice) from the top-left corner to the bottom-right, moving up, down, left or right, and avoiding walls (#):
#include <iostream>
#include <string>
#include <vector>
int paths(std::vector<std::string>& g, int r, int c) {
if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[r].size()) return 0; // off the grid
if (g[r][c] == '#' || g[r][c] == '*') return 0; // wall, or already on our path
if (r == (int)g.size() - 1 && c == (int)g[r].size() - 1) return 1; // reached the exit
char saved = g[r][c];
g[r][c] = '*'; // mark: we're standing here
int total = paths(g, r + 1, c) + paths(g, r - 1, c) + paths(g, r, c + 1) + paths(g, r, c - 1);
g[r][c] = saved; // unmark on the way back
return total;
}
int main() {
std::vector<std::string> maze = {
"...",
".#.",
"...",
};
std::cout << paths(maze, 0, 0) << " paths\n";
std::vector<std::string> open = {
"....",
"....",
"....",
};
std::cout << paths(open, 0, 0) << " paths\n";
}
2 paths
38 paths
How it works
- The checks at the top handle every reason to stop: off the grid, a wall, or a cell already on the current path. Checking before marking means callers can blindly try all four neighbors.
- The cell is marked with
*by writing into the grid itself, so no separate "visited" array is needed, and it's restored fromsavedbefore returning. - With the wall in the middle, only the two routes around it exist. The open 3 × 4 grid has 38, including long winding ones, because the search is exhaustive.
Word search
The same shape answers "is this word hidden in the grid?", the classic word-search puzzle where letters must be adjacent (up, down, left or right) and no cell is used twice. Start from every cell. From a cell, the search succeeds if the cell's letter matches the next letter of the word, and the rest of the word can be found starting from one of its neighbors. Mark the cell while exploring, so the path can't reuse it, and unmark it before returning.
Your turn: write exists(grid, word). It returns true if word can be traced through horizontally or vertically adjacent cells, using each cell at most once. The grid is passed by value, so you're free to mark cells in it.