Introduction

Filling a 2D grid with a single path usually means visiting every cell exactly once without branching. In graph terms, that is a Hamiltonian path on the grid graph, and the right solution depends on whether the grid is empty, whether obstacles exist, and whether the start and end cells are fixed.

Model the Grid as a Graph

A rectangular grid can be treated as a graph where each cell is a node and each valid up, down, left, or right move is an edge. A "single path" means:

• every chosen cell appears exactly once
• consecutive cells are adjacent
• the path has no forks or revisits

For an empty rectangular grid, a simple snake-like traversal already solves many cases.

For example, a 3 x 4 grid can be filled like this:

1(0,0) (0,1) (0,2) (0,3)
2                        |
3(1,0) (1,1) (1,2) (1,3)
4|
5(2,0) (2,1) (2,2) (2,3)

The path moves left-to-right across one row, then right-to-left across the next, and so on.

Simple Construction for an Empty Grid

If you only need one valid path for an obstacle-free grid, a row-wise snake pattern is the simplest construction.

1def snake_path(rows, cols):
2    path = []
3    for r in range(rows):
4        if r % 2 == 0:
5            for c in range(cols):
6                path.append((r, c))
7        else:
8            for c in range(cols - 1, -1, -1):
9                path.append((r, c))
10    return path
11
12
13for cell in snake_path(3, 4):
14    print(cell)

This runs in O(rows * cols) time and is often enough for animation, puzzle generation, or deterministic traversal problems where there are no blocked cells.

A column-wise snake pattern works just as well if that matches your output format better.

When the Problem Gets Hard

The problem becomes much harder when any of these conditions apply:

• some cells are blocked
• the path must start and end at specific cells
• diagonal movement is forbidden and only some shapes are allowed
• the path must also satisfy extra puzzle constraints

At that point, the question is no longer "how do I print a traversal" but "does a Hamiltonian path exist at all for this grid configuration."

For arbitrary blocked grids, there is no simple universal pattern like the snake traversal. A search algorithm is usually required.

Backtracking Search

A standard approach is depth-first search with backtracking. You place one cell on the path, mark it visited, and recursively try the next legal moves.

1DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
2
3
4def find_single_path(grid, start):
5    rows = len(grid)
6    cols = len(grid[0])
7    total_open = sum(cell == 0 for row in grid for cell in row)
8    visited = set()
9    path = []
10
11    def dfs(r, c):
12        visited.add((r, c))
13        path.append((r, c))
14
15        if len(path) == total_open:
16            return True
17
18        for dr, dc in DIRECTIONS:
19            nr, nc = r + dr, c + dc
20            if 0 <= nr < rows and 0 <= nc < cols:
21                if grid[nr][nc] == 0 and (nr, nc) not in visited:
22                    if dfs(nr, nc):
23                        return True
24
25        visited.remove((r, c))
26        path.pop()
27        return False
28
29    return path if dfs(*start) else None
30
31
32grid = [
33    [0, 0, 0],
34    [0, 1, 0],
35    [0, 0, 0],
36]
37
38print(find_single_path(grid, (0, 0)))

Here 0 means open and 1 means blocked. This code is practical for small grids, but the search space grows very quickly as the grid size increases.

Useful Heuristics

Because naive backtracking can explode combinatorially, small heuristics help a lot:

• try cells with fewer onward moves first
• detect disconnected open regions early
• stop immediately if an unvisited cell becomes isolated
• choose endpoints with odd degree constraints in mind

These ideas do not change the worst-case difficulty, but they make real puzzle-sized cases much easier to solve.

For empty rectangular grids, though, you should not use search when a direct construction already works. Search is for constrained variants, not the easiest version of the problem.

Common Pitfalls

• Treating every grid as a shortest-path problem when this is really a visit-every-cell problem.
• Using brute force on empty rectangles where a simple snake construction is enough.
• Forgetting that obstacles can make a Hamiltonian path impossible.
• Not marking and unmarking visited cells correctly during backtracking.
• Assuming that one valid path implies every start and end pair is possible.

Summary

• A single path through every grid cell is a Hamiltonian-path style problem.
• For empty rectangular grids, a snake traversal is the simplest construction.
• Obstacles and fixed endpoints make the problem much harder.
• Backtracking is the usual general method for small constrained grids.
• Use direct constructions when possible and reserve search for cases that truly need it.