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

[dimkadimon]

Nataly-Mak я бегло посмотрел вашу книгу. Интересная книга, жалко что ее не читают. Вы хотели коментарии. Вот они, только не обижайтесь:

* Я не заметил никакой информации про Bill Gasarch. Ведь ето он придумал задачу и дал деньги за решение C4N17.
* У Tom Sirgedas есть новые результаты про заполнение единичками.
* Напишите про мой метод. Я заполняю каждое 1xC одной единичкой чтобы не было запрещеных прямоугольников, а потом создаю полное решение сдвигом на лево. Вот пример для C5N25: http://paste2.org/p/2183533
* Напишите про метод alexBlack для C=15 и 21
* Напишите про создание решений для C=10, 12, 14, 18 и 20
* Добавьте ссылки на все статьи
* Хорошо бы описать связь с Bipartite Numbers
* Еще можно добавить описание быстрых методов для проверки правильности решений. Например можно использовать битовую арифметику для низких C, я об етом писал в начале темы. Еще когда мы делаем много маленьких изменений в решение то не надо каждый раз все заново проверять. Об етом тоже раньше писал.
* Можно привести таблицу лучших результатов и таблицу с участниками
* Вы наверное сохранили картинки как jpg? Они не резкие потому что етот формат сжимает данные и при етом теряет качество. Лучше использовать png, правда тогда файл будет очень большой. Еще лучше написать все в LaTex, но на ето нужно много времени

[Nataly-Mak]

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

Nataly-Mak я бегло посмотрел вашу книгу. Интересная книга, жалко что ее не читают. Вы хотели коментарии. Вот они, только не обижайтесь:

* Напишите про метод alexBlack для C=15 и 21
* Напишите про создание решений для C=10, 12, 14, 18 и 20
* Добавьте ссылки на все статьи

Вот на этих замечаниях остановлюсь.
О методе alexBlack для C=15,21 писать не буду по той простой причине, что я этот метод не разбирала. К тому же, это слишком авторский метод, метод, который автор сам описал в своей статье. Зачем это дублировать? Я даю ссылку на эту статью.

О создании решений для С=10,12,14,18 и 20 буду писать. Книга-то ещё не закончена, вы видите только первые 4 главы.

Все ссылки будут добавлены в конце книги, разумеется.

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

Спасибо за замечания. Никаких обид

[dimkadimon]

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

О методе alexBlack для C=15,21 писать не буду по той простой причине, что я этот метод не разбирала. К тому же, это слишком авторский метод, метод, который автор сам описал в своей статье. Зачем это дублировать?

О вашем методе тоже писать не буду по той же самой причине: я его не знаю.

Хорошо. Тогда дайте ссылки на ети методы, чтобы читатель смог их найти.

[Nataly-Mak]

На статью alexBlack я ссылку даю.
Давайте ссылку на вашу статью, её тоже укажу.

[dimkadimon]

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

На статью alexBlack я ссылку даю.
Давайте ссылку на вашу статью, её тоже укажу.

У меня только на английском есть:

I came up with a variation of the method used by Bernd Steinbach and Christian Posthoff. The idea is to tile the grid into 1xC tiles row by row. We then need to assign a single 1 to each of the tiles such that there are no forbidden rectangles. When we shift all the 1s one cell to the right (mod C) we get the coloring for the second color. Shifting again we get the remaining colors. Every color is guaranteed to occupy uniques cells and every color is guaranteed to be rectangle-free provided that the first color (1s) is rectangle free. Here is an example of such a 25x25 coloring for the first color and the corresponding full coloring: http://paste2.org/p/2183533

P.S. Я наконец нашел C21N401! Сколько ето мне стоило...

[Pavlovsky]

(Оффтоп)

№1
0,1,2,3,4,5,1,0,3,2,5,4,2,3,5,4,1,0,3,2,4,5,0,1,4,5,1,0,2,3,5,4,0,1,3,2
2,3,4,5,3,2,5,4,4,5,2,6,5,4,6,2

1,1,1,1,1,1,2,2,2,2,2,1,3,3,3,3,3,1,4,4,4,4,4,1,5,5,5,5,5,1,6,6,6,6,6,1,1,2,3,4,5,2,2,1,4,3,6,2,3,4,6,5,2,2,4,3,5,6,1,2,5,6,2,1,3,2,6,5,1,2,4,2,1,3,2,5,4,3,2,4,1,6,3,3,3,6,4,2,5,3,4,5,3,1,6,3,5,2,6,3,
1,3,6,1,5,4,2,3,1,4,5,2,6,4,2,3,6,1,5,4,3,5,2,4,1,4,4,6,1,3,2,4,5,1,3,6,4,4,6,2,4,5,3,4,1,5,4,6,2,5,2,6,3,5,1,5,3,2,5,1,4,5,4,1,6,2,3,5,5,3,1,4,6,5,6,4,2,3,5,5

