fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

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 »

I’ve been making notes when I have time, on the “17 x 17 challenge” posted a couple months back by Bill Gasarch. I’ve been sketching out algorithms for the problem and wanted to quickly produce some optimal rectangle free subsets to check my work and look at. So the code below answers the following question:

Imagine an n x n grid. You can color cells of the grid such that no rectangle overlayed on the grid will have all four corners colored. Find a grid with the maximum possible colored cells.

Read the rest of this article »