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

[Nataly-Mak]

И 34х34 есть!!

-- Сб июн 23, 2012 11:51:08 --

И 35х35 есть!

Обратите внимание, как быстро достраиваю

Вот теперь действительно остался последний шажочек.
Неужели не достроится? Быть такого не может!

[Pavlovsky]

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

Расстояния между одинаковыми цифрам подчиняются определённым закономерностям. Например, если есть одноцветный прямоугольник, то обязательно имеется пара одинаковых расстояний между номерами этого цвета, обратное не верно.

Хорошое свойство. Надо придумать необходимое и достаточное условие существования запрещенного прямоугольника. Тогда перебор будет очень шустрым.
Наверно у svb есть хорошия условия существования запрещенного прямоугольника в диагональных решениях. Ведь как то он справился с перебором при поиске решения 36х36 для С=6.

PS Сергей почему не учавствуете в конкурсе? Зачем отличные решения складывать под подушку?

[Nataly-Mak]

Всё! Последний рубеж пройден, решение C=6, N=36x36 получено!

А дьявольски красивое получилось решение. Ну, пока не буду показывать

Конечно, диагональное красивее, но у меня пока диагонального нет.

Очень долго я шла к этому решению. Тут были и уникальные перестановки, и непересекающиеся комбинации, и метод достраивания. Это было чрезвычайно интересное исследование!

Pavlovsky
вы сообщали, что в книге Картеси описывается построение диагональных решений.
И вы даже экспериментировали с этим методом, но ничего хорошего не нашли.

А вот, оказывается, существует весьма интересное диагональное решение 36х36 для C=6.
Не исключено, что существует и диагональное решение 100x100 для C=10.

[Pavlovsky]

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

Расстояния между одинаковыми цифрам подчиняются определённым закономерностям. Например, если есть одноцветный прямоугольник, то обязательно имеется пара одинаковых расстояний между номерами этого цвета, обратное не верно.

А почему неверно??

В первом, приведенном Наталией решении, в один цвет красятся разорванные диагонали.
Во втором, приведенном Наталией решении, в один цвет красятся диагонали. То есть разорванная диагональ может быть покрашена в два цвета.

Так если красить в один цвет разорванные диагонали, то верно и обратное утверждение.
Пронумеруем диагонали по номеру в первой строке. Пусть в нашем квадрате есть запрещенный прямоугольник.
Возьмем пару его верхних точек. Расстояние между этими точками равно модулю номеров диагоналей которым они принадлжат. Аналогично для нижней пары.

-- Сб июн 23, 2012 13:26:14 --

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

Pavlovskyвы сообщали, что в книге Картеси описывается построение диагональных решений. И вы даже экспериментировали с этим методом, но ничего хорошего не нашли.А вот, оказывается, существует весьма интересное диагональное решение 36х36 для C=6.Не исключено, что существует и диагональное решение 100x100 для C=10.

В своих планах исследования я уже снял с этого направления пометку "малоперспективно".

[svb]

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

Сергей почему не учавствуете в конкурсе? Зачем отличные решения складывать под подушку?

Пока особых успехов нет. С грехом пополам только что разобрался с GF(16), т.е. вышел на результат 13. Пора переходить к составным C - для C=6 просто перебор был быстрым. Картинки, правда, удалось получить красивыми даже для всех простых C, что и завораживает. Это не чистые диагонали, но явно просматривается диагональная структура.

[Nataly-Mak]

Мне удалось достраиванием только что полученного решения 36х36 получить прямоугольник 37х36 6-coloring! И тоже весьма интересный прямоугольник получился.

Кто-нибудь пробовал получить решение 37х37 для C=6?

-- Сб июн 23, 2012 12:52:05 --

Кстати, я стала 14-ым участником, одолевшим решение C=6, N=36x36:

6 36 1296  Alex Chernov @ 23:02:26 on 05-31-2012 14

svb
вы вступите в игру, когда наберёте 19,99 баллов?

[Pavlovsky]

Цитата:

5 Artem Karavaev 19.823100 06-23-2012 @ 10:44:21