1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,2,2,2,2,2,1,3,3,3,3,3,2,4,4,4,4,4,3,5,5,5,5,5,4,6,6,6,6,6,5,1,1,1,1,1,6,3,3,3,3,3,1,4,4,4,4,4,2,5,5,5,5,5,3,6,6,6,6,6,4,1,1,1,1,
1,5,2,2,2,2,2,6,4,4,4,4,4,1,5,5,5,5,5,2,6,6,6,6,6,3,1,1,1,1,1,4,2,2,2,2,2,5,3,3,3,3,3,6,5,5,5,5,5,1,6,6,6,6,6,2,1,1,1,1,1,3,2,2,2,2,2,4,3,3,3,3,3,5,4,4,4,4,4,6,6,6,6,6,6,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,
3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,1,2,3,4,5,2,2,3,4,5,6,3,3,4,5,6,1,4,4,5,6,1,2,5,5,6,1,2,3,6,6,1,2,3,4,1,2,1,4,3,6,2,3,2,5,4,1,3,4,3,6,5,2,4,5,4,1,6,3,5,6,5,2,1,4,6,1,6,3,2,5,1,3,4,6,5,2,2,4,5,1,6,3,3,
5,6,2,1,4,4,6,1,3,2,5,5,1,2,4,3,6,6,2,3,5,4,1,1,4,3,5,6,1,2,5,4,6,1,2,3,6,5,1,2,3,4,1,6,2,3,4,5,2,1,3,4,5,6,3,2,4,5,6,1,5,6,2,1,3,2,6,1,3,2,4,3,1,2,4,3,5,4,2,3,5,4,6,5,3,4,6,5,1,6,4,5,1,6,2,1,6,5,1,2,
4,2,1,6,2,3,5,3,2,1,3,4,6,4,3,2,4,5,1,5,4,3,5,6,2,6,5,4,6,1,3,1,1,3,2,5,4,3,2,4,3,6,5,4,3,5,4,1,6,5,4,6,5,2,1,6,5,1,6,3,2,1,6,2,1,4,3,2,2,4,1,6,3,3,3,5,2,1,4,4,4,6,3,2,5,5,5,1,4,3,6,6,6,2,5,4,1,1,1,3,
6,5,2,2,3,6,4,2,5,3,4,1,5,3,6,4,5,2,6,4,1,5,6,3,1,5,2,6,1,4,2,6,3,1,2,5,3,1,4,2,4,5,3,1,6,3,5,6,4,2,1,4,6,1,5,3,2,5,1,2,6,4,3,6,2,3,1,5,4,1,3,4,2,6,5,2,5,2,6,3,1,3,6,3,1,4,2,4,1,4,2,5,3,5,2,5,3,6,4,6,
3,6,4,1,5,1,4,1,5,2,6,2,6,1,5,4,2,3,1,2,6,5,3,4,2,3,1,6,4,5,3,4,2,1,5,6,4,5,3,2,6,1,5,6,4,3,1,2,1,4,5,2,6,4,2,5,6,3,1,5,3,6,1,4,2,6,4,1,2,5,3,1,5,2,3,6,4,2,6,3,4,1,5,3,2,3,6,1,5,4,3,4,1,2,6,5,4,5,2,3,
1,6,5,6,3,4,2,1,6,1,4,5,3,2,1,2,5,6,4,3,3,5,2,4,1,4,4,6,3,5,2,5,5,1,4,6,3,6,6,2,5,1,4,1,1,3,6,2,5,2,2,4,1,3,6,3,4,6,1,3,2,4,5,1,2,4,3,5,6,2,3,5,4,6,1,3,4,6,5,1,2,4,5,1,6,2,3,5,6,2,1,3,5,1,3,6,4,4,6,2,
4,1,5,5,1,3,5,2,6,6,2,4,6,3,1,1,3,5,1,4,2,2,4,6,2,5,3,3,6,2,4,5,3,4,1,3,5,6,4,5,2,4,6,1,5,6,3,5,1,2,6,1,4,6,2,3,1,2,5,1,3,4,2,3,1,5,4,6,2,5,2,6,5,1,3,6,3,1,6,2,4,1,4,2,1,3,5,2,5,3,2,4,6,3,6,4,3,5,1,4,
2,6,3,5,1,5,3,1,4,6,2,6,4,2,5,1,3,1,5,3,6,2,4,2,6,4,1,3,5,3,1,5,2,4,6,4,3,2,5,1,4,5,4,3,6,2,5,6,5,4,1,3,6,1,6,5,2,4,1,2,1,6,3,5,2,3,2,1,4,6,3,4,4,1,6,2,3,5,5,2,1,3,4,6,6,3,2,4,5,1,1,4,3,5,6,2,2,5,4,6,
1,3,3,6,5,1,2,4,5,3,1,4,6,5,6,4,2,5,1,6,1,5,3,6,2,1,2,6,4,1,3,2,3,1,5,2,4,3,4,2,6,3,5,4,6,4,2,3,5,5,1,5,3,4,6,6,2,6,4,5,1,1,3,1,5,6,2,2,4,2,6,1,3,3,5,3,1,2,4,4,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,
5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,4,3,2,1,6,5,4,3,2,1,6,5,
4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1

