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

[whitefox]

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

Нет, не смогу.

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

Используя эту программу, Вы сможете проверить все комбинации из четырёх своих блоков на наличие монохромных прямоугольников. Пример такой комбинации:

1 2
3 4

где числа это номера блоков.
Всего таких комбинаций 1296.
В результате получите базу данных запрещённых комбинаций из своих блоков.

Остаётся только написать процедуру перебора с возвратом для заполнения базовой матрицы, использующую эту базу данных.
Уверен, это Вы тоже сможете.

[dimkadimon]

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

А что если существует решение C6N36, которому не соответствует никакой 6-сильный прямоугольник? Такое невозможно разве?
Вот, например, имеем решение C10N94, но пока никто не нашёл 10-сильный прямоугольник 84х10.

Конечно есть такой C6N36, например диагональное решение.

[Nataly-Mak]

Цитата:

Так вот, для C = 6 не существует матрицы CxC из рассматриваемых нами блоков, зато существует 10 вариантов (C-1)x(C-1). Один из них...

(из статьи alexBlack)

Зато существует для С=6 базовая матрица 6х6 из других блоков.

Новый взгляд на строго диагональное решение C6N36

Строго диагональное решение C6N36 прекрасно вписывается в матричный метод.
Это 6 блоков 6х6:

(Оффтоп)

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

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

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

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

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

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

Эти блоки вообще никакие не латинские квадраты. Это не строго диагональные раскраски. В некоторых раскрасках отсутствуют первые цвета, однако максимальный цвет 6 присутствует во всех блоках.
Это базовая матрица 6х6:

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

Замечательная базовая матрица! Классический латинский квадрат 6-го порядка, построенный циклическим сдвигом.
Заполняем базовую матрицу приведёнными блоками в соответствии с их номерами. Получаем строго диагональное решение C6N36.



Понятно, что я шла от готового строго диагонального решения C6N36. Автор этого решения Herbert Kociemba.
Точно так же можно построить строго диагональные решения C3N9, C4N16, C5N25, C7N49.

[Nataly-Mak]

Этот 6-сильный прямоугольник 30х6 получен из 31-символьной строки Pavlovsky



Вписывается ли это решение в теорию построения 6-сильных прямоугольников на основе ЛК и матрицы перестановок?
Или тут так: на основе некоторых классических ЛК 6-го порядка и матрицы перестановок можно построить 6-сильный прямоугольник 30х6, но не любой 6-сильный прямоугольник 30х6 можно построить таким способом

[Pavlovsky]

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

Любое решение можно представить как bipartite graph.

Не понял как это сделать? Таблица ЛК заполнена числами от 0 до N-1. Как такую таблицу интерпретировать как таблицу инцедентности двудольного графа?

-- Пн окт 01, 2012 09:34:31 --

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

Перестановка символов
(0,1,2,3,4,5)
(4,2,1,5,3,0)
Плюс нормализация
Получим:

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

[Nataly-Mak]

Вот набор из шести попарно ортогональных латинских прямоугольников 5х6, соответствующий приведённой в предыдущем посте 6-сильной раскраске 30х6:

(Оффтоп)

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

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

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

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

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

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

Латинские прямоугольники 5х6 обобщённые - полный аналог обобщённых латинских квадратов. Каждый прямоугольник заполнен числами от 1 до 6, и каждое из этих чисел использовано в прямоугольнике ровно 5 раз.

Кстати, из 31-символьной строки Pavlovsky мной получена 6-сильная раскраска 31х6 (пример приведён в книге), которой соответствует такой набор попарно ортогональных обобщённых латинских квадратов 6-го порядка с неполной последней строкой:

(Оффтоп)

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

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

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

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

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

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

Получить 6-сильный прямоугольник с числом строк больше 31 мне не удалось.
Выскажу гипотезу, что не существует 6-сильного прямоугольника mx6 при m>31.

[Pavlovsky]

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

На мой взгляд, ориентация на сильноокрашенный прямоугольник (применённая в последних трёх примерах Pavlovsky) сужает матричный метод.

Я исхожу из постулата, что все алгоритмы "алгебраического" типа эквивалентны.

-- Пн окт 01, 2012 09:46:24 --

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

