Re:The 17x17 problem solved
by experiment0 on Sunday February 12, 2012 @08:34PM
(#3583778)
Best way of finding if there are rectangles:
> We encode the rows of the grid in a set of bit vectors–four vectors for each row, representing the four possible colors. For example, the red vector for a row has a 1 at each position where the corresponding node is red, and zeroes elsewhere. The blue vector has 1s for blue nodes, and so forth. Now we can detect a rectangle merely by taking the logical AND of two rows (an operation that could be a single machine instruction). A rectangle exists if and only if at least two bits are set in the resulting vector.
> We encode the rows of the grid in a set of bit vectors–four vectors for each row, representing the four possible colors. For example, the red vector for a row has a 1 at each position where the corresponding node is red, and zeroes elsewhere. The blue vector has 1s for blue nodes, and so forth. Now we can detect a rectangle merely by taking the logical AND of two rows (an operation that could be a single machine instruction). A rectangle exists if and only if at least two bits are set in the resulting vector.
-- http://bit-player.org/2009/the-17x17-challenge
Thats some lovely hacking.