№2
0,1,2,3,4,5,1,5,0,4,3,2,2,4,5,0,1,3,3,0,4,5,2,1,4,3,1,2,5,0,5,2,3,1,0,4
2,3,4,5,3,2,6,4,4,6,2,3,6,4,3,2

1,1,1,1,1,1,2,2,2,2,2,1,3,3,3,3,3,1,4,4,4,4,4,1,5,5,5,5,5,1,6,6,6,6,6,1,1,2,3,4,5,2,2,6,1,5,4,2,3,5,6,1,2,2,4,1,5,6,3,2,5,4,2,3,6,2,6,3,4,2,1,2,1,3,2,6,4,3,2,1,6,3,5,3,3,6,5,4,1,3,4,5,1,2,6,3,5,2,4,1,
3,3,6,4,3,5,2,3,1,4,6,2,3,4,2,5,3,6,1,4,3,1,4,5,6,4,4,6,2,1,5,4,5,3,1,4,2,4,6,2,5,3,4,4,1,6,4,3,2,5,2,3,5,1,6,5,3,4,1,6,5,5,4,2,6,5,1,5,5,1,3,2,4,5,6,5,2,4,3,5

1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,2,2,2,2,2,1,3,3,3,3,3,2,4,4,4,4,4,3,5,5,5,5,5,4,6,6,6,6,6,5,1,1,1,1,1,6,3,3,3,3,3,1,4,4,4,4,4,2,5,5,5,5,5,3,6,6,6,6,6,4,1,1,1,1,
1,5,2,2,2,2,2,6,4,4,4,4,4,1,5,5,5,5,5,2,6,6,6,6,6,3,1,1,1,1,1,4,2,2,2,2,2,5,3,3,3,3,3,6,5,5,5,5,5,1,6,6,6,6,6,2,1,1,1,1,1,3,2,2,2,2,2,4,3,3,3,3,3,5,4,4,4,4,4,6,6,6,6,6,6,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,
3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,1,2,3,4,5,2,2,3,4,5,6,3,3,4,5,6,1,4,4,5,6,1,2,5,5,6,1,2,3,6,6,1,2,3,4,1,2,6,1,5,4,2,3,1,2,6,5,3,4,2,3,1,6,4,5,3,4,2,1,5,6,4,5,3,2,6,1,5,6,4,3,1,3,5,6,1,2,2,4,6,1,2,3,3,
5,1,2,3,4,4,6,2,3,4,5,5,1,3,4,5,6,6,2,4,5,6,1,1,4,1,5,6,3,2,5,2,6,1,4,3,6,3,1,2,5,4,1,4,2,3,6,5,2,5,3,4,1,6,3,6,4,5,2,1,5,4,2,3,6,2,6,5,3,4,1,3,1,6,4,5,2,4,2,1,5,6,3,5,3,2,6,1,4,6,4,3,1,2,5,1,6,3,4,2,
1,2,1,4,5,3,2,3,2,5,6,4,3,4,3,6,1,5,4,5,4,1,2,6,5,6,5,2,3,1,6,1,1,3,2,6,4,3,2,4,3,1,5,4,3,5,4,2,6,5,4,6,5,3,1,6,5,1,6,4,2,1,6,2,1,5,3,2,2,1,6,3,5,3,3,2,1,4,6,4,4,3,2,5,1,5,5,4,3,6,2,6,6,5,4,1,3,1,1,6,
5,2,4,2,3,6,5,4,1,3,4,1,6,5,2,4,5,2,1,6,3,5,6,3,2,1,4,6,1,4,3,2,5,1,2,5,4,3,6,2,4,5,1,2,6,3,5,6,2,3,1,4,6,1,3,4,2,5,1,2,4,5,3,6,2,3,5,6,4,1,3,4,6,1,5,2,5,2,4,1,3,3,6,3,5,2,4,4,1,4,6,3,5,5,2,5,1,4,6,6,
3,6,2,5,1,1,4,1,3,6,2,2,6,4,3,5,2,3,1,5,4,6,3,4,2,6,5,1,4,5,3,1,6,2,5,6,4,2,1,3,6,1,5,3,2,4,1,2,1,4,6,2,3,4,2,5,1,3,4,5,3,6,2,4,5,6,4,1,3,5,6,1,5,2,4,6,1,2,6,3,5,1,2,3,2,5,3,6,1,4,3,6,4,1,2,5,4,1,5,2,
3,6,5,2,6,3,4,1,6,3,1,4,5,2,1,4,2,5,6,3,3,1,4,5,6,4,4,2,5,6,1,5,5,3,6,1,2,6,6,4,1,2,3,1,1,5,2,3,4,2,2,6,3,4,5,3,4,6,2,1,5,4,5,1,3,2,6,5,6,2,4,3,1,6,1,3,5,4,2,1,2,4,6,5,3,2,3,5,1,6,4,3,5,3,1,4,2,4,6,4,
2,5,3,5,1,5,3,6,4,6,2,6,4,1,5,1,3,1,5,2,6,2,4,2,6,3,1,3,6,2,5,3,4,4,1,3,6,4,5,5,2,4,1,5,6,6,3,5,2,6,1,1,4,6,3,1,2,2,5,1,4,2,3,3,1,6,4,3,2,5,2,1,5,4,3,6,3,2,6,5,4,1,4,3,1,6,5,2,5,4,2,1,6,3,6,5,3,2,1,4,
2,3,5,1,6,5,3,4,6,2,1,6,4,5,1,3,2,1,5,6,2,4,3,2,6,1,3,5,4,3,1,2,4,6,5,4,3,4,1,6,5,5,4,5,2,1,6,6,5,6,3,2,1,1,6,1,4,3,2,2,1,2,5,4,3,3,2,3,6,5,4,4,4,2,6,5,1,5,5,3,1,6,2,6,6,4,2,1,3,1,1,5,3,2,4,2,2,6,4,3,
5,3,3,1,5,4,6,4,5,1,3,2,4,5,6,2,4,3,5,6,1,3,5,4,6,1,2,4,6,5,1,2,3,5,1,6,2,3,4,6,2,1,3,4,6,5,2,4,3,5,1,6,3,5,4,6,2,1,4,6,5,1,3,2,5,1,6,2,4,3,6,2,1,3,5,4,1,3,2,4,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,
5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,4,3,2,1,6,5,4,3,2,1,6,5,
4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1

