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 »
1/06/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.
An almost silly amount of time passes between my new ideas on this problem and investigating/coding those ideas, but I’m trying to be better about helping my thoughts see the light of day before I get entirely bored of them.
So in that spirit, here are a few more thoughts on the 17×17 Problem investigated.
Will Graph Layout Algorithms show Symmetry?
Force-based algorithms tend to be good at creating symmetrical layouts of graphs. The idea is to translate a Graph into a system of springs (edges) and charged particles (nodes). You then run a simulation of this 2-dimensional sytem and the graph eventually should work itself out into some equilibrium state.
At that point hopefully you get a layout which is more clear and perhaps makes clear some important relationships of the Graph.
I used the graphviz software suite to do the force-directed layouts and wrote some ugly code to coax some rectangle-free single-colorings into the graphviz file format. I hoped that some of the single- and double-symmetrical relationships that I noticed would emerge in the process.
Read the rest of this article »
9/04/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 a previous post I presented rotations of some single-color rectangle-free grids which were symmetrical along a diagonal axis. I also noticed that, of the single-colorings of optimal size which I could generate, all with an odd number side-length could be made symmetrical along both diagonals (the evens could not):
Perhaps all odd-sided optimal single-colorings are doubly-symmetrical in one of their rotations! That would be a cool thing to learn, and it would also mean that if we wanted to generate an optimal coloring, then our search space would be roughly 1/4 of the grid.
Read the rest of this article »
