Here's a problem +Brendan Barnwell
came up with and told me about. Given an N
square grid, where the edges wrap around in a toroidal fashion, color N
squares in each of N
different colors such that for any pair (a
) of colors, (a
can be the same color) there are exactly 4 ways to go from a cell of color a
to an adjacent cell of color b
. Because there are four ways to go from a cell to another of the same color, the area of a given color must contain either a tromino, (either L or straight) or two dominoes. All other cells of that color must be disconnected single squares.
Some solutions for N
=3, 4, and 5 are shown below. (You can think of the unshaded area as being a single image of the grid, surrounded by additional shaded images of the grid where it wraps around.)
Some questions: for small N
an exhaustive enumeration of solutions should be possible: how many are there? In all of the cases shown, the squares of any color can be translated onto the squares of any other color. Are there solutions with no symmetry? Is there a quick algorithm for generating a solution for a given size?