Capsules

This problem gives you a grid, and you have to put numbers 1-n in each "section" such that across the whole grid, no number is adjacent to a cell with the same number.

The GNYR guy asks a problem like this every year, and it's always just brute force. If you didn't know that, the size of 49 cells ought to be enough.

The easiest way to do this, I think, is to just go from upper left to lower right, find the first empty cell, and put the next valid number that fits. It's just recursive backtracking. Might want a bitmap or hashmap or something to track which numbers are used for any given "section," as well as a mapping of which "section" a given cell is in (reverse mapping of how it's input). Other than that, the only challenge is the input and output.

It's hard to prove this is fast enough....but it is. Note the search tree is heavily pruned, and many cells will only be able to get to 1 or 2 due to the groupings, and the fact that by the time you get to a cell, at least 4 numbers will be forbidden due to adjacency.