a Haskell programming blog

I’ve been puzzling over some of the problems presented by the 17 x 17 Challenge, and wanted to share some of what I’ve learned and have been wondering about. The problem and ultimate goal is to color a 17 x 17 grid with four colors such that every cell is colored and no rectangle is formed by any four cells of the same color.

Single-Color Subsets

I’ve started by trying to find an algorithm to find optimal single-color subsets, i.e. a way of coloring a grid with one color such that no rectangle is formed by the colored cells, and we have the greatest number of cells colored as possible. I started thinking of coloring cells one at a time, following a path based on the notion of an “extended rectangle” where the fourth side was longer or shorter than the first, to avoid forming rectangles.

I also noticed that we could traverse all the cells in the largest known 17×17 subset by following a simple spiraling algorithm. It didn’t seem to matter which cell or direction we started in either:

go until you hit a colored cell, then rotate 90 degrees

I finally got some time to code up a messy script to test out a few variations of an algorithm to generate rectangle-free single colorings of a grid, as part of a lazy humble effort to solve the 17 x 17 challenge.

This post is going to be a bit of a code-dump. The algorithm is essentially:

1. color cell,
2. turn to the right,
3. stop on first non-rectangle forming cell,
4. if the cell is uncolored, color it and turn to the right, else if the cell was already colored and has been entered from this direction already, then skip it, else turn to the right

Read the rest of this article »

This is the third post of mine on DeBruijn sequences, and is in preparation for another post to come which I hope should be an interesting investigation into a possible parallel algorithm. The first two posts are here and here.
Read the rest of this article »