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

[Zealint]

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

Может кому будет интересно порешать вспомогательную задачу.

В квадрате NxN расставить максимальное количество 1, так чтобы не возникало запрещенных прямоугольников (все вершины которых помечены 1). Особо интересуют квадраты 5х5, 7х7, 9х9.
У меня получилось
Для 5х5 12 единиц
Для 7х7 21 единица
Для 9х9 29 единиц.
Не знаю являются ли эти результаты максимальными?

А вы разве не читали "The Solution of Ultra Large Grid Problems" по ссылкам? Там точно такие же результаты.

[Pavlovsky]

Zealint
Точно. Спасибо.

-- Пт июн 22, 2012 17:51:37 --

Чего то в программе Эда не работают кнопки "Rotate", "Mirror X", "Mirror Y"

[dimkadimon]

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

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

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

Забавно получилось. Мой намёк помог вам, но не помог мне. Увы я не такой догадливый. Значит всё таки решение для C=p^k+1 находится через решение C=p^k?

У меня получилось именно так.

(Оффтоп)

Строим прямоугольник С^2x(C^2+C) с использованием С цветов по алгоритму из теоремы 4.12. И достраиваем его с использованием C+1 цвета. Причем при достраивании не нужен перебор. Если внимательно посмотреть на исходный прямоугольник, то легко увидеть простой "регулярный" алгоритм достраивания.

Огромное вам спасибо - очень помогли. Теперь я вам должен. Я пробовал имено этот метод, но делал другое достраивание и поэтому не получалось.

[Pavlovsky]

Секретный алгоритм для С=2k с оценкой С^2, над которым неспешно работаю, никому не расскажу!

Хотя кое что уже сбалтнул. Не возмут меня в Штирлицы.

[Zealint]

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

Чего то в программе Эда не работают кнопки "Rotate", "Mirror X", "Mirror Y"

Надо сначала выделить нужный квадрат комбинацией CTRL+"клик мышкой", тогда к нему можно применить указанные кнопки

[Scryer]

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

Может кому будет интересно порешать вспомогательную задачу.

В квадрате NxN расставить максимальное количество 1, так чтобы не возникало запрещенных прямоугольников (все вершины которых помечены 1). Особо интересуют квадраты 5х5, 7х7, 9х9.
У меня получилось
Для 5х5 12 единиц
Для 7х7 21 единица
Для 9х9 29 единиц.
Не знаю являются ли эти результаты максимальными?

Я сделал 6х6 раньше, и, видимо, 16 единиц максимум.

-- 22.06.2012, 12:36 --

http://oeis.org/A072567

[whitefox]

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

Теперь смотрим на диагональные решения для C=5.
Здесь тоже используется сдвиг в строках, но он не совсем циклический, т. к. последее число не "зацикливается".

Например. в решении для C=5, N=17x17.
Первая строка:

01033143221100434

Как составляется эта строка
Вторая строка получается из первой сдвигом, но последнее число не 0, как должно быть в циклическом сдвиге, а 4:

10331432211004344

Почему здесь не циклический сдвиг, мне непонятно. Как определяется последнее число в строке при сдвиге, тоже непонятно.
И так я вижу во всех решениях для C=5.

Здесь циклически сдвигается строка из 33 элементов:

010331432211004344102034332211201

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

[Nataly-Mak]

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

Здесь циклически сдвигается строка из 33 элементов:

010331432211004344102034332211201

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

Спасибо, поняла со сдвигом.
Хотя не поняла, откуда берётся такая строка из 33 элементов. Но она, разумеется, полностью определяет квадрат 17х17.

Интересный алгоритм!

Скажите, правильно ли я поняла svb: диагональное решение существует и для C=6, N=36x36?
Алгоритм построения этого решения расскажете, когда закончится конкурс.

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

-- Сб июн 23, 2012 05:29:03 --

У меня для C=6 построен прямоугольник 31х36 6-coloring.

Строила я его по базовому алгоритму № 1 на основе набора из 31 непересекающихся комбинаций чисел 1,2,3,4,5,6 (где-то выкладывала этот набор; 30 первых комбинаций получил форумчанин с форума nazva.net по своей программе, а 31-ую комбинацию я нашла сама; в теме "Уникальные перестановки" это подробно описано).

Использовала два способа получения из прямоугольника 31х6 прямоугольника 31х36.

Первый способ
замена каждого элемента в прямоугольнике 31х6 таким образом:

1={1,2,3,4,5,6}
2={2,3,4,5,6,1}
3={3,4,5,6,1,2}
4={4,5,6,1,2,3}
5={5,6,1,2,3,4}
6={6,1,2,3,4,5}

Второй способ
замена выполняется по схеме:

1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> 6
6 -> 1

Покажу прямоугольник 31x36 6-coloring в обоих вариантах.





Пробовала достроить этот прямоугольник до квадрата 36х36 вручную в программе Эда. Увы, достраивается очень плохо
У кого есть программа достраивания, могут попробовать автоматическое достраивание.

