10/07/2010
Note: this is part of a series of posts is related to the “17×17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.
This is something I’ve been wanting to play with for months now, but haven’t made the time to implement: I wondered if simulated annealing techniques could be effective in finding a complete grid covering.
We would simply start with four copies of the 74-color grid and swap their rows and columns around, within each color set, trying to cover all of the cells by the union of the four subsets. So all of the sets of cells of a single color are fundamentally simply different permutations of the same 74-cell rectangle-free Graph.
Here is an illustration of the concept. Our algorithm starts with all four colored sets of cell overlapping (the red cells are on top, covering the other three colors):
…then we swap two rows or two columns from a colored subset of cells, until the four colored subsets spread out covering as much of the grid as possible. Here we cover all but 21 cells:
Read the rest of this article »
9/05/2010
The Problem
Problem A in the qualifying round of this year’s Google CodeJam contest was really clever. The problem used a classic made-for-TV gadget from the 80s: The Clapper™ (“snapper” in google’s version) and went like this:
The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.
When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers — making a clicking sound — any Snapper receiving power at the time of the snap toggles between the ON and OFF states.
In hopes of destroying the universe by means of a singularity, I have purchased N Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper.
Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.
I keep doing this for hours. Will the light be on or off after I have snapped my fingers K times? The light is on if and only if it’s receiving power from the Snapper it’s plugged into.
Read the rest of this article »
18/03/2010
Note: this is part of a series of posts is related to the “17×17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.
In my last post, I gave a symmetrical rotation of the known 74-cell single-coloring. I want to use a slight variation of that grid to show why I think treating the grids as symmetrical will help us in solving this problem.
Here is a new spreadsheet, with several panes you can click through on the bottom. Panes ONE through FIVE represent the first few rows of a single-coloring in which we avoid making any real choices, thanks to a few assumptions we make (I’ll come back to that).
Orange represents the row we’re coloring, gray cells are rectangle forming cells (in which marks are not allowed), and blue cells represent what I consider to be the real search-space:
NOTE: We’re simply using another automorphism of the original 74-coloring, i.e. a series of rotations that preserve all the significant attributes of the graph.
Read the rest of this article »
