31/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.
Just a few follow-ups to my previous post in which I use a simulated annealing-type algorithm to find a good (hopefully complete) cover of a grid by swapping rows and columns from four identical sub-grids of 74 colors.
Easing into new thresholds
I modified my algorithm so that the likelihood of jumping into the highest permitted energy level is decreased over time; thus instead of having an abrupt transition to a new threshold, resulting in a steep dive, we instead ease into the new energy level.
Here is a graph of a run with the adjusted meta-heuristic (in blue) alongside a previous abrupt threshold transition run (in black). You can check compare it to the graph from the previous post:
Read the rest of this article »
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 »