№3
0,1,2,3,4,5,1,5,3,0,2,4,2,4,5,1,3,0,3,2,4,5,0,1,4,0,1,2,5,3,5,3,0,4,1,2
2,3,4,5,3,2,5,4,4,5,2,3,5,4,3,2

1,1,1,1,1,1,2,2,2,2,2,1,3,3,3,3,3,1,4,4,4,4,4,1,5,5,5,5,5,1,6,6,6,6,6,1,1,2,3,4,5,2,2,6,4,1,3,2,3,5,6,2,4,2,4,3,5,6,1,2,5,1,2,3,6,2,6,4,1,5,2,2,1,3,2,5,4,3,2,4,6,3,1,3,3,6,5,4,2,3,4,5,3,1,6,3,5,2,1,6,
3,3,6,1,4,2,5,3,1,4,5,2,3,4,2,1,3,6,4,4,3,2,4,5,6,4,4,6,1,3,5,4,5,3,6,1,2,4,6,5,2,4,1,4,1,5,4,3,2,5,2,3,1,4,6,5,3,4,2,6,5,5,4,1,6,5,3,5,5,6,3,2,1,5,6,2,5,1,4,5

1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,2,2,2,2,2,1,3,3,3,3,3,2,4,4,4,4,4,3,5,5,5,5,5,4,6,6,6,6,6,5,1,1,1,1,1,6,3,3,3,3,3,1,4,4,4,4,4,2,5,5,5,5,5,3,6,6,6,6,6,4,1,1,1,1,
1,5,2,2,2,2,2,6,4,4,4,4,4,1,5,5,5,5,5,2,6,6,6,6,6,3,1,1,1,1,1,4,2,2,2,2,2,5,3,3,3,3,3,6,5,5,5,5,5,1,6,6,6,6,6,2,1,1,1,1,1,3,2,2,2,2,2,4,3,3,3,3,3,5,4,4,4,4,4,6,6,6,6,6,6,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,
3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,1,2,3,4,5,2,2,3,4,5,6,3,3,4,5,6,1,4,4,5,6,1,2,5,5,6,1,2,3,6,6,1,2,3,4,1,2,6,4,1,3,2,3,1,5,2,4,3,4,2,6,3,5,4,5,3,1,4,6,5,6,4,2,5,1,6,1,5,3,6,2,1,3,5,6,2,4,2,4,6,1,3,5,3,
5,1,2,4,6,4,6,2,3,5,1,5,1,3,4,6,2,6,2,4,5,1,3,1,4,3,5,6,1,2,5,4,6,1,2,3,6,5,1,2,3,4,1,6,2,3,4,5,2,1,3,4,5,6,3,2,4,5,6,1,5,1,2,3,6,2,6,2,3,4,1,3,1,3,4,5,2,4,2,4,5,6,3,5,3,5,6,1,4,6,4,6,1,2,5,1,6,4,1,5,
2,2,1,5,2,6,3,3,2,6,3,1,4,4,3,1,4,2,5,5,4,2,5,3,6,6,5,3,6,4,1,1,1,3,2,5,4,3,2,4,3,6,5,4,3,5,4,1,6,5,4,6,5,2,1,6,5,1,6,3,2,1,6,2,1,4,3,2,2,4,6,3,1,3,3,5,1,4,2,4,4,6,2,5,3,5,5,1,3,6,4,6,6,2,4,1,5,1,1,3,
5,2,6,2,3,6,5,4,2,3,4,1,6,5,3,4,5,2,1,6,4,5,6,3,2,1,5,6,1,4,3,2,6,1,2,5,4,3,1,2,4,5,3,1,6,3,5,6,4,2,1,4,6,1,5,3,2,5,1,2,6,4,3,6,2,3,1,5,4,1,3,4,2,6,5,2,5,2,1,6,3,3,6,3,2,1,4,4,1,4,3,2,5,5,2,5,4,3,6,6,
3,6,5,4,1,1,4,1,6,5,2,2,6,1,4,2,5,3,1,2,5,3,6,4,2,3,6,4,1,5,3,4,1,5,2,6,4,5,2,6,3,1,5,6,3,1,4,2,1,4,5,2,3,4,2,5,6,3,4,5,3,6,1,4,5,6,4,1,2,5,6,1,5,2,3,6,1,2,6,3,4,1,2,3,2,1,3,6,4,4,3,2,4,1,5,5,4,3,5,2,
6,6,5,4,6,3,1,1,6,5,1,4,2,2,1,6,2,5,3,3,3,2,4,5,6,4,4,3,5,6,1,5,5,4,6,1,2,6,6,5,1,2,3,1,1,6,2,3,4,2,2,1,3,4,5,3,4,6,1,3,5,4,5,1,2,4,6,5,6,2,3,5,1,6,1,3,4,6,2,1,2,4,5,1,3,2,3,5,6,2,4,3,5,3,6,1,2,4,6,4,
1,2,3,5,1,5,2,3,4,6,2,6,3,4,5,1,3,1,4,5,6,2,4,2,5,6,1,3,6,5,2,4,1,4,1,6,3,5,2,5,2,1,4,6,3,6,3,2,5,1,4,1,4,3,6,2,5,2,5,4,1,3,6,3,1,5,4,3,2,5,2,6,5,4,3,6,3,1,6,5,4,1,4,2,1,6,5,2,5,3,2,1,6,3,6,4,3,2,1,4,
2,3,1,4,6,5,3,4,2,5,1,6,4,5,3,6,2,1,5,6,4,1,3,2,6,1,5,2,4,3,1,2,6,3,5,4,3,4,2,6,5,5,4,5,3,1,6,6,5,6,4,2,1,1,6,1,5,3,2,2,1,2,6,4,3,3,2,3,1,5,4,4,4,1,6,5,3,5,5,2,1,6,4,6,6,3,2,1,5,1,1,4,3,2,6,2,2,5,4,3,
1,3,3,6,5,4,2,4,5,6,3,2,1,5,6,1,4,3,2,6,1,2,5,4,3,1,2,3,6,5,4,2,3,4,1,6,5,3,4,5,2,1,6,4,6,2,5,1,4,5,1,3,6,2,5,6,2,4,1,3,6,1,3,5,2,4,1,2,4,6,3,5,2,3,5,1,4,6,3,4,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,
5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,4,3,2,1,6,5,4,3,2,1,6,5,
4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1

