The other day I stumbled upon this blog post by William Gasarch: one could read the following:
The 17×17 challenge: worth $289.00. I am not kidding.
Definition: The n x m grid is c-colorable if there is a way to c-color the vertices of the n x m grid so that there is no rectangle with all four corners the same color. (The rectangles I care about have the sides parallel to the x and y axis.)
The 17×17 challenge: The first person to email me a 4-coloring of 17×17 in LaTeX will win $289.00. (I have a LaTeX template below.)
This challenge was started a few months ago (November 30, 2009) and I think that no solution has been founded yet. A straighforward adaptation of this exercice shows that a 19×19 cannot be colored with only 4 colors while many examples of 16×16 grids have been exhibited: the question thus only remains for size 17 and 18. One can read about this challenge at quite a few places
- William Gassarch blog: it all started over there,
- an excellent article in bit-player blog: nice pictures, link to relevant articles, some background on the problem, some ways of attacking the problem,
- Chris Taylor computes the expected number of rectangles in the 17×17 grid, and discuss some possible attacks,
- Andre Roberge also mentioned the challenge.
Quite a lot of people have implemented their ideas and very promising results have been obtained. Nevertheless, perhaps surprisingly, there is no place where one can find a clear summary of all the failed attempts, with a brief description of the method used. Here is an attempt to remedy to this situation:
| #Monochromatic rectangles | Author | Method | Picture |
|---|---|---|---|
| 0 | ? | ||
| 1 | |||
| 2 | |||
| 3 | Alexandros Marinos | Unknown |  |
| 4 | Rohan Puttagunta | unknown |  |
| 5 | |||
| 6 | Kanodonkey | Simulated Annealing |  |
| 7 | |||
| 8 | Kanodonkey | Simulated Annealing |
|
| 9 | Alex Thiery | Parallel Tempering 11 temperatures 30.10^6 iterations |
 |
| 10 | |||
| 11 | |||
| 12 | |||
| 13 | |||
| 14 | |||
| 15 | |||
| 16 | Alexandros Marinos | tree search, symmetric solution |
 |
