Once again, the easy set can easily be solved by hand. For the hard set a greedy approach works. We generated the inputs for Q using a randomized backtracking algorithm – we always find the first cell that does not belong to any polygon, generate a random polygon that contains it, check that the remaining area is still connected, and if yes, we continue recursively.
Of course, those who are good with pen and paper puzzles can solve even R2 by hand:
