Trying cases by hand

A useful thing to do when you're stuck with a problem is to try creating some of your own sample cases and solving them yourself. The process of solving by hand can help give you inspiration for an algorithm!

Let's take a look at the problem NORT from AIO 2012. It's not too hard to see that for many grids, you can perform a snake-like pattern that covers the entire grid.

NORT

The second sample case in the problem statement shows that there are cases where it is not possible to fill the grid. If you try the snake pattern in this 3x3 grid, you'll get stuck. See if you can find two more grids where it is not possible to cover the entire grid. What's the best you can do for these cases?

By now, you should have an idea of what the solution might be.

Spoiler

When either \(R\) or \(C\) are even, then you can always cover the grid. When they're both odd, you can cover all but one square.

It's fairly easy to see that the snake pattern covers everything when either \(R\) or \(C\) are even, but it's harder to see that you can always cover all but one square when both are odd.

Here is an algorithm that always fills all but one square when \(R\) and \(C\) are both odd.

  1. Let's ignore the last row. We can fill the entire subgrid without this row using the snake algorithm from before (since there are now an even number of rows).
  2. We can add in squares two at a time from the last row by adding a short detour to our snaking path.
  3. We can do this until there is only one square left. We've now covered all but one square!

The diagram below might clarify:

NORT

For completeness, we should also prove that it is impossible to fill the entire grid when \(R\) and \(C\) are odd. Instead, I'll leave it as something for you to consider (perhaps this will point you in the right direction).

Exercises