Artem Karavaev вышел за пределы джентельменского набора решений!

14  Sigi S 18.946100 06-21-2012 @ 23:36:50 
15  Natalya Makarova 18.908400 06-23-2012 @ 14:02:34 

Дамский набор решений тоже радует.

[Nataly-Mak]

13 Wes Sampson 18.979700 06-10-2012 @ 07:54:57
14 Sigi S 18.946100 06-21-2012 @ 21:36:50
15 Natalya Makarova 18.908400 06-23-2012 @ 12:02:34
16 Martin Richardt 18.521200 06-17-2012 @ 16:24:47
17 Aicke Hinrichs 18.431700 06-22-2012 @ 00:52:34
18 Markus Egli 18.430000 06-11-2012 @ 15:51:59
19 Roy van Rijn 18.324600 06-22-2012 @ 12:00:09
20 Rodolfo Niborski 18.030100 06-20-2012 @ 10:42:01

Все эти конкурсанты находятся в зоне 18 баллов с хвостиком.
Высокий порог! За ним идёт последняя зона - 19 баллов с хвостиком.

-- Сб июн 23, 2012 13:12:47 --

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

Дамский набор решений тоже радует.

Pavlovsky
если бы вы были джентльменом и помогли даме разобраться с теоремой 4.12 (под помощью я имею в виду чисто техническую помощь - нормальный перевод текста на русский язык; никакие подсказки мне не нужны!), то дама, возможно, имела бы джентльменский набор решений.

Но вы, увы, не джентльмен

[Pavlovsky]

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

Не исключено, что существует и диагональное решение 100x100 для C=10.

Если будем расскрашивать разорванные диагонали в один цвет. Тогда решение определяется первой строкой. Это 10^100 вариантов. Цифра завораживает, даже если удастся:

1) Определить условия корректности первой строки без необходимости строить остальной квадрат.
2) Будут хорошие отсечения.
3) Просто повезет быстро построить корректную первую строку.

В этом направлении еще думать и думать, пока получится реальный алгоритм.

[Nataly-Mak]

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

1) Определить условия корректности первой строки без необходимости строить остальной квадрат.

Так ведь всё и определяется именно первой строкой.
Только вот в одних случаях эта строка имеет длину n, а в других случаях длину 2n-1 (n - сторона квадрата).

Я пока не поняла, в каких случаях первое, а в каких - второе.
Моя гипотеза такая: для чётных n строка имеет длину n, а для нечётных n - строка имеет длину 2n-1.

В имеющихся у меня примерах для n=16 строка имеет длину 16, для n=17 строка имеет длину 33.

Предполагаю, что для C=6 в квадрате 36х36 всё определяется первой строкой квадрата длиной 36. Далее идёт нормальный циклический сдвиг по строкам.

Если моя гипотеза верна, то для C=10 всё будет определяться первой строкой квадрата 100х100 длиной 100. Даже если это так, найти правильную первую строку очень сложно.

Ещё важно! При поиске первой строки нужно знать условия её корректности, о чём здесь говорилось. Тогда поиск сделается осмысленным. Разумеется, тупой перебор здесь захлебнётся.

-- Сб июн 23, 2012 13:37:02 --

Цитата:

Моя гипотеза такая: для чётных n строка имеет длину n, а для нечётных n - строка имеет длину 2n-1.

Нет, неверная гипотеза. Это зависит, наверное, не от стороны квадрата, а от количества цветов.

Посмотрела все диагональные решения для C=5, во всех надо искать строку длиной 2n-1.

Тогда такая гипотеза:
для С чётных строка длиной n, для С нечётных строка длиной 2n-1.

-- Сб июн 23, 2012 14:16:30 --

Почти диагональное решение 22х22 7-coloring:

[Nataly-Mak]

И почти диагональное решение 23х23 8-цветное:



Мне очень нравятся диагональные решения

Ну, хорошо. Для C=4 и С=5 я здесь привела диагональные решения из статьи.
Для С=6 у svb такое решение под подушкой

