Whack-a-Rectangle
by Brian Hayes
Published 13 November 2010
It’s been almost a year since Bill Gasarch gave us the problem of four-coloring the nodes of a 17 × 17 grid in such a way that no rectangle has all four corners the same color. (See my earlier commentary here and here.)
The problem remains open, the prize of $172 unclaimed.
A few weeks ago I had a momentary fantasy that I might have come upon the answer. I was browsing in a strange New England emporium called Building 19, full of merchandise found nowhere else (thankfully). From across the room I spotted a sofa cushion that looked like it might well be a rectangle-free four-colored grid.
Sadly, a closer look showed that the cushion is neither rectangle-free nor four-colored. Nor 17 × 17 for that matter. And the price tag reads $399.90, so if Bill wants to receive the solution in the form of tacky furniture, he’s going to have to up his offer.
But let us set aside these disappointments. There’s happier news from elsewhere. Martin Schweitzer has turned the square-free-rectangle problem into a game! He explains that he was exploring the new canvas element of HTML5, and thought the rectangle-free problem would make a nice Javascript programming project. The result is entertaining and may even lead to better intuition about the structure of the problem.
On the other hand, the hardest level (“Ninja”) in Schweitzer’s game is only a 12 × 12 array, so don’t think you’re going to click away at little colored squares and earn yourself $289.
The program requires a canvas-capable browser, such a recent version of Chrome, Firefox, Opera or Safari.
Responses from readers:
Please note: The bit-player website is no longer equipped to accept and publish comments from readers, but the author is still eager to hear from you. Send comments, criticism, compliments, or corrections to brian@bit-player.org.
Publication history
First publication: 13 November 2010
Converted to Eleventy framework: 22 April 2025
I beat the Ninja level fairly easily after a few minutes of clicking and a couple of heuristics, but the only thing I learned in the process is that humans are terrible at this game because I can’t help interpreting the board as closer to solved if the rectangles are smaller (since there is less red).
It is easy to force the game to create a 17×17 version. Load the page and then at the top select the URL bar and enter: “javascript:createLevel(17,30);”