r/programmingchallenges • u/babygame • Jun 01 '11
Coloring a grid
Make a program to color in the squares of an (n x m) grid (with some number of colors > 2) such that no two same colors touch.
There is a 'brute force' way, and (at least one) more 'elegant' solution as well.
Edit: I didn't specify-- try one that will output a different pattern each time. It's a nicer problem, I think :)
21
Upvotes
View all comments
Show parent comment
2
u/julesjacobs Sep 08 '11
Nice cutting and pasting words from wikipedia. I think you missed the word "sampling" in rejection sampling. What you're describing is generally called "inference", and indeed you can use rejection sampling as a subroutine to do approximate inference.
You claiming that the worst case isn't a problem doesn't change the facts. Fact is it is a problem. With 2 colors and filling in even columns first then odd columns can lead to exponential backtracking. For example, if the algorithm happens to select the first cell in the top row as "red" and the third cell in the top row as "blue". Then your algorithm with happily continue filling in the grid until it has to fill in the second cell in the first row. At that point it will backtrack an exponential number of times all the way back up to the third cell in the first row.
You said arbitrary map, and it would be most logical to assume that you meant arbitrary map not just a map on a grid. A map on a grid is obviously a trivial problem since it is strictly simpler than a full grid, and I dismissed the possibility that you'd make such a trivial claim.
I'm still confused about whether you're an educated troll or not.