[Nataly-Mak]

Здесь рассказали, как получить решение С=6, N=31x31 по другому алгоритму.
Уверена, что это решение отличается от решения, найденного мной.

И очень интересно, конечно, увидеть диагональное решение N=36x36. Оно очень красивое!
Надеюсь, что по окончании конкурса его покажут.
Кстати, наверное, существует и диагональное решение 31х31.
Если исходить из того, что для C=5 существует несколько диагональных решений; мне известны из статьи 17х17, 18х18, 19х19 и 20х20. Предположу, что есть и 21х21, ..., 25х25.

dimkadimon сообщал, что у него свой алгоритм построения решения N=36x36.
Наверное, у всех, кто нашёл это решение, какие-то свои алгоритмы. Всё это весьма интересно!

-- Сб июн 23, 2012 06:17:51 --

А это прямоугольник 21х36 6-coloring.
Сначала по базовому алгоритму № 2 построила прямоугольник 7х36 6-coloring.
Затем достраивала его вручную в программе Эда.



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

Здесь осталось достроить 15 строк. Думаю, что в этом примере 15 строк достроить проще, чем в примере с прямоугольником 31х36, приведённым выше, в котором надо достроить всего 5 строк.

Выше я привела решение 26х26 6-coloring, полученное ручным достраиванием решения 20х20, выложенного Alexu007. Тоже нерегулярное решение и очень хорошо достраивается, очень быстро расширила квадрат 20х20 до квадрата 26х26.

У меня есть ещё решение C=6, N=30x36, красивое. Получено по базовому алгоритму №1, достраивается плохо.

-- Сб июн 23, 2012 06:47:53 --

Вот этот прямоугольник 18x18, заполненный нулями и единичками, из статьи
http://www.cs.umd.edu/~gasarch/papers/gridtalk.pdf

не та же самая идея, показанная выше Pavlovsky?

[Nataly-Mak]

Покрутила квадрат 18х18 (почему я написала "прямоугольник", когда это квадрат? впрочем, квадрат - тоже прямоугольник, с равными сторонами), что-то у меня с ним ничего не получилось.

Как из этого квадрата получить решение 18х18 4-coloring?
Судя по подписи к рисунку, это сделать можно.

С квадратом, который привёл Pavlovsky, у меня сразу всё получилось.

[Alexu007]

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

Alexu007
знаете ли вы, что ваше решение C=6, N=20x20 неплохо достраивается в программе Эда?
Не пробовали? Оно у вас нерегулярное и потому легко достраивается.

У меня получилось расширить ваш квадрат 20х20 до квадрата 26х26:

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

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

[Pavlovsky]

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

Как из этого квадрата получить решение 18х18 4-coloring?Судя по подписи к рисунку, это сделать можно.

Из этого квадрата нельзя получить решение 18х18 4-coloring. Подпись к рисунку гласит. Если верна гипотеза RFC, тогда существует решение 18х18 4-coloring.

В статье сформулирована гипотеза.

Цитата:

Rectangle-Free Conjecture (RFC) is the converse:
Let n;m; c  2. If rfree(Gn;m)  dnm=ce then Gn;m is c-colorable.

Гипотеза (RFC) Если существует прямоугольник (n,m), состоящий из 0,1. Количество единиц в этом квадрате rfree(n,m)>=nm/C. Тогда существует С-раскрашиваемый прямоугольник (n,m).

Гипотеза предназанчена для определения нижней оценки существоания С-раскрашиваемого прямоугольника. Как ее использовать для построения квадратов непонятно.

[Nataly-Mak]

Alexu007
Так ведь алгоритм достраивания вроде очевиден

Например, есть у нас решение 31х36 6-coloring. В решении не хватает всего 5 строк.
Пристраеваем к прямоугольнику 32-ую строку и начинаем вписать в неё числа от 1 до 6 произвольным образом; при этом проверяем, не получаются ли прямоугольнички с одноцветными вершинами.
Если появляются такие прямоугольнички, пытаемся их исправить, при этом, естественно, залезаем с корректировкой внутрь исходного прямоугольника.

По-моему, именно так действует на достраивании программа Эда. Но в этой программе всё делается вручную.

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

Вот получила почти диагональное решение 21х21 6-coloring. Взяла диагональное решение 20х20 для C=5 и добавила в него цвет 6. Немного испортилась диагональность, но всё равно красиво.



Кстати, решение замечательно достраивается.
Это уже 26х26, получила ручным достраиванием решения 21х21:

26,26,A,B,A,E,B,B,C,D,D,F,F,E,C,C,D,A,D,C,B,D,B,E,E,E,C,F,B,A,E,B,B,C,D,D,E,A,A,C,C,D,A,D,C,B
,D,B,E,A,F,E,E,F,A,E,B,B,C,D,D,E,A,A,F,C,D,B,D,C,B,D,B,C,A,F,C,E,F,E,E,B,F,C,D,D,C,A,A,C,E,D,F,
D,C,B,D,B,E,A,E,E,A,B,F,A,B,B,C,D,C,E,A,A,C,F,D,A,D,C,B,D,B,E,A,E,E,D,F,F,F,E,B,C,D,D,E,A,A,C,
C,D,A,D,C,B,D,B,E,A,E,E,B,F,F,E,A,A,C,D,D,E,F,F,C,C,D,A,D,C,B,D,B,E,A,E,E,F,B,B,A,A,A,F,D,D,E,
A,A,C,C,D,A,D,C,B,D,F,E,A,E,E,F,F,F,E,B,B,B,C,D,C,A,A,C,C,D,F,D,C,B,D,B,E,A,E,E,B,B,F,E,D,E,A,
F,A,E,A,A,C,C,D,A,D,F,B,D,B,E,A,E,E,B,B,C,E,D,F,A,F,C,F,A,A,F,C,D,C,D,C,B,D,B,E,A,E,E,B,B,C,F,
A,C,F,B,D,A,E,A,C,C,A,F,D,C,B,D,B,E,A,E,E,B,B,C,E,D,C,F,A,F,D,B,D,C,C,D,A,D,F,B,D,F,E,A,E,E,B,
F,F,E,D,C,A,A,B,F,C,D,D,C,D,A,D,C,B,D,B,E,A,E,E,B,F,F,E,D,C,A,A,D,C,D,B,F,D,D,A,D,F,B,F,B,E,A,
E,E,B,B,C,E,B,C,A,A,D,C,F,C,A,E,B,A,F,C,B,D,B,E,A,E,E,B,F,C,E,D,C,A,A,D,E,C,B,D,F,B,C,D,C,B,D,
B,E,F,E,E,B,B,F,E,D,C,A,A,D,E,A,C,A,E,B,F,F,C,B,D,C,E,A,E,E,B,F,C,E,D,C,A,F,D,E,A,C,A,F,A,D,B,B
,B,D,B,E,A,E,E,B,B,C,E,D,C,A,A,D,E,A,C,A,F,C,C,D,D,F,F,B,E,A,E,E,B,B,C,E,D,F,A,A,F,E,A,C,A,B,F,
F,D,C,D,C,B,E,F,E,E,F,B,C,E,D,C,F,A,D,E,A,C,A,B,D,A,D,B,C,C,D,D,A,E,B,F,C,F,B,F,F,E,A,F,C,D,C,
A,F,F,E,A,C,B,C,D,A,F,F,F,F,E,A,F,A,C,A,F,D,E,A,C,A,B,D,C,F,D,B,F,B,E,E,E,E,B,F,F,E,A,F,A,D,D,F,
A,E,C,F,D,D,D,B,B,A,C,C,E,B,C,E,A,D,A,B,E,A,C,C,F,F,E,B,B,C,C,B,F,D,A,E,B,D,A,B,D,E,E,A,D,F,B,
F,B,B,F,E,F,F,C,D,F,A,E,C,B,C,A,F,C,C

Здесь уже диагональность сильнее испорчена.

[Pavlovsky]

В Статье "The Solution of Ultra Large Grid Problems" есть таблица (TABLE IV) где представлены максимальное количество единиц для квадратов с размерами от 2 до 10. Например для квадрата 10х10 максимум 34 единиц. Тогда согласно гипотезе квадрат 10х10 можно раскрасить в [10*10/34]=3 цвета.

[Nataly-Mak]

Поиграла с прямоугольником 36х31 6-coloring

Сегодня повезло, с ходу удалось достроить до прямоугольника 36х32. А раньше пыталась достраивать, ничего не получилось, никак не удавалось "убить" все ошибки.

Итак, есть решение C=6, N=32x32!
Невзначай получилось
Вполне может быть, что решение достраивается до 36х36. Осталось всего 4 строки в готовом прямоугольнике 32х36.

Решение С=6, N=36х36 почти есть.
Из "джентельменского" набора у меня не реализован только алгоритм C=p^k+1, p - простое, k>=1.

Но решения для С=10,12,14,18,20 у меня введены, и они довольно неплохие. Так что реализация этого алгоритма мне может дать максимум 1 балл.

-- Сб июн 23, 2012 11:30:52 --

Ур-р-р-а-а-а!
И решение 33х33 получить удалось.
Что ж, по-моему, неплохое начало таблицы результатов:

2 4 16 1.000000 05-30-2012 @ 07:37:46
3 10 100 1.000000 05-30-2012 @ 15:39:17
4 18 324 1.000000 05-30-2012 @ 15:21:28
5 25 625 1.000000 06-01-2012 @ 05:26:42
6 33 1089 0.840278 06-23-2012 @ 11:25:05
7 49 2401 1.000000 06-01-2012 @ 07:30:35
8 64 4096 1.000000 06-06-2012 @ 21:21:02
9 81 6561 1.000000 06-07-2012 @ 06:52:04

До полной идиллии не хватает всего 0,16 балла

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