| 17 | |||
| 18 | Edwards |  |
|
| 19 | |||
| 20 | |||
| 26 | Thomas Levy | Genetic Algorithms |  |
To share your results and method, send an email at alek.thiery.blog(-AT-)gmail.com. It could be interesting to have a brief description of the approach used, or a link towards something related.
Challenge – Announcement « Journey into Randomness said,
June 6, 2010 at 12:44 pm
[...] probability) Tags: 17×17 challenge, Monte Carlo, William Gasarch Have you already heard about the 17×17 Challenge ? It all started 7 months ago, and still no solution has been found. I have the feeling though that [...]
Kaondonkey said,
June 6, 2010 at 3:07 pm
Nice Page, since you are putting such nice piccies up here are a couple of other simulated annealing results I got. A 6 one:
01021132201330232
31002320330311122
20303121233210210
23100102013323123
12312112302231003
31133011020020233
03301313212022031
31012203113032210
11232330223100001
03230122130132300
13203031312101220
32310231201003321
00123223022301311
10231203300223112
10020033131212023
02111000323112332
22223310001133110
and a 7 one
22010321123333100
10203101321203223
03102033101132212
00312113223120023
23132312012200133
30023120201231132
33201220333020101
02222331310101301
12003313130222011
31210030212302013
21120103300320231
32031103112013322
21331211301032020
03323200022311310
11033032023112102
02310232231013231
10111022030031323
I am pretty sure I have a 5 one lying around somewhere — will try to find it.
Alekk said,
June 6, 2010 at 3:32 pm
thanks – I just uploaded your 6 one!
Alexandros Marinos said,
June 10, 2010 at 12:23 am
I spent 5 months writing custom algorithms in C and Python, and all I got is this lousy 16-rectangle grid. But hey, it’s symmetric!
42212134411423433
24223314142141343
22431224314134134
12341141423234243
23114341343422124
13213442134242431
31244424233113221
44411242332321213
41343123344223112
14124333434132212
12433432443311122
41124213213244331
24332412231414312
31442231321441321
43121422121333344
34342321112312434
33434113222121443
Alekk said,
June 10, 2010 at 2:10 am
Nice! I will add that beauty to the list next week (will be away for a few days)
Did you constraint your search to the symmetric solutions ?
Alexandros Marinos said,
June 10, 2010 at 10:48 am
Yeap, that was my bet. In fact, it’s symmetric solutions with two 74s. (3 and 4 each have 74 cells). By now I have a set of algorithms that can explore the whole space of these grids within the space of max. 40 cpu-days. I have also identified a symmetry that can split the tree in half but have not bothered applying it.
I guess I could also look into 74/72/72/71 grids, haven’t looked in that direction yet.
I may have solutions with fewer rectangles, I produced this one by simply taking the ones that went furthest with 0 rectangles and filling in the remaining 3×2 cells to make minimum rectangles.
I have produced 178 permutation-independent symmetric 16x16s though
Thomas Levy said,
May 28, 2011 at 6:05 pm
Don’t sell yourself short, I can only spot 8 rectangles in this one. I think your rectangle counting algorithm might be doing an extra sweep over already checked rows while checking lower rows.
JohnPaul Adamovsky said,
July 10, 2010 at 9:26 am
Hello,
Let’s not beat around the bush here… I like doing my mathematics by hand.
Computers only need to be used when the paperwork becomes overwhelming. Computers should not be used when a pencil and paper will get the job done.
By hand, a high-school student should understand how to generate an enormous number of 17×17 4-colourings with FOUR monochromatic rectangles. There may be a proof that FOUR is a hard limit, so find it in this essay, and get your $289. It may also be possible that no such limit exists.
Allow me to demonstrate:
Step 1) Define 4 colour sets { A, B, C, D }, where each set contains each colour, but has nothing in common with the other sets. There are many such sets.
Example:
A = 0123
B = 1230
C = 2301
D = 3012
Step 2) Using { A, B, C, D }, construct a perfect 16×16 4-colouring, where each row has nothing in common with 3 rows, and ( 1 of each colour ) in common with the remaining 12 rows.
Example: 16×16 – A perfect 4-colouring.
0 – AAAA
1 – BBBB
2 – CCCC
3 – DDDD
4 – ABCD
5 – ACDB
6 – ADBC
7 – BADC
8 – BCAD
9 – BDCA
a – CABD
b – CBDA
c – CDAB
d – DACB
e – DBAC
f – DCBA
* I am ashamed about how long it took me to formalize these simple permutations.
Step 3) Group the rows with nothing in common together. There will be 4 groups, each containing 4 rows. This will guide Step 4.
Gp0 = { 0, 1, 2, 3 }
Gp1 = { 4, 7, c, f }
Gp2 = { 5, 9, a, e }
Gp3 = { 6, 8, b, d }
Step 4) Build a 17th column by assigning 1 colour to each Group. Simply choose the corresponding Gp#. Note that a perfect 16×20 colouring can easily be generated using this method.
Step 5) Build a 17th row by assigning 1 colour to each Column-Group with nothing in common. In the 17th row, each number represents 4 identical numbers. Notice how there will be a single position, which has not been assigned a colour, marked by X. When it gets assigned, it introduces exactly 4 mono-chromatic rectangles into an otherwise perfect 17×17 colouring. Behold the result:
0 – AAAA 0
1 – BBBB 0
2 – CCCC 0
3 – DDDD 0
4 – ABCD 1
5 – ACDB 2
6 – ADBC 3
7 – BADC 1
8 – BCAD 3
9 – BDCA 2
a – CABD 2
b – CBDA 3
c – CDAB 1
d – DACB 3
e – DBAC 2
f – DCBA 1
L – 0 1 23 X
* L = Last Row Number 17
Please do not give up hope just yet. If somebody would like to show me a 16×21 perfect 4-colouring, this might open the gates to the 17×17 perfect 4-colouring, because the 16×21 grid is the first format not easily plotted perfect by hand.
Mathematical Aside:
The “Apex Constraint Condition” – I define this condition to be a colouring where each row has exactly one position, of each colour, in common with EVERY other row.
I conjecture that an analytical proof for the (existence / non-existence) of a perfect 17×17 4-colouring will arise from a thorough investigation of colourings having the “Apex Constraint Condition”.
Here is the solution to an NP-Complete problem, known to actually have a valid solution: 10 Best 5×5 Boggle Boards – TWL06
http://www.pathcom.com/~vadco/deep.html
All the very best,
JohnPaul Adamovsky
PS – Contact me if you have questions – logarithm69@hotmail.com
Perhaps Rohan equates “unknown” with “by-hand”.
Here is the most simple explicit case:
01230123012301230
12301230123012300
23012301230123010
30123012301230120
01231230230130121
01232301301212302
01233012123023013
12300123301223011
12302301012330123
12303012230101232
23010123123030122
23011230301201233
23013012012312301
30120123230112303
30121230012323012
30122301123001231
0000111122223333X
* Think of a professional way to say: “Suck on it… Suck it long, and suck it hard.”
* The metric system, that’s right, I don’t have a job.
JohnPaul Adamovsky said,
July 15, 2010 at 6:52 pm
Hello People,
Is the money real, or did I fall for a hoax?
Long story short. I’ve stumbled into a proof that 4 Monochromatic rectangles is the HARD-LIMIT minimum for a 17×17 4-Colouring.
Mathematics Required: High School – Basic Enumeration Techniques
STATEMENT: It is impossible to construct 5 rows in any 4-Colouring, which have nothing in common with each other.
PROOF:
r1 – 0
r2 – 1
r3 – 2
r4 – 3
r5 – X
* Filling X with any Colour will introduce a commonality in the set.
CONCLUSION:
Four sets of 4 rows with nothing in common is an absolute hard limit for a 16×16 perfect 4-Colouring. This represents a “Minimal Constraint Condition” for 16×16 Colourings. It can also be shown that the “Apex Constraint Condition” where every row has 1 position of each Colour in common with each other row is impossible to construct for a 16×16 grid, and trivial for a 16×20 grid.
T1 – Any 4-Colouring can only contain a maximum of 4 rows with nothing in common.
PROOF BY CONTRADICTION:
Proposition: A Perfect 17×17 4-Colourings Does Exist
Thus, this Colouring must contain a perfect 16×16 Colouring.
By T1, and demonstrated in above post, the Optimal 16×16 Perfect Colouring has 4 sets of 4 rows with nothing in common.
Even with this optimal arrangement, there will be 4 sets of columns with nothing in common, and there will be 4 row sets with nothing in common.
Each row and column set can therefore be assigned a unique Colour, which will be added to the 17th row and column respectively. Adding the 16-element-row and 16-element-column will then introduce ZERO monochromatic rectangles.
The final element in the Bottom-Right corner is marked with an “X”.
Leaving the “X” blank, even in the most optimal case, the 17th row, and 17th column have exactly 1 Colour in common with each other corresponding row or column.
Filling any Colour into position X will thus introduce exactly 4 monochromatic rectangles. Simply inspect the Enumeration examples in the post directly above this one…
The proposition is a logical flaw, because assuming it to be true, PROVES THAT IT IS FALSE!
Therefore, A Perfect 17×17 4-Colourings Does NOT Exist
PS – I prefer cash, so please find a colleague of yours that lives in Toronto, who can hand it to me, and then you can wire them the money.
PPS – I prefer not to deal with banks until I get a sincere-written-apology from CIBC for claiming that they saved my life by emptying the $5000 in my account, while I was in a 25 day-long coma. I saved up that money working construction to pay for a trip to find a merit-based Aerospace Engineering job. I’m pretty sure that bankers aren’t in the business of saving lives, and I don’t give up, so I am still unemployed.
PPPS – I’m thinking this was a hoax, because I doubt that a tenured computer scientist would have any trouble putting together this bush-league high-school proof after a thorough and systematic investigation. I’ve recovered from massive head trauma, so even if it was a hoax, I’d at least like some peer review, and then my money in cash.
PPPPS – I also wrote an extremely powerful search algorithm in C with meticulous and space-saving record keeping, so as to completely eliminate cyclic redundant analysis, while being extremely greedy. Row isolated deviations allowed my quad core to analyse 2,733,499,642,000 of the best colourings in 9 hours and change. The program tanks out at 4 monochromatic rectangles, moves around the 6 to 10 space, and finds the next closest 4-mono-Colourings (typically 20 of them).
5 Monochromatic Rectangles are never found.
Maybe put out a bounty to prove that they don’t exist.
Either your intuition was way off, and-or you’re a stooge.
All the very best,
JohnPaul Adamovsky
JohnPaul Adamovsky said,
July 25, 2010 at 11:48 am
Hello,
Obviously, my enumeration proof isn’t there yet. I need to investigate a Perfect 10×10 3-colouring, and then rethink it.
But what it does establish is that if the computer programs we wrote don’t find a colouring with 4 monochromatic rectangles every time they are run, then THE PROGRAMS PRODUCE ZERO NEW EVIDENCE.
A valid algorithm needs to search wide enough without redundant cycles, so as to hit multiple patch of 4-rectangle colourings, and hopefully in all their possible forms.
In other words, write a program that hits multiple patches of 4 monochromatic-rectangle patches, starting from a mono-colour grid, or keep programming, because your algorithm is too weak to help out.
All the very best,
JohnPaul Adamovsky
Alekk said,
July 25, 2010 at 3:09 pm
> A valid algorithm needs to search wide enough without redundant cycles,
> so as to hit multiple patch of 4-rectangle colourings, and hopefully in all
> their possible forms.
unfortunately, this is far more easily said than done … as you might have noticed
JohnPaul Adamovsky said,
July 25, 2010 at 4:02 pm
Fortunately, this program is a hell of a lot easier and cheaper to DO than a sustained manned-lunar-exploration program.
If you can’t get me a job at NASA JPL, at least admire me. I would also appreciate a really powerful parallel computer with tons of memory for the required record keeping. I’m pretty sure my algorithm will produce real evidence for the hard limit in a reasonable amount of time, even on a top-of-the-line PC.
All the very best,
JohnPaul Adamovsky
JohnPaul Adamovsky said,
July 27, 2010 at 4:58 am
Hello,
I could use some help here.
I have an idea, which I am fairly certain is a good idea:
The 17×17 grid search-space can be reduced to a static row and column, with a 16×16 dynamic grid.
Observe:
00000111122223333
0YYYYxxxxxxxxxxxx
0YYYYxxxxxxxxxxxx
0YYYYxxxxxxxxxxxx
0YYYYxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
I am thinking that any candidate 17×17 Perfect Colouring can be converted into this format using row/col switches, and colour flip-flops.
The “Y” positions can only take on 3 colours.
Please let me know if you have anything to add…
Along with my enumeration investigation, I am going to write a program that uses this format, along with massive pre-allocated arrays, and POSIX threads, which will hopefully start from a mono-colouring, and bounce around to colourings with the HARD-LIMIT minimum RANK. It will be extremely greedy, keep trie-compressed records, and have deviations confined to single rows to reduce the analysis time required.
All the very best,
JohnPaul Adamovsky – logarithm69@hotmail.com
PS – I’ve decided to solve this problem if it is possible, and there is a very good chance that it is possible.
Thomas Levy said,
May 16, 2011 at 10:36 am
I’m working on a genetic algorithm approach. Best grid coloring I have gotten so far has 26 monochromatic rectangles. They are all in color 4.
23124342343412113
13224234112134234
13234441234321121
43321421421113322
12141143342332324
33243113124212441
31444131413322212
22214123431441433
32122444311223431
11313232334214424
21133214423121334
24311314212244132
12443412221343213
24112441133433224
34441322132421314
41232332141443142
34312224244132411
Alexandros Marinos said,
October 9, 2011 at 11:26 pm
It turns out, I’m still working on this. Here’s a grid with 6 rectangles, by my count. Please verify.
41213134432421413
14332214241341243
23431114224234134
13343243412214142
32133141242413324
12121443324343412
31144444231322132
44431343133211221
42242321144233113
34214233424132121
21422413442112333
43224332211344311
24311421331434322
11443321322444231
42113412113332244
14342132123123434
33424221313121443
A new record « Journey into Randomness said,
November 6, 2011 at 10:45 pm
[...] just found a new solution to the Challenge 17 problem. His solution only contains 3 rectangles. This is the best solution (6 November 2011) known [...]
Dmitry Kamenetsky said,
December 21, 2011 at 6:33 am
Here are some more 4-colourings of 17×17 with 3 rectangles. These are different from Alexandros’ grid. I fixed the first 3 rows from Rohan Puttagunta’s solution and used a version of simulated annealing for the remaining rows.
11111222233334444
12222233334444111
13333244431114222
41234313223141243
42143342321321421
21234142342413312
24321124143143421
32134424112312234
14344211132224333
23414231424132413
31442324131423142
34321441324211142
22143113244233134
31243431413242321
43412412343214231
13412143212341324
44321312411432314
11111222233334444
12222233334444111
13333244431114222
43241321323241431
24123124312341342
31432112442342134
34123342124123124
33241143141422342
21432443113213421
44123413241232231
42314313422311243
22314134244123431
14444211132224333
41432334221431312
23241412414133213
24113231423412413
32314421311432124
Just for fun, here is a solution with 4 rectangles that is composed from 16 4×4 Latin squares. It turns out that solutions of this form are quite easy to find. Looks like JohnPaul Adamovsky was right after all, maybe he is a genius. See his 10th of July 2010 post: http://linbaba.wordpress.com/17×17-challenge/
4312|1342|2143|2413|1
2134|2134|3421|1324|1
3421|4213|4312|3241|1
1243|3421|1234|4132|1
———————
1243|1342|4312|1324|2
3421|2134|1234|2413|2
4312|3421|3421|3241|2
2134|4213|2143|4132|2
———————
1243|2134|2143|3241|3
4312|4213|1234|1324|3
2134|3421|4312|2413|3
3421|1342|3421|4132|3
———————
1243|4213|3421|2413|4
4312|2134|4312|4132|4
3421|3421|2143|1324|4
2134|1342|1234|3241|4
———————
4444|2222|1111|3333|1
Dmitry Kamenetsky said,
February 12, 2012 at 8:50 am
The problem has been solved!
http://blog.computationalcomplexity.org/2012/02/17×17-problem-solved-also-18×18.html
Cheers,
Dmitry