Три решения для С=6
Первая строка - исходный ЛК
Вторая строка - Матрица без первой колонки и строки
Третья строка - сильноокрашенный прямоугольник
Четвертая строка - результирующий квадрат.

[Nataly-Mak]

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

У меня только на английском есть:

Хорошо, пусть на английском. Только вы оформите всё это в виде статьи и выложите её где-нибудь, а мне дайте ссылку на эту статью.
В этой статье можете описать и другие свои методы.

Цитата:

P.S. Я наконец нашел C21N401! Сколько ето мне стоило...

Здорово! Поздравляю!
Вашему упорству можно позавидовать.

[dimkadimon]

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

Хорошо, пусть на английском. Только вы оформите всё это в виде статьи и выложите её где-нибудь, а мне дайте ссылку на эту статью.
В этой статье можете описать и другие свои методы.

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

-- 28.09.2012, 20:41 --

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

Три решения для С=6
Первая строка - исходный ЛК
Вторая строка - Матрица без первой колонки и строки
Третья строка - сильноокрашенный прямоугольник
Четвертая строка - результирующий квадрат.

А ети все решения разные? Или они изоморфны?

[Pavlovsky]

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

А может Вы имели ввиду моё предложение:
А именно будем заполнять базовую матрицу не числами, а перестановками.

Пусть

A B
C D

некоторый прямоугольник в базовой матрице, где A B C D перестановки.

Прямоугольник будет "разрешённым" если перестановка $\mathrm{M}=\mathrm{A}\mathrm{B^{-1}}\mathrm{D}\mathrm{C^{-1}}$ является беспорядочной, то есть не оставляет на месте ни одно число.

