Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph
This appears to be NP-complete by a reduction from Hamiltonian cycle in planar graphs of degree at most three. Hamiltonian cycle should still be hard in planar graphs of degree at most three that contain two adjacent degree-two nodes (this is the part I haven't checked very carefully). Embed the given planar graph into the grid in such a way that each vertex becomes a grid point, each edge becomes a grid path, and all edges have the same length $\ell$ (pad the shorter ones by zigzagging if necessary to achieve this). Let $s$ and $f$ be two adjacent degree-two nodes. Include walls in the initial placement of walls so that only the vertices and edges of the embedding remain available to connect $s$ to $f$. Let $n$ and $m$ be the numbers of vertices and edges in the original graph. Then, the original graph has a Hamiltonian cycle if and only if it is possible to place $m-(n-1)$ more walls in such a way that the new shortest path from $s$ to $f$ has length $(n-1)l+(n-2)$. A path of that length must be a Hamiltonian path in the original graph which together with the edge from $s$ to $f$ forms a Hamiltonian cycle, and conversely if the graph contains a Hamiltonian cycle then you can force the path from $s$ to $f$ to be that long by placing a wall in each other edge.