What is the time complexity of rat in a maze?

Worst case O(4^(rows×cols)). Space complexity is O(rows×cols). Finds *a* path, not the shortest - use BFS for that.

Rat in a maze

medium

The clearest picture of what backtracking actually means: a path is marked on the way in and erased on the way out, so a dead end leaves no trace to block later attempts.

Worst O(4^(rows×cols))Space O(rows×cols)

Loading the rat in a maze engine…

Where to go next

A* and BFS pathfinding

medium

Paint a maze and watch three algorithms solve it differently.

Depth-first search

easy

A stack instead of a queue - that is the only difference.

N-Queens

hard

Switch pruning off and watch the search explode.