Тезисно опишу чего сейчас делаю.
1) Ваша идея использовать матричные операции очень интересная. Нечто подобное видел в различных статьях. Но пока серьезно разобраться во всем этом руки не дошли.
2) Все так называемые "алгебраические" алгоритмы эквиваленты. Естественно подробного доказательства этого утверждения у меня нет. Но кое что я в свох последних постах описал.
3) Мой псоледний основной алгоритм выглядит так. Строим сильноокрашенный прямоугольник CKxM. Выбираем исходный ЛК CxC в качестве набора перестановок (каждая колонка - перестановка). Заполняем (перебором) матрицу KxM номерами перестановок, так чтобы у нас не было полупрямоугольников. Первые строку и колонку матрицы заполняем номером 1.
4) Свои результаты для С=6,7,8 я приводил. Для С>8 у меня нет наборов неизоморфных ЛК, да и их слишком много.
5) Планирую заполнять матрицу двумя наборами перестановок, сведенными в два исходных ЛК. Кое какие свойства этой пары исходных ЛК уже установил. К тому же существует явная связь с разностными множествами.
6) Правда, пока эту тему отложил, перекинулся на теорему Зингера.
7) Изучаю книгу Холла "Комбинаторика". Есть много вкусного.

-- Пт сен 28, 2012 17:16:54 --

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

А ети все решения разные? Или они изоморфны?

Все исходные ЛК неизоморфны (неизотопны). Вроде как и решения должны быть разными. Пока у нас нет перечня преобразований для решений конкурса, относительно которых мы будем считать решения разными. Относительно перестановки строк, столбцов и символов эти решени различны!

-- Пт сен 28, 2012 17:24:19 --

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

2 3 4 5    2 3 4 5
3 2 5 4    3 2 5 4
4 5 2 6    4 5 2 3
5 4 6 2    5 4 3 2

2 5
5 2

2-5+2-5=0 (mod 6)

2 3 4 5 
3 2 6 4 
4 6 2 3 
6 4 3 2

3 5
2 4

3-5+4-2=0 (mod 6)

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

-- Пт сен 28, 2012 17:31:50 --

Теорема Зингера.
http://svb.hut.ru/ALG/mono.htm
Сергей Беляев в свой статье утверждает.

Цитата:

На разностные множества обратил внимание один из участников конкурса, Herbert Kociemba

И приводит формулу (k^2+k+1,k+1,1), где первое число сторона квадрата, второе число количество цветов, третье, в нашем случае всегда 1.

Для k=9 получается не интересно (91,10,1). То есть существует решение C10N91.

А если подставить k=14?? Получается С15N211!!!

[dimkadimon]

Формула (к^2+к+1, к+1, 1) работает только если k=р^m, где p простое. Поэтому k=14 нельзя иметь.

[Pavlovsky]

А если попробовать? У Холла есть такие понятия "почти поле", "полу-поле".

[Nataly-Mak]

Цитата:

№1
0,1,2,3,4,5,1,0,3,2,5,4,2,3,5,4,1,0,3,2,4,5,0,1,4,5,1,0,2,3,5,4,0,1,3,2
2,3,4,5,3,2,5,4,4,5,2,6,5,4,6,2

whitefox
можно я приведу своё понимание первого примера Pavlovsky (см. цитату)?
Сама еле-еле разобралась Когда разобралась, всё оказалось очень просто. Тот же самый матричный метод, который завёрнут в "матрицу перестановок, сильноокрашенный прямоугольник". Те же самые штанишки, только пуговки назад
Итак:
исходный латинский квадрат 6-го порядка:

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

Блок №k строится от k-ого столбца исходного ЛК, а дальше +1 по модулю 6 (что равносильно репликации сильноокрашенного прямоугольника). Показываю все 6 блоков:

(Оффтоп)

№1
1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5

№2
2 3 4 5 6 1
1 2 3 4 5 6
4 5 6 1 2 3
3 4 5 6 1 2
6 1 2 3 4 5
5 6 1 2 3 4

№3
3 4 5 6 1 2
4 5 6 1 2 3
6 1 2 3 4 5
5 6 1 2 3 4
2 3 4 5 6 1
1 2 3 4 5 6

№4
4 5 6 1 2 3
3 4 5 6 1 2
5 6 1 2 3 4
6 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 1

№5
5 6 1 2 3 4
6 1 2 3 4 5
2 3 4 5 6 1
1 2 3 4 5 6
3 4 5 6 1 2
4 5 6 1 2 3

№6
6 1 2 3 4 5
5 6 1 2 3 4
1 2 3 4 5 6
2 3 4 5 6 1
4 5 6 1 2 3
3 4 5 6 1 2

Базовая матрица:

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

Как и положено в матричном методе, заполняем эту базовую матрицу приведёнными блоками в соответствии с их номерами и получаем решение 30х30 6-coloring:

(Оффтоп)

