Новый конкурс программистов

[Nataly-Mak]

Вот она - головоломка о непересекающихся комбинациях из чисел 1,2,3,...,10

Nataly-Mak в сообщении #583413 писал(а):

Красивая головоломка



Этот прямоугольник 10х20 надо сделать strong-10-coloring (заполнить пустые ячейки). Есть решение?

Выше я привела решение, найденное на форуме nazva.net
Красивое решение! А я не додумалась, была где-то рядом, но до конца так и не поняла закономерность. А она есть! И в этом красота задачи.

-- Ср июн 20, 2012 07:44:30 --

Pavlovsky в сообщении #587136 писал(а):

Какая теорема полезная я говрил в самом начале конкурса. Теорема 4.12. Именно по ней можно получить решение С^2 для С=p^s, где p простое.

Блин!
Это я уже давно пережевала и выплюнула
Я нашла базовый алгоритм № 1, который позволяет строить эти решения, и нашла его совсем в другой статье. И этот алгоритм гораздо проще в применении, чем тот, что описали вы. В изложенном мной алгоритме не надо строить никаих разбиений. К тому же, его можно применять не только для С простых и степеней простых, но и для других С, для которых можно найти набор непересекающихся комбинаций. Я применила его, например, для C=6.

(вы, похоже, тоже не читаете мои сообщения )

Что вы мне голову морочите?
Вы тут говорили, что именно леммы и теоремы этой статьи дали вам возможность построить решения для C=p^k+1, p - простое, k>=1.
Вам хватило лемм и теорем этой статьи, как вы тут сказали.

Да ради Бога, не надо говорить больше ничего!
Я вообще прекращаю поиск решений и начинаю писать статью о задаче. Мне это гораздо интереснее.

-- Ср июн 20, 2012 08:02:16 --

dimkadimon
я снимаю свой вопрос о разбиениях.

Как утверждает Pavlovsky, они служат только для доказательства теоремы 4.5, а эта теорема совсем бесполезная для решения конкурсной задачи.

Больше от этих разбиений нет никакого проку, как я поняла из сообщения Pavlovsky.

Pavlovsky нам сообщает, что большой прок есть от теоремы 4.12 но это уже и ёжик знает.

[Pavlovsky]

Nataly-Mak в сообщении #587137 писал(а):

Большой прок есть от теоремы 4.12 но это уже и ёжик знает.

Решение 256х256 для С=16 нашло только 18 ежиков.

[dimkadimon]

Nataly-Mak в сообщении #587132 писал(а):

А потому что я не хочу писать программы, которые мне не нужны и писать которые мне неинтересно.
(Ха! Ну и что интересного в программе проверки правильности??? Ну, да 7 строчек. Организовать циклы, по всем строкам, по всем столбцам квадрата (прямоугольника) и проверять одинаковость цветов во всех вершинах внутренних прямоугольников.)

Как я уже говорила, программа проверки правильности мне абсолютно не нужна!
Все составленные мной решения я проверяю в программе Эда или прямо на конкурсе.

Страно, а мне все ето время казалось что нужна...

С етой программой вы сможете проверять не только квадраты, а еше и прямоугольники. К тому же программу лекго изменить чтобы она проверяла strong c-coloring и strong (c,c')-coloring. Очень полезная штука!

Для меня писание программ настолько же интересно (и красиво!), как сама математика задачи. Красивые программы бывают короткие и еффективные.

[Nataly-Mak]

Pavlovsky в сообщении #587142 писал(а):

Nataly-Mak в сообщении #587137 писал(а):

Большой прок есть от теоремы 4.12 но это уже и ёжик знает.

Решение 256х256 для С=16 нашло только 18 ежиков.

Ну, вы на этом фоне бегемот

Это просто конкурсанты не читают данную тему. Некоторые из них сильно ленивы, как наш Alexu007, другие ещё не знают о её существовании.
Кто тему читает, тот просто не мог не построить это решение! Я же подробно изложила алгоритм.

[есть ещё и третьи: кто не хочет пользоваться готовыми алгоритмами]

Вот она - заполненная головоломка:



Гармония! Красота!

-- Ср июн 20, 2012 08:38:04 --

dimkadimon в сообщении #587146 писал(а):

Страно, а мне все ето время казалось что нужна...

Знаете, что нужно делать, когда кажется?

Ну на фига она мне нужна, если это можно делать в готовой программе Эда?!

Цитата:

С етой программой вы сможете проверять не только квадраты, а еше и прямоугольники.

Ох! Могучий совет
Но в программе Эда тоже можно проверять прямоугольники!

Цитата:

К тому же программу лекго изменить чтобы она проверяла strong c-coloring и strong (c,c')-coloring. Очень полезная штука!

А вот это я написала!

Цитата:

Для меня писание программ настолько же интересно (и красиво!), как сама математика задачи. Красивые программы бывают короткие и еффективные.

Так ведь программа программе рознь! Есть программы тупого перебора (к которой, кстати, относится проверка правильности решения).
А есть программы, реализующие очень интересные алгоритмы.

И не надо рассказывать мне о коротких и эффективных программах. Я не вчера о программах узнала!

-- Ср июн 20, 2012 08:49:17 --

Кстати, о птичках...

Pavlovsky
изложенный вами алгоритм, основанный на теореме 4.12, вы изложили не полностью, а только для С - простых чисел.
Как делать разбиения, например, для C=9, вы так и не написали.
Поэтому, реализовав этот алгоритм для простых чисел по вашему описанию, я не смогла по этой же методе построить решения для С, являющихся степенью простых чисел.

Долго не могла придумать, как же строить разбиения для С=9. Потом бросила ваш метод и начала искать другой. И нашла! Там, в другой статье, приведён пример для С=4. Это я тут подробно изложила. Далее вышла на уникальные перестановки. Не сразу сообразила, как же построить уникальные перестановки для С=8,9,16.
Вы дали подсказку: "Возьми их из ОЛК". Но как взять, так и не сказали. Я долго искала решение (и здесь спрашивала, как же взять уникальные перестановки из ЛК, но вы... молчок ). Не могла догадаться, что надо брать не строки ЛК, а столбцы.

Потом была подсказка dimkadimon (в теме "Уникальные перестановки"). Он тоже не сразу догадался о столбцах. Но как только догадался, сразу же подсказал.

И уникальные перестановки, наконец-то, были получены!
Дальше в том алгоритме, который я привела, вообще делать нечего. Решения для С=8,9,16 уже получаются шутя.

Думаю, что после долгих раздумий я всё равно догадалась бы, как же взять из ЛК уникальные перестановки.

[не зря же вы просили полную группу ОЛК 16-го порядка
Кстати, мысль об ОЛК пришла мне сразу же, как вы описали разбиения по теореме 4.12]

Да, а вот в ОЛК 12-го порядка уникальные перестановки расположены в строках, а не в столбцах. Очень красивая группа ОЛК из 5 штук, и решение даёт очень красивое - 72х144.
Ровно половина квадрата 144х144.

[Alexu007]

dimkadimon в сообщении #587130 писал(а):

а почему бы ... не написать программу которая проверяет решения на правильность

Если кому нужно - пожалуйста. Функция написана на С++, для её работы нужен глобальный (внешний) массив Kvad[Sz][Sz], рабочие цифры начинаются с единицы, 0 - пустое место, пробел на графическом изображении. Тестирует и не полностью заполненные квадраты (0 в массиве игнорируется).

int Kvad[Sz][Sz];

//функция тестирует большой квадрат
//возвращает 0 - ошибка, 1 - правильно.

int fn_TestKvadrat(void)
{
int A,B,D,E;

for(int i = 0; i < Sz-1; i++)
 {
 for(int j = 0; j < Sz-1; j++)
  {
  A = Kvad[j][i]; if(A == 0) continue;

  for(int k = j+1; k < Sz; k++)
   {
   B = Kvad[k][i]; if(B == 0) continue;

   if(A == B)
    {
    for(int m = i+1; m < Sz; m++)
     {
     D = Kvad[j][m]; if(D == 0) continue;
     E = Kvad[k][m]; if(E == 0) continue;

     if((A == D) && (A == E)) return 0;     //неправильно
     }
    }
   }
  }
 }

return 1;      //правильно
}

[Nataly-Mak]

Alexu007

что-то в вашей программе строчек много.
Говорят, что программа эта состоит всего из 7 строк

И какой максимальный квадрат NxN проверяет ваша программа? Быстро проверяет?

svb тут жаловался, что программа Эда квадрат 169х169 долго проверяла в старой версии, в новой версии быстрее стала проверять.

Кстати, программа, которая на конкурсе проверяет вводимые решения, большие квадраты тоже очень долго проверяет. Прямо ощущение, что программа вообще зависла, несколько минут ждала, потом прерывала. Но иногда оказывалось, что решение уже проверено и записано, а браузер всё крутится и крутится, то есть выход из программы не срабатывает.

Проверка квадратов 289х289 и 361х361 была мучением. Несколько раз запускала.

dimkadimon
вот этот момент осветили бы...
Почему так плохо проверяются большие квадраты? Почему нет выхода из программы после проверки? Зависает браузер!
Это виноват мой браузер, или это виновата конкурсная программа?

Тупой перебор - он и в Африке тупой перебор

И Zealint тоже сообщал, что у него очень долго выполнялась проверка квадратов 289х289 и 361х361.

[Zealint]

Цитата:

И Zealint тоже сообщал, что у него очень долго выполнялась проверка квадратов 289х289 и 361х361.

Да, но не только долго проверялась (потому что на PHP), но гораздо дольше отправлялась.

(dimkadimon)

dimkadimon, небольшая поправка. Вы, наверно, мало говорите по-русски, но слова "это" и "этих", "этого" и т. д. мы пишем через "э", а не через "е".

[Nataly-Mak]

Zealint в сообщении #587164 писал(а):

Да, но не только долго проверялась (потому что на PHP), но гораздо дольше отправлялась.

Так я и говорю об отправке решений, то есть о вводе их на конкурсе. Там же программа проверяет решение, когда его введёшь. Вот об этой проверке я и говорю.

Был у меня такой момент: несколько минут ждала (около 10), браузер всё крутится; прервала, запустила по-новой. Отработало и выдалось сообщение: результат без улучшения

То есть решение было проверено и записано с первого раза, но браузер не остановился. А я не знала, что решение уже принято, и запустила второй раз.

[dimkadimon]

Nataly-Mak в сообщении #587161 писал(а):

dimkadimon
вот этот момент осветили бы...
Почему так плохо проверяются большие квадраты? Почему нет выхода из программы после проверки? Зависает браузер!
Это виноват мой браузер, или это виновата конкурсная программа?

Браузер зависает наверное потому что он на php и еше решение долго отправляется и записывается в базу даных. Сама программа быстрая и на моем компе проверяет квадраты (даже 361х361) за доли секунды: http://infinitesearchspace.dyndns.org/s ... uares.html

[Nataly-Mak]

То есть ваша программа эффективнее программы Эда?
Программа Эда так быстро большие квадраты не проверяет.

Правда, я в новой версии программы Эда большие квадраты ещё не пробовала проверять.
svb говорит, что в новой версии проверка выполняется быстрее.

-- Ср июн 20, 2012 10:12:21 --

Ах да... вспомнила, svb сообщал, что в новой версии программы Эда размер квадрата ограничен, не больше N=200x200.

А я сейчас хотела попробовать проверку квадрата 361х361, программа не стала работать. Сначала не поняла, потом вспомнила про сообщение svb.

[Alexu007]

Nataly-Mak в сообщении #587161 писал(а):

Alexu007

что-то в вашей программе строчек много.
Говорят, что программа эта состоит всего из 7 строк

И какой максимальный квадрат NxN проверяет ваша программа? Быстро проверяет?

Я не гнался за компактностью. И это не полноценная программа, а функция - часть программы, которую можно использовать при написании других программ.

Ограничений по максимуму нет, но с увеличением размеров квадрата её скорость разумеется будет сильно падать - всё таки простой перебор всех возможных прямоугольников внутри большого квадрата, вряд-ли тут придумаешь что-нибудь иное.

[Nataly-Mak]

Alexu007 в сообщении #587188 писал(а):

Ограничений по максимуму нет, но с увеличением размеров квадрата её скорость разумеется будет сильно падать - всё таки простой перебор всех возможных прямоугольников внутри большого квадрата, вряд-ли тут придумаешь что-нибудь иное.

Вот и я о том же говорю: тупой перебор он и есть тупой перебор, что тут можно придумать иное?

Но вот dimkadimon говорит, что его программа даже квадрат 361х361 проверяет доли секунды. Или это у него комп такой мощный?

Я попробовала в последней версии программы Эда (от 13 июня) проверить квадрат 171х171, проверялся более 3 минут.

Хотя...
svb утверждает, что даже в тупом переборе всегда можно найти некую "мелочь", которая кардинально изменяет перебор и, естественно, намного убыстряет выполнение программы.

[dimkadimon]

Nataly-Mak в сообщении #587147 писал(а):

Pavlovsky
изложенный вами алгоритм, основанный на теореме 4.12, вы изложили не полностью, а только для С - простых чисел.
Как делать разбиения, например, для C=9, вы так и не написали.
Поэтому, реализовав этот алгоритм для простых чисел по вашему описанию, я не смогла по этой же методе построить решения для С, являющихся степенью простых чисел.

Долго не могла придумать, как же строить разбиения для С=9. Потом бросила ваш метод и начала искать другой. И нашла! Там, в другой статье, приведён пример для С=4. Это я тут подробно изложила. Далее вышла на уникальные перестановки. Не сразу сообразила, как же построить уникальные перестановки для С=8,9,16.
Вы дали подсказку: "Возьми их из ОЛК". Но как взять, так и не сказали. Я долго искала решение (и здесь спрашивала, как же взять уникальные перестановки из ЛК, но вы... молчок ). Не могла догадаться, что надо брать не строки ЛК, а столбцы.

Потом была подсказка dimkadimon (в теме "Уникальные перестановки"). Он тоже не сразу догадался о столбцах. Но как только догадался, сразу же подсказал.

Для C=8, 9 и 16, можно использовать латинские квадраты двумя способами. Ваш способ - записать их колонки в строчки strong c-coloring и добавить строчки 11..11, 22..22 итд. Другой способ - использовать их строчки для записи разбиений, которые потом можно превратить в strong c-coloring. Оба метода работают и дают похожие результаты. Вот пример второго метода, имеем 2 ортогональных латинских квадрата:

А)
123
231
312

и

Б)
123
312
231

Перепишем квадрат Б):

Б2)
456
645
564

Добавим еше простой квадрат:

В)
789
789
789

Теперь используя А, Б2 и В получаем 3 разбиение цифр 1 до 9 на 3 группы по 3 числа. Читаем строчки сверха вниз с права на лево, берем одно число из каждого квадрата:

(1,4,7), (2,5,8), (3,6,9)
(2,6,7), (3,4,8), (1,5,9)
(3,5,7), (1,6,8), (2,4,9)

Должен согласится первый метод гораздо проше! Кстати C=8 и 16 я получил другим (третим) методом, а C=5 можно получить еше одним (четвертым!) методом. Поетому совсем не верно ети методы называть "базовыми" или "классическими" или "стандартными".

-- 20.06.2012, 16:28 --

Nataly-Mak в сообщении #587195 писал(а):

Alexu007 в сообщении #587188 писал(а):

Ограничений по максимуму нет, но с увеличением размеров квадрата её скорость разумеется будет сильно падать - всё таки простой перебор всех возможных прямоугольников внутри большого квадрата, вряд-ли тут придумаешь что-нибудь иное.

Вот и я о том же говорю: тупой перебор он и есть тупой перебор, что тут можно придумать иное?

Но вот dimkadimon говорит, что его программа даже квадрат 361х361 проверяет доли секунды. Или это у него комп такой мощный?

Я попробовала в последней версии программы Эда (от 13 июня) проверить квадрат 171х171, проверялся более 3 минут.

Хотя...
svb утверждает, что даже в тупом переборе всегда можно найти некую "мелочь", которая кардинально изменяет перебор и, естественно, намного убыстряет выполнение программы.

Выкладываю свою программу в Java. Тут есть несколько хитростей которые ее делают быстрее тупого перебора. Каждый прямоугольник задаем двумя противоположными углами (r1,c1) и (r2,c2), где r1<r2 и c1<c2. Если цвет a[r1][c1] не равен цвету a[r2][c1] можно смотреть дальше. Все ети "мелочи" заметно убыстряют программу. Программа Еда наверное медленее из за того что она графическая и из за того что она подсчитывает много других вешей, хотя точно не знаю.

  public boolean isOk(int[][] a)
  {
    for (int r1=0; r1<height-1; r1++)
      for (int r2=r1+1; r2<height; r2++)
        for (int c1=0; c1<width-1; c1++)
        {
          if (a[r1][c1]!=a[r2][c1]) continue;
          for (int c2=c1+1; c2<width; c2++)
            if (a[r1][c1]==a[r1][c2] && a[r1][c1]==a[r2][c2]) return false;   
        }
    return true;
  }

Кстати есть еше один метод для проверки. Етот метод хранит каждую строчку в C цифрах (одна цифра на каждый цвет) и использует операции над битами чтобы проверять совпадение цветов. Очень красивый метод, но к сожалению я не заметил что он быстрее моего. Вот тут тот метод: http://bit-player.org/2009/the-17x17-challenge

"One final hackerish note: What’s the best way to detect the presence of a monochromatic rectangle in a grid? My candidate goes like this. We encode the rows of the grid in a set of bit vectors–four vectors for each row, representing the four possible colors. For example, the red vector for a row has a 1 at each position where the corresponding node is red, and zeroes elsewhere. The blue vector has 1s for blue nodes, and so forth. Now we can detect a rectangle merely by taking the logical AND of two rows (an operation that could be a single machine instruction). A rectangle exists if and only if the result of the AND is nonzero. at least two bits are set in the resulting vector. "

[Nataly-Mak]

dimkadimon в сообщении #587211 писал(а):

Должен согласится первый метод гораздо проше! Кстати C=8 и 16 я получил другим (третим) методом, а C=5 можно получить еше одним (четвертым!) методом. Поетому совсем не верно ети методы называть "базовыми" или "классическими" или "стандартными".

Нет! Вы говорите об отдельных методах, для C=8, C=16, C=5.
Я же говорю о базовых алгоритмах!
Понимаете разницу между отдельными, частными методами и базовыми алгоритмами?

Я здесь выложила два базовых алгоритма: №1 и №2.

Базовый алгоритм работает не для каких-то отдельных С, а для любых С, или, по крайней мере, для большой группы С.

Например, базовый алгоритм №1 основан на уникальных перестановках или на непересекающихся комбинациях. Для всех С, для которых можно найти набор уникальных перестановок и/или непересекающихся комбинаций, этот алгоритм применим.

Вот в чём его универсальность. Поэтому совершенно правильно называть этот алгоритм базовым!

Аналогично базовый алгоритм №2, основанный на лемме 4.3.

Для C=5, к примеру, я получила решения и по базовому алгоритму №1 (два решения, первое из уникальных перестановок, второе из непересекающихся комбинаций), и по алгоритму, который был описан Pavlovsky в самом начале темы.

[всё это я опишу в статье]

Не знаю, какой там у вас четвёртый метод. Но это всего лишь частный метод! который, может быть, только для С=5 и работает.

-- Ср июн 20, 2012 12:19:35 --

Вот набор из 25 непересекающихся комбинаций из чисел 1,2,3,4,5:

1 1 1 1 1 
1 2 2 2 2 
1 3 3 3 3 
1 4 4 4 4 
1 5 5 5 5 
2 1 2 3 4 
2 2 3 4 5 
2 3 4 5 1 
2 4 5 1 2 
2 5 1 2 3 
3 1 3 5 2 
3 2 4 1 3 
3 3 5 2 4 
3 4 1 3 5 
3 5 2 4 1 
4 1 4 2 5 
4 2 5 3 1 
4 3 1 4 2 
4 4 2 5 3 
4 5 3 1 4 
5 1 5 4 3 
5 2 1 5 4 
5 3 2 1 5 
5 4 3 2 1 
5 5 4 3 2

Найден форумчанином на форуме nazva.net

Очень красивые комбинации! Закономерность и гармония!

И решение по базовому алгоритму №1 из этого набора получается элементарно.
Я даже нашла и изложила здесь два способа, как этот прямоугольник 25х5 strong-5-coloring превратить в квадрат 25х25 5-coloring. Оба способа очень простые в реализации.

Может быть, расскажете ваш четвёртый метод для С=5?
Научное любопытство

-- Ср июн 20, 2012 12:32:59 --

Решение для С=10, N=30x30, основанное на наборе уникальных перестановок, взятых из ОЛК 10-го порядка, я уже показала.

Сейчас собираюсь сделать решение для С=10, основанное на наборе из 50 непересекающихся комбинаций (этот набор выложен выше).

Решение это будет 50х100, а для конкурса всего квадрат 50х50. Но зато какое красивое решение!

И оба эти решения получаются по базовому алгоритму №1.

[Nataly-Mak]

Начала строить квадрат 50х50 из набора непересекающихся комбинаций из чисел 1,2,3,...,10. Не получился квадрат 10-coloring.
Посмотрела на комбинации, ошибся малость товарищ с того форума. Комбинации у него пересекаются.
Вот! Алгоритм не обманешь

Тема на форуме nazva.net:
http://nazva.net/forum/index.php/topic,7758.75.html

