The bisection problem asks for a partition of the n vertices of a graph into two sets of size at most ⌈n/2⌉, so that the number of edges connecting the sets is minimised. A grid graph is a finite connected subgraph of the infinite two-dimensional grid. It is called solid if it has no holes. Papadimitriou and Sideri (Theory Comput Syst 29:97–110, 1996) gave an O(n5)time algorithm to solve the bisection problem on solid grid graphs. We propose a novel approach that exploits structural properties of optimal cuts within a dynamic program. We show that our new technique leads to an O(n4)time algorithm.