Walk over every free square
Count the routes from a start square to an end square that step through every free square of a grid exactly once, by backtracking and counting the squares visited. About 20 minutes.
Know what must be covered
The grid has a start square marked 1, an end square marked 2, free squares marked 0 and walls marked minus 1. A valid route walks from the start to the end through free squares, moving up, down, left or right, and covers every walkable square exactly once.
Count the walkable squares first: the start, the end and all free squares. That is the total the route must reach.
free = sum(v != -1 for row in grid
for v in row)Start at the top left. There are 9 walkable squares in all.
Count a route at the end
Explore with a visited mark per square, set when you enter and cleared when you leave. When you step onto the end square, stop: this route counts as one if the number of squares visited, including the end, equals the total, and as zero otherwise.
Add up the results of the four directions. The squares of the route must be distinct, so never step onto a marked square or a wall.
done = visited == total
A route reaches the end square after visiting only 7 of the 11 walkable squares. Does it count?
- ANo, it must cover every walkable square
- BYes, it reached the end
- CIt counts as half a route
Show the answer
No, it must cover every walkable square. The visited count must equal the total.
Unique paths that cover every square
You are given a grid with these values: 1 is the start square (exactly one), 2 is the end square (exactly one), 0 is a free square and -1 is a wall. Return the number of different routes from the start to the end that step up, down, left or right, never enter a wall, and visit every non-wall square exactly once.
grid = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 2, -1]] → 2
1 ≤ rows, columns ≤ 5 · rows × columns ≤ 20 · exactly one 1 and one 2