А для С=3 существует диагональное решение? Скажем, 9х9 или 10х10.

-- Сб июн 23, 2012 14:53:03 --

А вот оно!



Стоп!
Наврала. Это решение 4-цветное.
Я сделала в программе Эда уменьшение количества цветов с 4-х до 3-х, думала, что всё автоматически и уменьшилось. А сейчас рассмотрела внимательно, здесь по-прежнему 4 цвета.

-- Сб июн 23, 2012 15:16:18 --

Пока для C=3 получилось только диагональное решение 6х6:



-- Сб июн 23, 2012 15:27:38 --

Это решение в числах:

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

Здесь происходит циклический сдвиг строки из 11 элементов:

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

Гипотеза вроде бы подтверждается, здесь С нечётное.

Кто может представить диагональное решение для C=3 бОльшего размера?

-- Сб июн 23, 2012 15:37:43 --

И наконец диагональное решение для С=2 4х4:



В числах:

1,1,2,2,
1,2,2,1,
2,2,1,1,
2,1,1,2

Здесь нормальный циклический сдвиг по строкам.
Опять гипотеза подтверждается!

[svb]

Nataly-Mak писал(а):

Кто может представить диагональное решение для C=3 бОльшего размера?

A,A,B,A,B,C,C,B,C,
A,B,A,B,C,C,B,C,A,
B,A,B,C,C,B,C,A,A,
A,B,C,C,B,C,A,A,B,
B,C,C,B,C,A,A,B,A,
C,C,B,C,A,A,B,A,B,
C,B,C,A,A,B,A,B,C,
B,C,A,A,B,A,B,C,C,
C,A,A,B,A,B,C,C,B,

[Nataly-Mak]

О!
Спасибо! Очень красиво.
Сейчас перепишу в числах, проанализирую. Мне почему-то с символами совсем не нравится работать, я привыкла работать с числами.

А 10х10 нету?

Хотя вроде видно, что в этом решении происходит нормальный циклический сдвиг по строкам.

Значит, моя гипотеза неверна.

svb
а для C=5 есть диагональное решение, в котором происходит нормальный циклический сдвиг по строкам?
Среди решений, приведённых в статье, такого решения нет (со стороной квадрата 17, 18, 19, 20).

Предположу, что максимальное диагональное решение для C цветов имеет размер C^2xC^2.
Вот для C=3 9x9 представили, а 10х10 уже нет?
Для С=4 16х16 есть в статье.
Для С=5 25х25 и для C=6 36x36 есть у svb.
Для C=2 4x4 я представила.

А для C=7 49x49 у кого-нибудь есть диагональное решение?

Нет, выкладывать, конечно, не надо. Просто сообщите, что есть

[svb]

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

а для C=5 есть диагональное решение, в котором происходит нормальный циклический сдвиг по строкам?
Среди решений, приведённых в статье, такого решения нет (со стороной квадрата 17, 18, 19, 20).

Предположу, что максимальное диагональное решение для C цветов имеет размер C^2xC^2.
Вот для C=3 9x9 представили, а 10х10 уже нет?
Для С=4 16х16 есть в статье.
Для С=5 25х25 и для C=6 36x36 есть у svb.
Для C=2 4x4 я представила.

А для C=7 49x49 у кого-нибудь есть диагональное решение?

Нет, выкладывать, конечно, не надо. Просто сообщите, что есть

Я искал именно с нормальным циклическим сдвигом - для 5-25 и 6-36 решения есть. Для 7-49 перебор очень большой, но решение может быть.

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

[Nataly-Mak]

А у вас есть какие-то оптимизации перебора? Ну, скажем, отсечение вариантов по каким-то критериям.
К тому же здесь ещё говорили о некоторой закономерности в первой строке - расстояния между одинаковыми цветами.
Вы всё это используете уже?

Вообще очень и очень интересный алгоритм. И работает он, видимо, для всех С.
Вот у нас уже есть для С=2,3,4,5,6. При этом решения по максимуму получаются C^2xC^2 (моё предположение).

Весьма заманчиво, однако