2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1 ... 28, 29, 30, 31, 32, 33, 34 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 10:42 
Аватара пользователя
И 34х34 есть!!

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

И 35х35 есть!

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 10:55 
Аватара пользователя
whitefox в сообщении #588081 писал(а):
Расстояния между одинаковыми цифрам подчиняются определённым закономерностям. Например, если есть одноцветный прямоугольник, то обязательно имеется пара одинаковых расстояний между номерами этого цвета, обратное не верно.


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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:05 
Аватара пользователя
Всё! Последний рубеж пройден, решение C=6, N=36x36 получено!

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

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

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

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:23 
Аватара пользователя
whitefox в сообщении #588081 писал(а):
Расстояния между одинаковыми цифрам подчиняются определённым закономерностям. Например, если есть одноцветный прямоугольник, то обязательно имеется пара одинаковых расстояний между номерами этого цвета, обратное не верно.

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

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

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

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

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


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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:34 
Аватара пользователя
Pavlovsky в сообщении #588131 писал(а):
Сергей почему не учавствуете в конкурсе? Зачем отличные решения складывать под подушку?
Пока особых успехов нет. С грехом пополам только что разобрался с GF(16), т.е. вышел на результат 13. Пора переходить к составным C - для C=6 просто перебор был быстрым. Картинки, правда, удалось получить красивыми даже для всех простых C, что и завораживает. Это не чистые диагонали, но явно просматривается диагональная структура.

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:43 
Аватара пользователя
Мне удалось достраиванием только что полученного решения 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 баллов? :D

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 11:56 
Аватара пользователя
Цитата:
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


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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 12:04 
Аватара пользователя
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 писал(а):
Дамский набор решений тоже радует. :D

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 12:13 
Аватара пользователя
Nataly-Mak в сообщении #588132 писал(а):
Не исключено, что существует и диагональное решение 100x100 для C=10.


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

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 12:21 
Аватара пользователя
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:

Изображение

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 13:42 
Аватара пользователя
И почти диагональное решение 23х23 8-цветное:

Изображение

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

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

А для С=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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 14:41 
Аватара пользователя
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,

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 14:46 
Аватара пользователя
О!
Спасибо! Очень красиво.
Сейчас перепишу в числах, проанализирую. Мне почему-то с символами совсем не нравится работать, я привыкла работать с числами.

А 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 у кого-нибудь есть диагональное решение?

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

 
 
 
 Re: Новый конкурс программистов
Сообщение23.06.2012, 16:04 
Аватара пользователя
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 у кого-нибудь есть диагональное решение?

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

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

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

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

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

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 28, 29, 30, 31, 32, 33, 34 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group