30,30,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,
2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,
3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,
4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,
5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,
6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,
1,2,3,4,5,6,2,3,4,5,6,1,3,4,5,6,1,2,4,5,6,1,2,3,5,6,1,2,3,4,
2,3,4,5,6,1,1,2,3,4,5,6,4,5,6,1,2,3,3,4,5,6,1,2,6,1,2,3,4,5,
3,4,5,6,1,2,4,5,6,1,2,3,6,1,2,3,4,5,5,6,1,2,3,4,2,3,4,5,6,1,
4,5,6,1,2,3,3,4,5,6,1,2,5,6,1,2,3,4,6,1,2,3,4,5,1,2,3,4,5,6,
5,6,1,2,3,4,6,1,2,3,4,5,2,3,4,5,6,1,1,2,3,4,5,6,3,4,5,6,1,2,
6,1,2,3,4,5,5,6,1,2,3,4,1,2,3,4,5,6,2,3,4,5,6,1,4,5,6,1,2,3,
1,2,3,4,5,6,3,4,5,6,1,2,2,3,4,5,6,1,5,6,1,2,3,4,4,5,6,1,2,3,
2,3,4,5,6,1,4,5,6,1,2,3,1,2,3,4,5,6,6,1,2,3,4,5,3,4,5,6,1,2,
3,4,5,6,1,2,6,1,2,3,4,5,4,5,6,1,2,3,2,3,4,5,6,1,5,6,1,2,3,4,
4,5,6,1,2,3,5,6,1,2,3,4,3,4,5,6,1,2,1,2,3,4,5,6,6,1,2,3,4,5,
5,6,1,2,3,4,2,3,4,5,6,1,6,1,2,3,4,5,3,4,5,6,1,2,1,2,3,4,5,6,
6,1,2,3,4,5,1,2,3,4,5,6,5,6,1,2,3,4,4,5,6,1,2,3,2,3,4,5,6,1,
1,2,3,4,5,6,4,5,6,1,2,3,5,6,1,2,3,4,2,3,4,5,6,1,6,1,2,3,4,5,
2,3,4,5,6,1,3,4,5,6,1,2,6,1,2,3,4,5,1,2,3,4,5,6,5,6,1,2,3,4,
3,4,5,6,1,2,5,6,1,2,3,4,2,3,4,5,6,1,4,5,6,1,2,3,1,2,3,4,5,6,
4,5,6,1,2,3,6,1,2,3,4,5,1,2,3,4,5,6,3,4,5,6,1,2,2,3,4,5,6,1,
5,6,1,2,3,4,1,2,3,4,5,6,3,4,5,6,1,2,6,1,2,3,4,5,4,5,6,1,2,3,
6,1,2,3,4,5,2,3,4,5,6,1,4,5,6,1,2,3,5,6,1,2,3,4,3,4,5,6,1,2,
1,2,3,4,5,6,5,6,1,2,3,4,4,5,6,1,2,3,6,1,2,3,4,5,2,3,4,5,6,1,
2,3,4,5,6,1,6,1,2,3,4,5,3,4,5,6,1,2,5,6,1,2,3,4,1,2,3,4,5,6,
3,4,5,6,1,2,2,3,4,5,6,1,5,6,1,2,3,4,1,2,3,4,5,6,4,5,6,1,2,3,
4,5,6,1,2,3,1,2,3,4,5,6,6,1,2,3,4,5,2,3,4,5,6,1,3,4,5,6,1,2,
5,6,1,2,3,4,3,4,5,6,1,2,1,2,3,4,5,6,4,5,6,1,2,3,6,1,2,3,4,5,
6,1,2,3,4,5,4,5,6,1,2,3,2,3,4,5,6,1,3,4,5,6,1,2,5,6,1,2,3,4

[Nataly-Mak]

Продолжаю пример.
Если строить сильноокрашенный прямоугольник, то у меня получается такой strong 6-coloring прямоугольник 5х30:

(Оффтоп)

5,30,1, 1, 1, 1, 1,
2, 2, 2, 2, 2,
3, 3, 3, 3, 3,
4, 4, 4, 4, 4,
5, 5, 5, 5, 5,
6, 6, 6, 6, 6,
1, 2, 3, 4, 5,
2, 1, 4, 3, 6,
3, 4, 6, 5, 2,
4, 3, 5, 6, 1,
5, 6, 2, 1, 3,
6, 5, 1, 2, 4,
1, 3, 2, 5, 4,
2, 4, 1, 6, 3,
3, 6, 4, 2, 5,
4, 5, 3, 1, 6,
5, 2, 6, 3, 1,
6, 1, 5, 4, 2,
1, 4, 5, 2, 6,
2, 3, 6, 1, 5,
3, 5, 2, 4, 1,
4, 6, 1, 3, 2,
5, 1, 3, 6, 4,
6, 2, 4, 5, 3,
1, 5, 4, 6, 2,
2, 6, 3, 5, 1,
3, 2, 5, 1, 4,
4, 1, 6, 2, 3,
5, 3, 1, 4, 6,
6, 4, 2, 3, 5

Применив к этому прямоугольнику теорему 3.3 (расширение репликациями), получаем то же самое решение 30х30 6-coloring, которое показано в предыдущем посте.
Чтобы получить решение C6N36, надо добавить к решению 30х30 обрамление блоками Ci, Ri (как написано в статье alexBlack).

