Given an $n \times n$ square grid, there are the outlines of $n^2$
$1 \times 1$ squares, $(n-1)^2$ $2 \times 2$ squares, and so on.
What is the minimum number of edges that can be removed from the
grid such that there is no complete outline of a square remaining?
Using techniques from tiling problems and other graph theoretic methods,
we solve the problem for all $n$ and prove similar results for
rectangular grids for which the side lengths differ by no more than six.
We also introduce another version of the problem where we ask for the minimum
number of edges to ``break'' all of the rectangles in a grid.
DIMACS Home Page