The 17x17 Four Color Challenge

Professor Gasarch at the University of Maryland is challenging people to see if a solution exists to a Four Color problem. In his proposed problem, each site of a 17 by 17 grid is occupied by one of four colors. The challenge is to place a color on each site such that all the corners of any rectangle formed from the sites are not the same color. (See Details). He is offering a prize of $289 ($17x17) for a solution (if one even exists). What intrigues me is his lack of prize money for a proof that a solution exists. He want's something that would 'stand up in court'. Which makes me inclined to think he plans to use this for a patentable encryption algorithm. But I'm speculating.

I quickly coded up the problem to get an idea of the solution space and the difficulty of the problem. First off, brute force is out of the question. 4^289 is an incredibly large number and finding all solutions would take longer than the earths lifetime. There may be some branch cut methods to reduce the complexity, but I'm guessing it is still too large.

As a first step, I did a random search of 10,000 configurations and plotted a histogram of the number of solutions with a given number of conflicts. A conflict being the number of rectangles that have four corners of the same color. The plot is depicted below. In summary, we see that the probability of getting a solution with zero rectangles with same colored corners is nearly zero. So, solving this problem is certainly a difficult challenge. Especially with the uncertainty of the existence of a solution.