Кстати, alexBlack в своей статье не ориентировался на сильноокрашенные прямоугольники; он применял матричный метод в общем виде: вот есть 6 блоков 6х6, вот есть базовая матрица 5х5; заполняем базовую матрицу блоками и получаем решение; при этом интересный момент: для одного и того же исходного ЛК он находит 10 (!) различных базовых матриц. Почему 10 Эти все решения разные что ли будут? Или они будут изоморфные?]

Три исходных неизоморфных ЛК и все базовые матрицы 5х5

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
2,3,4,5,3,2,5,6,5,4,6,3,6,5,3,2
2,3,4,6,3,6,2,4,4,2,6,5,6,4,5,3
2,3,4,6,4,2,6,3,5,6,3,4,6,4,5,2
2,3,5,6,3,2,4,5,4,5,6,3,5,6,3,2
2,3,5,6,3,6,4,5,5,4,3,2,6,5,2,3
2,4,5,6,3,2,6,4,4,6,3,5,6,3,4,2
2,4,5,6,4,2,3,5,5,3,2,4,6,5,4,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
2,3,4,6,3,2,5,4,4,6,2,3,6,4,3,2
2,3,4,6,3,2,6,4,4,5,2,3,6,4,3,2
2,3,4,6,3,2,6,4,4,6,2,3,5,4,3,2
2,3,4,6,3,2,6,4,4,6,2,3,6,4,3,2

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
2,4,5,6,4,2,6,5,5,6,2,4,6,5,4,2

-- Пн окт 01, 2012 10:10:08 --

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

А что если существует решение C6N36, которому не соответствует никакой 6-сильный прямоугольник? Такое невозможно разве?

Для сокращения перебора рассматривается некий класс решений. Естественно, наверняка существуют решения C6N36 без 6-сильноокрашенных прямоугольников. Более того решения с сильноокрашенными прямоугольниками имеют естественную верхнюю границу. Квадраты не могут иметь сторону больше C^2. А ведь наверняка существуют решения C6N37, может и больше.

-- Пн окт 01, 2012 10:21:29 --

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

Вот эти 6 блоков:

(Оффтоп)

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

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

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

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

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

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

Составте ЛК из первых колонок ваших блоков:

4,5,6,1,2,3,
6,1,2,3,4,5,
5,6,1,2,3,4,
3,4,5,6,1,2,
1,2,3,4,5,6,
2,3,4,5,6,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

[Nataly-Mak]

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

Три исходных неизоморфных ЛК и все базовые матрицы 5х5

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
2,3,4,5,3,2,5,6,5,4,6,3,6,5,3,2
2,3,4,6,3,6,2,4,4,2,6,5,6,4,5,3
2,3,4,6,4,2,6,3,5,6,3,4,6,4,5,2
2,3,5,6,3,2,4,5,4,5,6,3,5,6,3,2
2,3,5,6,3,6,4,5,5,4,3,2,6,5,2,3
2,4,5,6,3,2,6,4,4,6,3,5,6,3,4,2
2,4,5,6,4,2,3,5,5,3,2,4,6,5,4,2

Почему у вас только 8 базовых матриц, а не 10, как у alexBlack для изоморфного вашему исходного ЛК?

[Pavlovsky]

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

Почему у вас только 8 базовых матриц, а не 10, как у alexBlack для изоморфного вашему исходного ЛК?

Почему вопрос ко мне? Я свои 8 матриц показал. А alexBlack свои десять держит в секрете.

[Nataly-Mak]

Потому что вы показываете 8 матриц, а alexBlack утверждает в статье, что он нашёл 10 матриц.
Вопросы alexBlack я задавать не могу (обещала больше не задавать).

-- Пн окт 01, 2012 09:36:50 --

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

Составте ЛК из первых колонок ваших блоков:

4,5,6,1,2,3,
6,1,2,3,4,5,
5,6,1,2,3,4,
3,4,5,6,1,2,
1,2,3,4,5,6,
2,3,4,5,6,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

То есть вы хотите сказать, что для моего набора блоков существует базовая матрица?

Какая же это матрица? Она такая, как для вашего ЛК №1?
То есть я могу взять любую из 8 приведённых вами матриц, заполнить её своими блоками и получить правильную раскраску? Я правильно вас поняла?

[Pavlovsky]

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

А по теории Pavlovsky для него будет существовать базовая матрица тогда и только тогда, когда он изоморфен одному из ЛК Pavlovsky.

Это не теория, а теорема!

Пусть у нас есть набор C перестановок, сведенных в ЛК CxC. И есть базовая матрица MxK. Такая что если в каждую ячейку подставить перестановку с соответствующим номером, то получится сльноокрашенный прямоугольник CMxK.
1) Поменяем в исходном ЛК две строки местами. Это эквивалентно, что в сильноокрашенном прямоугольнике мы поменяли местами M пар строк. Понятно что свойство сильноокрашенности останется неизменным.
2) Поменяем в исходном ЛК местами пару колонок (пусть колонки i и j). Это эквивалентно, тому что мы изменили нумерацию наших перестановок. Тогда если в базовой матрице поменять число i на j и наоборот. Мы получим тот же сильноокрашенный прямоугольник.
3) Сделаем в исходном ЛК замену символов. Если ту же операцию сделать и в сильноокрашенном прямоугольнике CMxK, то опять же свойство сильноокрашенности не изменится.

Три исходных ЛК 6х6 для которых можно построить матрицу 5х5, получены полным перебором.

-- Пн окт 01, 2012 10:51:57 --

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

То есть я могу взять любую из 8 приведённых вами матриц, заполнить её своими блоками и получить правильную раскраску? Я правильно вас поняла?

Вот матрицы для ваших блоков.

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

-- Пн окт 01, 2012 11:01:25 --

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

Конечно есть такой C6N36, например диагональное решение.

Есть очень большое подозрение, что диагональные решения основанные на теореме Зингера эквивалентны алгоритмам алгебраического типа! Над доказательством сейчас работаю.

[dimkadimon]

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

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

Любое решение можно представить как bipartite graph.

Не понял как это сделать? Таблица ЛК заполнена числами от 0 до N-1. Как такую таблицу интерпретировать как таблицу инцедентности двудольного графа?

Не знаю как сделать для ЛК. А вот для оригинальной задачи знаю. У нас есть матрица А размером nxn. Пронумеруем колонки C1, C2, ..., Cn; пронумеруем строчки R1, R2, ..., Rn. Сделаем двудольный граф с вершинами R1...Rn слева и вершинами C1...Cn справа. Для любой ячейки А(r, c)=k красим ребро Rr-Cc в цвет k. Допустим в матрице А есть запрещенный прямоугольник A(r1,c1)=A(r1,c2)=A(r2,c1)=A(r2,c2), тогда в графе будет цикл длиной 4: Rr1-Cc1-Rr2-Cc2-Rr1.

Думаю тот же метод должен сработать для ЛК.

[Nataly-Mak]

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

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

А по теории Pavlovsky для него будет существовать базовая матрица тогда и только тогда, когда он изоморфен одному из ЛК Pavlovsky.

Это не я писала.

Цитата:

Вот матрицы для ваших блоков.

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

Вы уверены, что при заполнении любой из этих матриц моими блоками (ещё раз подчёркиваю: моими блоками) получится правильное решение C6N36?
Среди этих матриц (самая первая) есть матрица, приведённая в статье alexBlack:

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

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

[Pavlovsky]

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

Вы уверены, что при заполнении любой из этих матриц моими блоками

Не уверен. Ближе к вечеру по экспериментирую.

[Nataly-Mak]

Повторила процедуру заполнения указанной базовой матрицы моими блоками. Как и в прошлый раз, получилось решение C6N30 c 294 ошибками:



-- Пн окт 01, 2012 11:00:18 --

Кстати, whitefox от моих блоков пришёл к дугому исходному ЛК:

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

Им соответствуют следующие перестановки:

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

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

Но эти перестановки составляют латинский квадрат.
А по теории Pavlovsky для него будет существовать базовая матрица тогда и только тогда, когда он изоморфен одному из ЛК Pavlovsky.

-- Пн окт 01, 2012 11:02:55 --

Pavlovsky
а вы пришли от моих блоков к такому исходному ЛК:

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