<p>Just an extended comment:</p>

<p>You can take a look to the approach used by Steinbach and Posthoff to find <a href="http://blog.computationalcomplexity.org/2012/02/17x17-problem-solved-also-18x18.html" rel="noreferrer">the 4-coloring of a 18x18 (and 12x21) grid without monochromatic rectangles</a>:</p>

<p><a href="http://www.informatik.tu-freiberg.de/prof2/publikationen/ISMVL_2013_slofcrfg.pdf" rel="noreferrer">Bernd Steinbach and Christian Posthoff, Solution of the Last Open Four-Colored Rectangle-free Grid an Extremely Complex Multiple-Valued Problem</a>. In Proceedings of the 2013 IEEE 43rd International Symposium on Multiple-Valued Logic (ISMVL '13)</p>

<p>As proved by Gasarch et al. given a partial $c$-coloring of an arbitrary $n \times m$ rectangle, it is NP-complete to decide if the coloring can be extended to the whole rectangle without monochromatic rectangles: <a href="http://arxiv.org/abs/1205.3813" rel="noreferrer">Daniel Apon, William Gasarch, Kevin Lawler, An NP-Complete Problem in Grid Coloring</a>. 
So there are high chances that the problem is NP-complete even for equilateral triangles .... I think it would be a nice result to prove it.</p>

<p>Just a side note: I spent weeks of CPU cycles on the monochromatic rectangle-free 4-coloring problem but I started from a wrong partial result (a wrong previous analysis that restricted the number of possible 1-color sub-configurations) and I used the <a href="https://sites.google.com/site/stpfastprover/" rel="noreferrer">STP constraint solver</a>; you can achieve great improvements if you add constraints that break symmetries (e.g. an ordering on the coloring of a side of the triangle) and try to make an analysis of the possible configurations using only 1-color.</p>

<p>EDIT: this is the result of an STP program for n=19 (~ 1 min.)</p>

<p><img src="https://i.sstatic.net/NMilL.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-02-13T17:15:19.120Z
Thank you for the solution of $n=19$. I tried it myself in the meantime and wrote a little STP program ( http://pastebin.com/efzHu5md ). Unfortunately it is not really faster than the direct SAT approach, I thus assume that it is possible to choose the inequalities better than I did.
Listing
CC BY-SA 3.0
2014-01-22T21:12:14.520Z
2014-01-27T23:01:01.787Z
2014-01-27T23:01:01.787Z
Marzio De Biasi
<p>Using a SAT-based approach, I can confirm every instance is 3-colorable up to $n \leq 22$. A local search solver finds a solution for $n=22$ still rather quickly on a modern desktop. I tried the same approach for $n=23$, but obtained no solution in about 96 hours. It is thus tempting to conjecture that $n=23$ is <em>not</em> 3-colorable anymore. (Let me also remark that a 4-coloring is found instantly for $n=23$).</p>

<p>My observation for $n=19$ was similar to yours, that is, it already seems quite out of reach for a complete solver if the straightforward encoding is used. On the other hand, I wouldn't be surprised if a smarter encoding could settle the case of $n=23$ (and beyond?).</p>

<p>Below is the solution for $n=22$.</p>

<p><a href="https://i.sstatic.net/eoiWX.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eoiWX.png" alt="tri22-sol"></a></p>

<p>Many thanks to Marzio for generating the image, and for letting me know about the problem! :-)</p>

CC BY-SA 3.0
2016-07-14T15:09:33.070Z
2016-07-14T16:48:28.763Z
2016-07-14T16:48:28.763Z
Juho
<p>In the <a href="http://www.bundeswettbewerb-informatik.de/" rel="nofollow noreferrer">Bundeswettberweb Infomatik</a> 2010/2011, there was an interesting problem:</p>

<p>For fixed $n$, find a minimal $k$ and a map  $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that there is no triple $(i,j),(i+l,j),(i+l,j+l)$ with $\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$.</p>

<p>Namely we are looking for the minimal amount of colors for a triangle, such that there is no uniformly colored equilateral subtriangle (the following picture shows an invalid coloring as the highlighted vertices form such an uniformly colored equilateral subtriangle):</p>

<p>$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$<img src="https://i.sstatic.net/9Sblb.png" alt="Example"></p>

<p>In fact they asked for a reasonably small $k$ for $n=1000$ and in the <a href="http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf29/loesungshinweise292.pdf" rel="nofollow noreferrer">solution</a> (written in german) they noted that a greedy approach yields a coloring with $27$ colors for $n=1000$, which can be reduced to $15$ by randomizing colors until a valid solution is found.</p>

<p>I am interested into exact solutions (for smaller $n$). The solution says that backtracking yields that $2$ colors are sufficient for $n\in\{2,3,4\}$ and $3$ are sufficient for $5\leq n \leq 17$, where backtracking is already really slow for $n=17$.</p>

<p>First I tried to use an ILP formulation and Gurobi to get some results for $n&gt;17$, but it was too slow (already for $n=17$). Then I used a <a href="http://www.labri.fr/perso/lsimon/glucose/" rel="nofollow noreferrer">SAT solver</a>, because I noticed that there is a straight forward formulation as a SAT-instance.</p>

<p>With that approach I was able to generate a solution with $3$ colors for $n=18$ within $10$ minutes:</p>

<p>$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$<img src="https://i.sstatic.net/iIwnX.png" alt="Solution with 3 colors for 18 nodes"></p>

<p>But to decide if $3$ colors suffice for $n=19$ it is already too slow. Is there some different approach that gives exact solutions for $n \geq 19$? Certainly we can't expect a polynomial algorithm.</p>

CC BY-SA 3.0
2014-01-22T19:50:39.783Z
interesting question. why do you say we can't expect a polynomial time algorithm?
Sasho Nikolov
CC BY-SA 3.0
2014-01-22T20:04:03.743Z
@SashoNikolov it is just an assumption because this seems to be harder than finding a valid vertex coloring (harder in terms of more constraints), and vertex coloring is already a very hard problem.
Listing
<graph-theory><sat><combinatorics>
Minimum amount of colors preventing an equilateral uniformly colored subtriangle
Listing
# Minimum amount of colors preventing an equilateral uniformly colored subtriangle

(Asked by: username_0 on 2014-01-22)

In the [Bundeswettberweb Infomatik](http://www.bundeswettbewerb-informatik.de/) 2010/2011, there was an interesting problem:

For fixed $n$, find a minimal $k$ and a map $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that there is no triple $(i,j),(i+l,j),(i+l,j+l)$ with $\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$.

Namely we are looking for the minimal amount of colors for a triangle, such that there is no uniformly colored equilateral subtriangle (the following picture shows an invalid coloring as the highlighted vertices form such an uniformly colored equilateral subtriangle):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$![Example](https://i.sstatic.net/9Sblb.png)

In fact they asked for a reasonably small $k$ for $n=1000$ and in the [solution](http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf29/loesungshinweise292.pdf) (written in german) they noted that a greedy approach yields a coloring with $27$ colors for $n=1000$, which can be reduced to $15$ by randomizing colors until a valid solution is found.

I am interested into exact solutions (for smaller $n$). The solution says that backtracking yields that $2$ colors are sufficient for $n\in\{2,3,4\}$ and $3$ are sufficient for $5\leq n \leq 17$, where backtracking is already really slow for $n=17$.

First I tried to use an ILP formulation and Gurobi to get some results for $n>17$, but it was too slow (already for $n=17$). Then I used a [SAT solver](http://www.labri.fr/perso/lsimon/glucose/), because I noticed that there is a straight forward formulation as a SAT-instance.

With that approach I was able to generate a solution with $3$ colors for $n=18$ within $10$ minutes:

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$![Solution with 3 colors for 18 nodes](https://i.sstatic.net/iIwnX.png)

But to decide if $3$ colors suffice for $n=19$ it is already too slow. Is there some different approach that gives exact solutions for $n \geq 19$? Certainly we can't expect a polynomial algorithm.

**Tags:** graph-theory, sat, combinatorics

> **Comments:**
> **username_1**: interesting question. why do you say we can't expect a polynomial time algorithm?  
> **username_0**: @SashoNikolov it is just an assumption because this seems to be harder than finding a valid vertex coloring (harder in terms of more constraints), and vertex coloring is already a very hard problem.  

---

## 2 answers

### Answer by username_2 on 2014-01-22. Score: 11 | Accepted answer

Just an extended comment:

You can take a look to the approach used by Steinbach and Posthoff to find [the 4-coloring of a 18x18 (and 12x21) grid without monochromatic rectangles](http://blog.computationalcomplexity.org/2012/02/17x17-problem-solved-also-18x18.html):

[Bernd Steinbach and Christian Posthoff, Solution of the Last Open Four-Colored Rectangle-free Grid an Extremely Complex Multiple-Valued Problem](http://www.informatik.tu-freiberg.de/prof2/publikationen/ISMVL_2013_slofcrfg.pdf). In Proceedings of the 2013 IEEE 43rd International Symposium on Multiple-Valued Logic (ISMVL '13)

As proved by Gasarch et al. given a partial $c$-coloring of an arbitrary $n \times m$ rectangle, it is NP-complete to decide if the coloring can be extended to the whole rectangle without monochromatic rectangles: [Daniel Apon, William Gasarch, Kevin Lawler, An NP-Complete Problem in Grid Coloring](http://arxiv.org/abs/1205.3813).
So there are high chances that the problem is NP-complete even for equilateral triangles .... I think it would be a nice result to prove it.

Just a side note: I spent weeks of CPU cycles on the monochromatic rectangle-free 4-coloring problem but I started from a wrong partial result (a wrong previous analysis that restricted the number of possible 1-color sub-configurations) and I used the [STP constraint solver](https://sites.google.com/site/stpfastprover/); you can achieve great improvements if you add constraints that break symmetries (e.g. an ordering on the coloring of a side of the triangle) and try to make an analysis of the possible configurations using only 1-color.

EDIT: this is the result of an STP program for n=19 (~ 1 min.)

![enter image description here](https://i.sstatic.net/NMilL.png)

> **Comments:**
> **username_0**: Thank you for the solution of $n=19$. I tried it myself in the meantime and wrote a little STP program ( http://pastebin.com/efzHu5md ). Unfortunately it is not really faster than the direct SAT approach, I thus assume that it is possible to choose the inequalities better than I did.  

---

### Answer by username_3 on 2016-07-14. Score: 4

Using a SAT-based approach, I can confirm every instance is 3-colorable up to $n \leq 22$. A local search solver finds a solution for $n=22$ still rather quickly on a modern desktop. I tried the same approach for $n=23$, but obtained no solution in about 96 hours. It is thus tempting to conjecture that $n=23$ is *not* 3-colorable anymore. (Let me also remark that a 4-coloring is found instantly for $n=23$).

My observation for $n=19$ was similar to yours, that is, it already seems quite out of reach for a complete solver if the straightforward encoding is used. On the other hand, I wouldn't be surprised if a smarter encoding could settle the case of $n=23$ (and beyond?).

Below is the solution for $n=22$.

[![tri22-sol](https://i.sstatic.net/eoiWX.png)](https://i.sstatic.net/eoiWX.png)

Many thanks to Marzio for generating the image, and for letting me know about the problem! :-)


---

