17×17 Challenge

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 17x17_4_anonymous
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.

19 Comments

  1. 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 […]

  2. 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.

  3. 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 ?

      • 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.

  4. 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.

  5. 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

  6. 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

  7. 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

    • 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

  8. 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.

  9. 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

  10. 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

  11. 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 […]

  12. 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: https://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

  13. 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

  14. Jerald said,

    January 2, 2015 at 10:04 am

    You post interesting posts here. Your page deserves much more visitors.
    It can go viral if you give it initial boost, i know useful service that can help you,
    simply type in google: svetsern traffic tips


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: