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

[Nataly-Mak]

И опять в работе решения для С=10,12,14,15,18,20,21



-- Вт июл 31, 2012 14:16:34 --

Слёзы ёжика

Бедный ёжик плачет А почему он плачет? Потому что он останется в третьем классе на второй год

Вот простой пример, который ёжик решил.
Есть 3-сильная раскраска 9х4.
Задача такая: добавить к этой раскраске 2 строки и один цвет, чтобы получилась 4-сильная раскраска 11х4.

Вот исходная 3-сильная раскраска 9х4:



Эту задачу ёжик решает так:
первую строку приписывает из одного цвета 4 (одноцветная); получается 4-сильная раскраска 10х4. Теперь надо добавить ещё одну строку.
Ёжик загоняет раскраску 10х4 в программу Эда, добавляет рандомом 11-ую строку и удаляет все возникшие коллизии вручную

[хотя программа Эда не проверяет ошибки в С-сильной раскраске, ёжик делает это сам визуально]

Вот такая 4-сильная раскраска 11х4 получилась в результате этой процедуры:



А теперь ёжику надо выполнить то же самое только для 17-сильной раскраски 289х18.
Ну, первую одноцветную строку (из цвета 18) ёжик, конечно, добавляет, получает 18-сильную раскраску 290х18.
А как добавить вторую строку, чтобы получить 18-сильную раскраску 291х18
Трюк с рандомом в программе Эда повторить невозможно.
Что же делать бедному ёжику?

Ёжику чрезвычайно интересно, существует ли красивый алгоритм для решения этой задачи?
Такой алгоритм, который можно формализовать и запрограммировать. Ну, не вручную же, в самом деле, удалять все возникшие коллизии!

Ясное дело, что если такой алгоритм существует, описание его ёжик будет ждать после окончания конкурса.

Итак, решения для C=18,20,21 в третьем классе пока не поддаются ёжику

[dimkadimon]

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

Ёжику чрезвычайно интересно, существует ли красивый алгоритм для решения этой задачи?
Такой алгоритм, который можно формализовать и запрограммировать. Ну, не вручную же, в самом деле, удалять все возникшие коллизии!

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

[Nataly-Mak]

Ха! Про алгоритм отжига ёжик давным-давно знает

[Nataly-Mak]

Ёжик продолжает эксперименты.
Пришла такая идея: что мешает добавить к 4-сильной раскраске 11х4 (которая принадлежит классу 3) ещё одну строку и получить 4-сильную раскраску 12х4, которая принадлежит уже классу 4? А ничего не мешает!
Загоняем 4-сильную раскраску 11х4 в программу Эда и вручную подбором делаем 4-сильную раскраску 12х4:



Всё очень просто для маленьких С.
А теперь попробуйте-ка сделать то же самое для 9-сильной раскраски 81х10

Алгоритм отжига пока дал 10-сильную раскраску 84х10 с 5 ошибками.

Красивого алгоритма для решения этой задачи ёжик не знает

-- Ср авг 01, 2012 13:00:22 --

Добавилась и четвёртая строка! Получена 4-сильная раскраска 13х4, это уже класс 5.
Эта раскраска даёт решение 17х16 4-coloring. Столбца не хватает до решения C4N17, которое не является очень простым, его искали долго.



-- Ср авг 01, 2012 13:20:34 --

И... добавилась пятая строка! Получена 4-сильная раскраска 14х4:

4,14,D,A,A,A,B,A,D,D,C,C,C,A,B,D,C,B,B,C,A,C,C,A,B,B,A,C,B,D,A,A,C,C,C,B,D,C,C,D,A,D,A,B,A,B
,B,B,B,A,D,C,D,B,A,D,D,A

Эта раскраска даёт решение 18х16 4-coloring. Два столбца не хватает до максимального решения C4N18.

Так, это уже класс 6
Ну и что что маленькое С, ёжик учится на простом примере

А 10-сильной раскраски 86х10 в классе 6 ни у кого нет (?)
Иначе было бы выложено решение C10N96.

-- Ср авг 01, 2012 13:31:59 --

Фантастика! Добавилась и шестая строка, вот 4-сильная раскраска 15х4:

4,15,D,A,A,A,B,A,D,D,C,C,C,A,B,D,C,B,B,C,A,C,C,A,B,B,A,C,B,D,A,A,C,C,C,B,D,C,C,D,A,D,A,B,A,B
,B,B,B,A,D,C,D,B,A,D,D,A,D,D,B,C

Эта раскраска даёт решение 19х16 4-coloring.
А какой максимальный прямоугольник 4-coloring? Где-то встречала при просмотре статей, но забыла. Как-то на прямоугльники почти не обращала внимание.

[Nataly-Mak]

И последняя 4-сильная раскраска 16х4:

4,16,D,A,A,A,B,A,D,D,C,C,C,A,B,D,C,B,B,C,A,C,C,A,B,B,A,C,B,D,A,A,C,C,C,B,D,C,C,D,A,D,A,B,A,B
,B,B,B,A,D,C,D,B,A,D,D,A,D,D,B,C,D,B,C,D

Дальше у меня строки не добавляются уже так легко. Можно ли добавить ещё строку в принципе? Я этого не знаю.

Максимальный прямоугольник, полученный этим способом, 20х16 4-coloring.
Вроде есть больше прямоугольник 4-coloring? Что-то мне запомнилось число 21, вроде 21 строка максимум в прямоугольнике 4-coloring... А сколько столбцов максимум?

[Nataly-Mak]

Такой вопрос возник: любому ли комплекту попарно ортогональных ЛК порядка n=C соответствует С-сильная раскраска? И наоборот.

Я раньше считала, что это так. Но сейчас что-то начала сомневаться.

-- Ср авг 01, 2012 20:54:19 --

Из прямоугольника 20х16 4-coloring получила оригинальное решение C4N18 с 4 дырками:



Интересно, что окрашивание любой дырки в любой из 4 цветов даёт 4 ошибки, итого 16 ошибок при любой раскраске дырок.
Любопытное решение. Кстати, очень напоминает решение C5N30 с пустым подквадратом 5х5, который также расположен в правом нижнем углу квадрата.
А-а-а, так можно получить и аналогичное решение C4N20 с пустым подквадратом 4х4, причём это будет регулярное решение.
Ну, а у меня решение C4N18 с пустым подквадратом 2х2 нерегулярное.

Я тут давно просила показать оригинальные решение C4N18. Что-то не вижу

Есть первое решение, которое всем хорошо известно из Интернета, и второе оригинальное решение - решение Тома.

[Nataly-Mak]

До кучи:



Здесь тоже окрашивание любой дырки в любой из 4-х цветов даёт 4 ошибки.

-- Ср авг 01, 2012 21:38:15 --

Tom Sirgedas возглавляет большую группу джентльменов, причём уже очень давно:

Цитата:

10 Tom Sirgedas 19.638600 06-06-2012 @ 23:11:18
11 Il brigante Pennastorta 19.638600 06-08-2012 @ 08:28:33
12 Vladimir Chirkov 19.638600 07-10-2012 @ 07:04:16
13 Juha Saukkola 19.638600 07-31-2012 @ 03:06:51

Конкурсанты подтягиваются к этой группе довольно активно, на подходе конкурсант с 14-го места.
Интересно, кто первый потеснит Тома с 10-ой позиции.

-- Ср авг 01, 2012 22:08:39 --

6-сильная раскраска 27х6 (из 5-сильной раскраски 25х6) получается алгоритмом отжига мгновенно:



Pavlovsky
как специалист по классу 3, оцените решение ёжика

[dimkadimon]

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

Я тут давно просила показать оригинальные решение C4N18. Что-то не вижу

Есть первое решение, которое всем хорошо известно из Интернета, и второе оригинальное решение - решение Тома.

Вот мои оригинальные решения для C4N18. Я не проверял насколько они отличаются от известных решений. Решения построены таким же методом как в статье Bernd Steinbach и Christian Posthoff, только вместо SAT solver я использовал метод отжига. Моя интуиция подсказывала что метод отжига гораздо легче запрограмировать и результат будет получен быстрее. Оказалось действительно так - каждое из этих решений я нашёл примерно через час/полтора (вместо 5-7 часов). Кстати вся программа достаточно маленькая, примерно 300 строчек в Java. В конце соревнования я её покажу.

(Оффтоп)

2,3,4,1,4,1,3,2,2,4,1,3,2,4,3,1,4,3,
3,3,3,4,1,2,1,4,1,1,3,2,2,2,2,1,4,4,
4,4,2,2,2,4,3,3,4,1,3,1,2,3,1,3,4,1,
2,1,4,2,3,4,2,4,3,1,1,4,1,2,3,3,1,2,
3,1,2,1,1,3,4,4,4,4,2,3,3,2,4,3,2,1,
1,1,1,4,2,2,3,2,4,3,2,4,3,4,1,1,3,2,
2,1,4,3,2,3,1,1,4,3,3,2,4,1,3,4,2,4,
4,2,2,4,1,1,2,2,3,4,3,2,3,1,1,4,1,3,
3,4,4,4,3,2,2,3,2,3,4,1,1,1,4,1,2,3,
1,4,3,2,3,3,3,2,1,4,1,4,4,1,2,2,2,1,
1,3,2,3,3,1,4,1,2,1,4,4,3,3,2,4,4,2,
2,4,2,1,3,2,4,1,1,2,3,3,1,4,1,2,3,4,
4,1,3,3,2,1,2,4,1,2,4,1,4,4,2,3,3,3,
3,4,1,2,4,1,1,4,2,2,2,2,1,3,3,4,3,1,
4,3,1,1,4,3,2,3,3,1,2,4,2,1,4,2,3,4,
3,2,1,3,1,4,3,1,3,2,1,1,2,4,4,4,2,2,
2,2,3,4,4,4,4,1,3,3,2,3,4,3,2,1,1,1,
1,2,3,1,2,4,1,3,2,4,4,1,3,2,3,2,1,4

2,1,1,4,1,4,2,1,4,4,1,3,2,3,3,2,4,3,
3,2,4,1,2,3,2,1,4,1,4,3,1,4,1,4,3,2,
1,3,1,3,4,1,4,4,4,3,2,4,1,3,2,2,1,2,
2,4,1,1,2,4,3,4,1,3,3,3,3,2,2,4,2,1,
2,3,2,1,3,1,3,4,2,4,1,2,4,4,3,1,3,2,
1,4,4,2,3,3,4,3,2,3,1,1,4,2,1,2,4,1,
2,2,3,2,1,4,4,2,3,3,2,1,1,4,4,1,3,3,
4,3,1,2,4,4,1,3,3,2,4,3,4,1,1,1,2,2,
3,4,2,2,3,2,2,1,3,4,4,4,3,3,2,1,1,1,
3,3,3,4,1,1,2,2,2,1,3,4,4,1,4,4,2,1,
4,4,3,3,3,2,1,2,4,1,1,3,2,2,4,3,1,2,
1,1,3,2,2,3,3,4,1,1,4,2,2,3,4,1,4,4,
3,2,4,3,4,2,3,3,1,4,1,2,1,1,4,2,2,3,
4,1,3,1,2,2,4,3,2,4,2,1,3,1,3,4,1,4,
3,4,2,4,4,1,1,1,1,3,2,1,2,4,3,3,2,4,
4,3,4,4,1,3,2,4,1,2,2,2,3,2,1,3,1,3,
4,1,2,3,2,3,1,2,3,2,3,4,1,4,3,2,4,1,
1,2,4,1,1,4,1,3,2,2,3,4,2,3,2,3,3,4

2,1,3,2,1,2,3,4,1,4,4,4,4,2,1,3,3,3,
2,3,3,1,1,3,4,3,2,1,4,2,2,1,4,1,4,2,
2,4,2,4,2,3,2,4,1,3,1,1,3,1,3,3,4,4,
4,3,2,4,4,1,1,2,3,3,4,3,2,4,1,1,2,3,
1,4,4,3,4,2,4,3,3,2,3,4,1,1,1,3,2,2,
3,1,2,1,4,2,1,3,4,4,1,2,3,3,2,4,4,3,
3,1,4,2,3,1,2,1,4,2,4,3,2,1,2,3,1,4,
3,3,4,3,2,4,3,1,1,2,2,2,4,4,3,1,4,1,
3,4,2,2,1,3,1,1,3,4,2,1,1,4,4,2,3,2,
4,1,4,2,2,3,3,4,2,1,3,3,1,3,4,4,2,1,
3,2,3,1,2,2,4,4,4,3,3,1,2,4,1,2,1,1,
2,3,1,4,3,4,1,2,4,2,3,4,3,1,4,2,3,1,
1,2,2,4,1,1,4,3,2,2,1,3,4,2,3,4,3,1,
4,4,1,3,3,3,2,1,4,1,1,2,4,2,1,2,2,3,
1,4,3,3,2,4,1,2,1,1,4,3,3,2,2,4,1,2,
2,2,1,1,3,1,3,3,1,3,2,4,1,4,2,4,2,4,
4,2,3,2,3,4,4,2,3,4,1,2,1,3,3,1,1,4,
1,1,1,3,4,2,2,2,2,3,2,1,4,3,4,1,3,4

[whitefox]

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

Такой вопрос возник: любому ли комплекту попарно ортогональных ЛК порядка n=C соответствует С-сильная раскраска? И наоборот.

Если повернуть $C$-сильно окрашенный прямоугольник с числом строк $C^2$ на $90^{\circ}$ против часовой стрелки, то получится "ортогональная таблица" по Холлу.

В общем случае $C$-сильно окрашенный прямоугольник $N\times M$ взаимно-однозначно соответствует комплекту из $M$ попарно ортогональных прямоугольников $\lfloor N/C\rfloor\times C$, в которых последняя строка, может быть, заполнена не полностью.

[Nataly-Mak]

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

Оказалось действительно так - каждое из этих решений я нашёл примерно через час/полтора (вместо 5-7 часов). Кстати вся программа достаточно маленькая, примерно 300 строчек в Java. В конце соревнования я её покажу.

Где-то на форуме конкурса, если ничего не путаю, было сообщение, что кому-то удаётся строить решения C4N18 за считанные секунды. Не напутала?

-- Чт авг 02, 2012 07:28:43 --

whitefox в сообщении #602139 писал(а):

Если повернуть $C$-сильно окрашенный прямоугольник с числом строк $C^2$ на $90^{\circ}$ против часовой стрелки, то получится "ортогональная таблица" по Холлу.

Спасибо.

Хотя Холла немного читала, но было это три года назад, когда занималась ЛК.
Поясните, пожалуйста, что такое "ортогональная таблица" по Холлу.

Я вчера запарилась с преобразованиями ЛК 17-го порядка.
Вроде построила полный комплект попарно ортогональных ЛК. Правда, проверить попарную ортогональноять всех ЛК не хватило терпения (программа проверки ортогональности у меня сохранилась с тех пор, когда занималась ортогональными ЛК, она много раз испытана и работает правильно), проверила только ортогональность со всеми ЛК для первых трёх ЛК.
Строю из этого комплекта ЛК 17-сильную раскраску и... она не получается 17-сильная.
Голова пошла крУгом

Много раз строила С-сильные раскраски из полных комплектов попарно ортогональных ЛК, несколько раз выполняла обратную процедуру: восстанавливала по С-сильной раскраске, содержащей N^2 строк и (С+1) столбцов, полный комплект из (С-1) попарно ортогональных ЛК порядка N. И была уверена, что между этими объектами существует взаимно-однозначное соответствие.
Но вчерашний эксперимент с ЛК 17-го порядка пошатнул мою уверенность
Что тут может быть? Не все ЛК у меня взаимно ортогональны?

[dimkadimon]

whitefox в сообщении #602139 писал(а):

В общем случае $C$-сильно окрашенный прямоугольник $N\times M$ взаимно-однозначно соответствует комплекту из $M$ попарно ортогональных прямоугольников $\lfloor N/C\rfloor\times C$, в которых последняя строка, может быть, заполнена не полностью.

http://designtheory.org/library/encyc/mols/a/

[Nataly-Mak]

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

http://designtheory.org/library/encyc/mols/a/

Эх-ма!
Эту бы ссылку да в самом начале конкурса
Тут как раз показано то самое "четвёртое разбиение", в поисках которого я много ночей не спала. И всё-таки нашла его сама!

-- Чт авг 02, 2012 07:51:39 --

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

Итак, составляю разбиения:

1 группа, шаг (1,0):
{1,2,3}, {4,5,6}, {7,8,9}

2 группа, шаг (1,1):
{1,5,9}, {4,8,3}, {7,2,6}

3 группа, шаг (1,2):
{1,8,6}, {4,2,9}, {7,5,3}

Эти три группы я нашла в соответствии с описанием Pavlovsky.
О последнем разбиении я ничего не знаю, поэтому выбираю его наобум:

4 группа:
{1,4,7}, {2,5,8}, {3,6,9}

Это может быть неправильное разбиение.

Далее строю на основе этих разбиений прямоугольник 9х4 strong-3-coloring:

1 1 1 1
1 3 2 2
1 2 3 3
2 2 2 1
2 1 3 2
2 3 1 3
3 3 3 1
3 2 1 2
3 1 2 3

Прямоугольник получился strong-3-coloring, несмотря на то, что четвёртое разбиение я нашла не по теореме 4.12.

Это была моя маленькая победа, очень приятная! И это был всего только первый класс решений

Во втором классе я тоже нашла свой способ построения регулярных решений. Это была ещё одна победа.

А вот в третьем классе застряла

[Pavlovsky]

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

Поясните, пожалуйста, что такое "ортогональная таблица" по Холлу.

http://www.natalimak1.narod.ru/arry.htm

Цитата:

Даже поняла, как Холл этот ортогональный массив строит.

post180671.html?sid=8afbdd961d1eab7db4e8c063d6a890a4#p180671

[Nataly-Mak]

Ага, вот значит как
Было какое-то понимание ортогонального массива, когда "грызла" эти самые массивы по книге Холла

Надо свои статьи почитать, значит

Так "ортогональная таблица" это и есть тот самый ортогональный массив

[Pavlovsky]

Ортогональный массив strength 2 and index 1 - это сильноокрашенный прямоугольник! Надо порыть эту тему.