Он уже исправил ошибку, выложил другой набор комбинаций, теперь они не пересекаются.
И вот квадрат 50х50 10-coloring:

(Оффтоп)

1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5, 
1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6, 
1,3,3,3,3,3,3,3,3,3,2,4,4,4,4,4,4,4,4,4,3,5,5,5,5,5,5,5,5,5,4,6,6,6,6,6,6,6,6,6,5,7,7,7,7,7,7,7,7,7,
1,4,4,4,4,4,4,4,4,4,2,5,5,5,5,5,5,5,5,5,3,6,6,6,6,6,6,6,6,6,4,7,7,7,7,7,7,7,7,7,5,8,8,8,8,8,8,8,8,8, 
1,5,5,5,5,5,5,5,5,5,2,6,6,6,6,6,6,6,6,6,3,7,7,7,7,7,7,7,7,7,4,8,8,8,8,8,8,8,8,8,5,9,9,9,9,9,9,9,9,9, 
1,6,6,6,6,6,6,6,6,6,2,7,7,7,7,7,7,7,7,7,3,8,8,8,8,8,8,8,8,8,4,9,9,9,9,9,9,9,9,9,5,10,10,10,10,10,10,10,10,10, 
1,7,7,7,7,7,7,7,7,7,2,8,8,8,8,8,8,8,8,8,3,9,9,9,9,9,9,9,9,9,4,10,10,10,10,10,10,10,10,10,5,1,1,1,1,1,1,1,1,1, 
1,8,8,8,8,8,8,8,8,8,2,9,9,9,9,9,9,9,9,9,3,10,10,10,10,10,10,10,10,10,4,1,1,1,1,1,1,1,1,1,5,2,2,2,2,2,2,2,2,2, 
1,9,9,9,9,9,9,9,9,9,2,10,10,10,10,10,10,10,10,10,3,1,1,1,1,1,1,1,1,1,4,2,2,2,2,2,2,2,2,2,5,3,3,3,3,3,3,3,3,3, 
1,10,10,10,10,10,10,10,10,10,2,1,1,1,1,1,1,1,1,1,3,2,2,2,2,2,2,2,2,2,4,3,3,3,3,3,3,3,3,3,5,4,4,4,4,4,4,4,4,4, 
2,1,2,3,4,5,6,7,8,9,3,2,3,4,5,6,7,8,9,10,4,3,4,5,6,7,8,9,10,1,5,4,5,6,7,8,9,10,1,2,6,5,6,7,8,9,10,1,2,3, 
2,2,3,4,5,6,7,8,9,10,3,3,4,5,6,7,8,9,10,1,4,4,5,6,7,8,9,10,1,2,5,5,6,7,8,9,10,1,2,3,6,6,7,8,9,10,1,2,3,4, 
2,3,4,5,6,7,8,9,10,1,3,4,5,6,7,8,9,10,1,2,4,5,6,7,8,9,10,1,2,3,5,6,7,8,9,10,1,2,3,4,6,7,8,9,10,1,2,3,4,5, 
2,4,5,6,7,8,9,10,1,2,3,5,6,7,8,9,10,1,2,3,4,6,7,8,9,10,1,2,3,4,5,7,8,9,10,1,2,3,4,5,6,8,9,10,1,2,3,4,5,6, 
2,5,6,7,8,9,10,1,2,3,3,6,7,8,9,10,1,2,3,4,4,7,8,9,10,1,2,3,4,5,5,8,9,10,1,2,3,4,5,6,6,9,10,1,2,3,4,5,6,7, 
2,6,7,8,9,10,1,2,3,4,3,7,8,9,10,1,2,3,4,5,4,8,9,10,1,2,3,4,5,6,5,9,10,1,2,3,4,5,6,7,6,10,1,2,3,4,5,6,7,8, 
2,7,8,9,10,1,2,3,4,5,3,8,9,10,1,2,3,4,5,6,4,9,10,1,2,3,4,5,6,7,5,10,1,2,3,4,5,6,7,8,6,1,2,3,4,5,6,7,8,9, 
2,8,9,10,1,2,3,4,5,6,3,9,10,1,2,3,4,5,6,7,4,10,1,2,3,4,5,6,7,8,5,1,2,3,4,5,6,7,8,9,6,2,3,4,5,6,7,8,9,10, 
2,9,10,1,2,3,4,5,6,7,3,10,1,2,3,4,5,6,7,8,4,1,2,3,4,5,6,7,8,9,5,2,3,4,5,6,7,8,9,10,6,3,4,5,6,7,8,9,10,1, 
2,10,1,2,3,4,5,6,7,8,3,1,2,3,4,5,6,7,8,9,4,2,3,4,5,6,7,8,9,10,5,3,4,5,6,7,8,9,10,1,6,4,5,6,7,8,9,10,1,2, 
3,1,3,2,7,9,8,4,6,5,4,2,4,3,8,10,9,5,7,6,5,3,5,4,9,1,10,6,8,7,6,4,6,5,10,2,1,7,9,8,7,5,7,6,1,3,2,8,10,9, 
3,2,4,3,8,10,9,5,7,6,4,3,5,4,9,1,10,6,8,7,5,4,6,5,10,2,1,7,9,8,6,5,7,6,1,3,2,8,10,9,7,6,8,7,2,4,3,9,1,10, 
3,3,5,4,9,1,10,6,8,7,4,4,6,5,10,2,1,7,9,8,5,5,7,6,1,3,2,8,10,9,6,6,8,7,2,4,3,9,1,10,7,7,9,8,3,5,4,10,2,1, 
3,4,6,5,10,2,1,7,9,8,4,5,7,6,1,3,2,8,10,9,5,6,8,7,2,4,3,9,1,10,6,7,9,8,3,5,4,10,2,1,7,8,10,9,4,6,5,1,3,2, 
3,5,7,6,1,3,2,8,10,9,4,6,8,7,2,4,3,9,1,10,5,7,9,8,3,5,4,10,2,1,6,8,10,9,4,6,5,1,3,2,7,9,1,10,5,7,6,2,4,3, 
3,6,8,7,2,4,3,9,1,10,4,7,9,8,3,5,4,10,2,1,5,8,10,9,4,6,5,1,3,2,6,9,1,10,5,7,6,2,4,3,7,10,2,1,6,8,7,3,5,4, 
3,7,9,8,3,5,4,10,2,1,4,8,10,9,4,6,5,1,3,2,5,9,1,10,5,7,6,2,4,3,6,10,2,1,6,8,7,3,5,4,7,1,3,2,7,9,8,4,6,5, 
3,8,10,9,4,6,5,1,3,2,4,9,1,10,5,7,6,2,4,3,5,10,2,1,6,8,7,3,5,4,6,1,3,2,7,9,8,4,6,5,7,2,4,3,8,10,9,5,7,6, 
3,9,1,10,5,7,6,2,4,3,4,10,2,1,6,8,7,3,5,4,5,1,3,2,7,9,8,4,6,5,6,2,4,3,8,10,9,5,7,6,7,3,5,4,9,1,10,6,8,7, 
3,10,2,1,6,8,7,3,5,4,4,1,3,2,7,9,8,4,6,5,5,2,4,3,8,10,9,5,7,6,6,3,5,4,9,1,10,6,8,7,7,4,6,5,10,2,1,7,9,8, 
4,1,4,7,9,6,2,10,5,8,5,2,5,8,10,7,3,1,6,9,6,3,6,9,1,8,4,2,7,10,7,4,7,10,2,9,5,3,8,1,8,5,8,1,3,10,6,4,9,2, 
4,2,5,8,10,7,3,1,6,9,5,3,6,9,1,8,4,2,7,10,6,4,7,10,2,9,5,3,8,1,7,5,8,1,3,10,6,4,9,2,8,6,9,2,4,1,7,5,10,3, 
4,3,6,9,1,8,4,2,7,10,5,4,7,10,2,9,5,3,8,1,6,5,8,1,3,10,6,4,9,2,7,6,9,2,4,1,7,5,10,3,8,7,10,3,5,2,8,6,1,4, 
4,4,7,10,2,9,5,3,8,1,5,5,8,1,3,10,6,4,9,2,6,6,9,2,4,1,7,5,10,3,7,7,10,3,5,2,8,6,1,4,8,8,1,4,6,3,9,7,2,5, 
4,5,8,1,3,10,6,4,9,2,5,6,9,2,4,1,7,5,10,3,6,7,10,3,5,2,8,6,1,4,7,8,1,4,6,3,9,7,2,5,8,9,2,5,7,4,10,8,3,6, 
4,6,9,2,4,1,7,5,10,3,5,7,10,3,5,2,8,6,1,4,6,8,1,4,6,3,9,7,2,5,7,9,2,5,7,4,10,8,3,6,8,10,3,6,8,5,1,9,4,7, 
4,7,10,3,5,2,8,6,1,4,5,8,1,4,6,3,9,7,2,5,6,9,2,5,7,4,10,8,3,6,7,10,3,6,8,5,1,9,4,7,8,1,4,7,9,6,2,10,5,8, 
4,8,1,4,6,3,9,7,2,5,5,9,2,5,7,4,10,8,3,6,6,10,3,6,8,5,1,9,4,7,7,1,4,7,9,6,2,10,5,8,8,2,5,8,10,7,3,1,6,9, 
4,9,2,5,7,4,10,8,3,6,5,10,3,6,8,5,1,9,4,7,6,1,4,7,9,6,2,10,5,8,7,2,5,8,10,7,3,1,6,9,8,3,6,9,1,8,4,2,7,10,
4,10,3,6,8,5,1,9,4,7,5,1,4,7,9,6,2,10,5,8,6,2,5,8,10,7,3,1,6,9,7,3,6,9,1,8,4,2,7,10,8,4,7,10,2,9,5,3,8,1, 
5,1,6,8,5,4,9,3,10,7,6,2,7,9,6,5,10,4,1,8,7,3,8,10,7,6,1,5,2,9,8,4,9,1,8,7,2,6,3,10,9,5,10,2,9,8,3,7,4,1, 
5,2,7,9,6,5,10,4,1,8,6,3,8,10,7,6,1,5,2,9,7,4,9,1,8,7,2,6,3,10,8,5,10,2,9,8,3,7,4,1,9,6,1,3,10,9,4,8,5,2, 
5,3,8,10,7,6,1,5,2,9,6,4,9,1,8,7,2,6,3,10,7,5,10,2,9,8,3,7,4,1,8,6,1,3,10,9,4,8,5,2,9,7,2,4,1,10,5,9,6,3, 
5,4,9,1,8,7,2,6,3,10,6,5,10,2,9,8,3,7,4,1,7,6,1,3,10,9,4,8,5,2,8,7,2,4,1,10,5,9,6,3,9,8,3,5,2,1,6,10,7,4, 
5,5,10,2,9,8,3,7,4,1,6,6,1,3,10,9,4,8,5,2,7,7,2,4,1,10,5,9,6,3,8,8,3,5,2,1,6,10,7,4,9,9,4,6,3,2,7,1,8,5, 
5,6,1,3,10,9,4,8,5,2,6,7,2,4,1,10,5,9,6,3,7,8,3,5,2,1,6,10,7,4,8,9,4,6,3,2,7,1,8,5,9,10,5,7,4,3,8,2,9,6, 
5,7,2,4,1,10,5,9,6,3,6,8,3,5,2,1,6,10,7,4,7,9,4,6,3,2,7,1,8,5,8,10,5,7,4,3,8,2,9,6,9,1,6,8,5,4,9,3,10,7, 
5,8,3,5,2,1,6,10,7,4,6,9,4,6,3,2,7,1,8,5,7,10,5,7,4,3,8,2,9,6,8,1,6,8,5,4,9,3,10,7,9,2,7,9,6,5,10,4,1,8, 
5,9,4,6,3,2,7,1,8,5,6,10,5,7,4,3,8,2,9,6,7,1,6,8,5,4,9,3,10,7,8,2,7,9,6,5,10,4,1,8,9,3,8,10,7,6,1,5,2,9, 
5,10,5,7,4,3,8,2,9,6,6,1,6,8,5,4,9,3,10,7,7,2,7,9,6,5,10,4,1,8,8,3,8,10,7,6,1,5,2,9,9,4,9,1,8,7,2,6,3,10

Красивый квадратик! Его можно продолжить до прямоугольника 50х100 10-coloring.
Будет половина квадрата 100х100. А второй половины нету у меня

Вот интересный вопрос: можно ли найти 100 непересекающихся комбинаций из чисел 1,2,3,...,10?

Товарищ, который нашёл 50 комбинаций, искал их, конечно, по программе. Пишет, что программа работала очень долго, но больше 50 комбинаций не дала.
Не поняла, выполнился ли у него полный перебор, или просто ему надоело ждать и он прервал программу. Скорее всего, прервал.

Если всё же прямоугольник 100х10 strong-10-coloring (100 непересекающихся комбинаций) существует, тогда и решение C=10, N=100x100 тоже существует.