Jumlah minimum warna mencegah subtriangle berwarna seragam yang sama sisi

Dalam Bundeswettberweb Infomatik 2010/2011, ada masalah yang menarik:

Untuk fix , temukan minimal k dan peta φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , ... , k } , sedemikian sehingga tidak ada tiga ( i , j ) , ( i + l , j ) , ( i + l , j + l ) dengan φ ( $n$$k$$\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$$(i,j),(i+l,j),(i+l,j+l)$ .$\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$

Yaitu kami sedang mencari jumlah minimal warna untuk sebuah segitiga, sehingga tidak ada subtriangle sama sisi berwarna seragam (gambar berikut menunjukkan pewarnaan yang tidak valid karena simpul yang disorot membentuk subtriangle sama sisi berwarna sama):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

Bahkan mereka meminta cukup kecil untuk n = 1000 dan dalam solusi (ditulis dalam bahasa Jerman) mereka mencatat bahwa pendekatan rakus menghasilkan pewarnaan dengan 27 warna untuk n = $k$$n=1000$$27$$n=1000$ , yang dapat dikurangi menjadi dengan mengacak warna hingga solusi yang valid ditemukan.$15$

Saya tertarik pada solusi yang tepat (untuk lebih kecil ). Solusinya mengatakan bahwa backtracking menghasilkan 2 warna yang cukup untuk n ∈ { 2 , 3 , 4 } dan$n$$2$$n\in\{2,3,4\}$ cukup untuk 5 ≤ n ≤ 17 , di mana backtracking sudah sangat lambat untuk n = 17 .$3$$5\leq n \leq 17$$n=17$

Pertama saya mencoba menggunakan formulasi ILP dan Gurobi untuk mendapatkan beberapa hasil untuk , tapi itu terlalu lambat (sudah untuk n = 17 ). Kemudian saya menggunakan pemecah SAT , karena saya perhatikan bahwa ada formulasi lurus ke depan sebagai instance-SAT.$n>17$$n=17$

Dengan pendekatan itu saya dapat menghasilkan solusi dengan warna untuk n = 18 dalam 10 menit:$3$$n=18$$10$

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

Tetapi untuk memutuskan apakah warna sudah cukup untuk n = 19 sudah terlalu lambat. Apakah ada beberapa pendekatan berbeda yang memberikan solusi tepat untuk n $3$$n=19$ ? Tentu saja kita tidak dapat mengharapkan algoritma polinomial.$n \geq 19$

Hanya komentar yang diperluas:

Anda dapat melihat pendekatan yang digunakan oleh Steinbach dan Posthoff untuk menemukan 4-pewarnaan kisi 18x18 (dan 12x21) tanpa persegi panjang monokromatik :

Bernd Steinbach dan Christian Posthoff, Solusi dari Grid Terbuka Empat-Warna Terakhir Yang Terbuka Tanpa Warna Masalah Kompleks Berharga Banyak yang Sangat Kompleks . Dalam Prosiding Simposium Internasional ke-43 IEEE 2013 tentang Multiple-Valued Logic (ISMVL '13)

Sebagaimana dibuktikan oleh Gasarch et al. diberikan color parsial yang sewenang-wenang $c$$n \times m$

Hanya catatan tambahan: Saya menghabiskan berminggu-minggu siklus CPU pada masalah 4 warna pewarnaan empat-persegi monokromatik tapi saya mulai dari hasil parsial yang salah (analisis sebelumnya yang salah yang membatasi jumlah kemungkinan sub-konfigurasi 1 warna) dan saya menggunakan itu STP kendala pemecah ; Anda dapat mencapai peningkatan besar jika Anda menambahkan kendala yang memecah simetri (mis. pemesanan pada pewarnaan sisi segitiga) dan mencoba membuat analisis konfigurasi yang mungkin hanya menggunakan 1-warna.

EDIT: ini adalah hasil dari program STP untuk n = 19 (~ 1 mnt)

$n \leq 22$$n=22$$n=23$$n=23$$n=23$ ).

$n=19$$n=23$

$n=22$

Terima kasih banyak kepada Marzio karena menghasilkan gambar, dan telah memberi tahu saya tentang masalahnya! :-)