Замечу, что предложенная мной выше свёртка блоков 6х6 даёт совсем другой способ построения блоков по исходному классическому латинскому квадрату.
Так что, мой пример не вписывается в три примера, приведённых Pavlovsky.

Уверена, что матричный метод имеет огромные возможности, которые мы просто не умеем раскрыть до конца. Все наши попытки крутятся вокруг решения для C=6. Для C=7,8,9 мало интереса этот метод раскалывать, для этих С прекрасно работает метод использования конечных полей. Надо раскалывать матричный метод для C=10. А вот тут мы бессильны пока. Если найдена базовая матрица 8х8 для блоков, построенных циклическим сдвигом, то почему не может найтись базовая матрица 9х9 для блоков другого типа? Проверить все типы блоков мы не в состоянии. И потому поднимаем лапки кверху, то бишь признаём своё бессилие.

-- Пт сен 28, 2012 20:34:50 --

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

Тогда, примерно, ещё через 8 часов должен получиться вектор:

1,2,1,1,...

А ещё через сутки перебор должен закончиться.

Увы, прогноз не подтвердился.
26 часов 35 минут работает новая версия программы (с перерывами).
Базовый вектор на данный момент:

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

Похоже, что на полный перебор (поиск не строго диагонального решения C5N25) потребуется не 2 суток, а 2 недели.

[whitefox]

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

2) Все так называемые "алгебраические" алгоритмы эквиваленты

Вы имеете ввиду алгоритмы основанные на конечных полях?
А как относитесь к моему предложению использовать группы перестановок?
Тоже ведь алгебраические структуры.

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

3) Мой псоледний основной алгоритм выглядит так. Строим сильноокрашенный прямоугольник CKxM. Выбираем исходный ЛК CxC в качестве набора перестановок (каждая колонка - перестановка). Заполняем (перебором) матрицу KxM номерами перестановок, так чтобы у нас не было полупрямоугольников. Первые строку и колонку матрицы заполняем номером 1.

То есть в качестве условия корректности базовой матрицы Вы используете отсутствие прямоугольников вида:

A B
A B

где А и В перестановки?

Но это условие всего-лишь необходимое.

Необходимым и достаточным будет условие приведённое мной выше:

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

Пусть

A B
C D

некоторый прямоугольник в базовой матрице, где A B C D перестановки.

Прямоугольник будет "разрешённым" если перестановка $\mathrm{M}=\mathrm{A}\mathrm{B^{-1}}\mathrm{D}\mathrm{C^{-1}}$ является беспорядочной, то есть не оставляет на месте ни одно число.

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

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

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

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

Использованные ими перестановки являются элементами коммутативной группы. Именно поэтому моё условие:

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

всякий прямоугольник
a b
c d
базовой матрицы является "разрешённым".
То есть перестановка $\mathrm{M}=\mathrm{a}\mathrm{b^{-1}}\mathrm{d}\mathrm{c^{-1}}$ является беспорядочной.

преобразуется в условие:

всякий прямоугольник
a b
c d
базовой матрицы является "разрешённым".
То есть a+d-b-c<>0 (mod 6).

в силу коммутативности использованной группы перестановок.

А все перестановки полученные циклическим сдвигом составляют коммутативную группу.

-- 29 сен 2012, 00:41 --

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

whitefox
можно я приведу своё понимание первого примера Pavlovsky (см. цитату)?
Сама еле-еле разобралась Когда разобралась, всё оказалось очень просто. Тот же самый матричный метод, который завёрнут в "матрицу перестановок, сильноокрашенный прямоугольник". Те же самые штанишки, только пуговки назад

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

Повторю второй метод на примере Pavlovsky №1.

Имеем множество из шести не пересекающихся перестановок:

1: 1 2 3 4 5 6
2: 2 1 4 3 6 5
3: 3 4 6 5 2 1
4: 4 3 5 6 1 2
5: 5 6 2 1 3 4
6: 6 5 1 2 4 3

и базовую матрицу:

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

где числа это номера перестановок.

Заменим эти номера самими перестановками, получим базовую матрицу следующего вида:

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

Каждый столбец этой матрицы является прямоугольником 5х6. И все эти прямоугольники попарно-ортогональны.

Добавим к ним ещё прямоугольник:

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

получим комплект из шести попарно-ортогональных прямоугольников 5х6. Этого достаточно чтобы построить 6-сильный прямоугольник 30х6 (он совпадает с приведённым Pavlovsky).

-- 29 сен 2012, 00:46 --

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

Похоже, что на полный перебор (поиск не строго диагонального решения C5N25) потребуется не 2 суток, а 2 недели.

Конфуций писал(а):

Трудно искать чёрную кошку в тёмной комнате, особенно если её там нет.

[whitefox]

Pavlovsky

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

То есть в качестве условия корректности базовой матрицы Вы используете отсутствие прямоугольников вида:

A B
A B

где А и В перестановки?

Но это условие всего-лишь необходимое.

Необходимым и достаточным будет условие приведённое мной выше:

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

Такая проверка будет эквивалентна проверке, предложенной мной.

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