Programming: theory and practice by alexBlack


Главная Эксперименты Утилиты Компоненты Что почитать Контакты
Главная
Эксперименты 
Быстрое умножение матриц

Кривые Безье.Применение

Шрифты.Чтение/запись отдельных символов

Кубик Рубика

Точки пересечения кривых Безье

 topswops 

Алгоритм Бухбергера

Оверлеи многоугольников

 Delphi

Вызов методов по имени 1

Вызов методов по имени 2

 C#

Динамическая реализация интерфейсов

Латинские и магические квадраты

Несамопересекающиеся маршруты коня

Меандры на сетке

Задача о посадке деревьев

Пути ладьи

Monochromatic Squares

Утилиты

 txt2html converter 

Номер телефона словами 

Компоненты

 alTex.dll 

Вычисление выражений

 Тестирование кода в Delphi

Что почитать

Контакты



















    Форум программистов


    Конкурсы, статьи по математике


    Популярная математика для взрослых

    Fractal Image Compression












Monochromatic Squares





Содержание







Очередная задача конкурса Infinite Search Space:
для решетки NxN требуется заполнить ее ячейки C цветами так, чтобы не было 
прямоугольников (имеются в виду прямоугольники со сторонами, параллельными 
границам решетки), у которых все четыре угла одинакового цвета. Для заданного 
цвета C (в конкурсе от 2 до 21) нужно найти максимальное N. Например, для C = 2
максимальное N = 4. Один из вариантов решения:













abba

aabb

abab

baaa





До начала конкурса были известны максимальные значения для C=2,3,4. Эти решения
доступны в интернете. Интересна история поиска G4,18 и красивое 
решение[1]. Кроме того, в статье "Rectangle Free Coloring of Grids"[2] 
был предложен метод для построения Gp,p*p для случая когда p - степень 
простого числа. 




Текст ниже был написан в процессе работы над задачей. Скорее всего интерес 
представляют последние два раздела, где описан способ получения решений для 
C = 15 и C = 21. 





Обозначения

В grid.pdf принято обозначать: c-coloring Gn,m. Нижние индексы - размер 
сетки. Чтобы не писать каждый раз c-coloring, перенесем в нижние индексы и 
переменную c. Т.о. Gc|n,m обозначает c-coloring сетку размером nxm. 
Если сетка квадратная, второй размер можно не указывать: Gc|n.




Блоки с циклическим сдвигом

Разобьем сетку на блоки размером CxC. Внутри каждого блока CxC будем 
использовать заполнение циклическим сдвигом по горизонтали и вертикали. 
Каждый такой блок можно закодировать позицией элемента цвета (a) в 
первой строке. Если оба сдвига положительны, имеем C блоков. 
Например, для C = 5:













0
1
2
3
4













a


a
a
a
a















a
a
a
a

a














a
a
a

a


a














a
a

a
a


a














a

a
a
a


a




Теперь простым перебором будем искать матрицу таких блоков проверяя 
правильность решения с учетом структуры выбранных блоков. 
Очень быстро такие матрицы находятся для C = 5 и C = 7: 

























01234

41442

31100

21313

11021















0123456

6150504

5114622

4141040

3105165

2132213

1166331







Квадрат G5|25, построенный по этой таблице:
 










abcde eabcd deabc cdeab bcdea 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 

bcdea eabcd bcdea bcdea deabc 
abcde deabc abcde abcde cdeab 
eabcd cdeab eabcd eabcd bcdea 
deabc bcdea deabc deabc abcde 
cdeab abcde cdeab cdeab eabcd 

cdeab eabcd eabcd abcde abcde 
bcdea deabc deabc eabcd eabcd 
abcde cdeab cdeab deabc deabc 
eabcd bcdea bcdea cdeab cdeab 
deabc abcde abcde bcdea bcdea 

deabc eabcd cdeab eabcd cdeab 
cdeab deabc bcdea deabc bcdea 
bcdea cdeab abcde cdeab abcde 
abcde bcdea eabcd bcdea eabcd 
eabcd abcde deabc abcde deabc 

eabcd eabcd abcde deabc eabcd 
deabc deabc eabcd cdeab deabc 
cdeab cdeab deabc bcdea cdeab 
bcdea bcdea cdeab abcde bcdea 
abcde abcde bcdea eabcd abcde 





Существуют еще два блока, заполненных циклически, но без сдвига по 
вертикали/горизонтали. У Холла[3] эти матрицы названы R и C













R
C













aaaaa

bbbbb

ccccc

ddddd

eeeee















abcde

abcde

abcde

abcde

abcde







Для нас важна еще и позиция цвета (a), поэтому таких матриц будет C 
и обозначать их будем R0, R1 … C0, C1 … 
Используя эти матрицы мы можем расширить полученное решение вправо или 
вниз. Например, расширение вправо: 












abcde eabcd deabc cdeab bcdea abcde
eabcd deabc cdeab bcdea abcde abcde
deabc cdeab bcdea abcde eabcd abcde
cdeab bcdea abcde eabcd deabc abcde
bcdea abcde eabcd deabc cdeab abcde

bcdea eabcd bcdea bcdea deabc eabcd
abcde deabc abcde abcde cdeab eabcd
eabcd cdeab eabcd eabcd bcdea eabcd
deabc bcdea deabc deabc abcde eabcd
cdeab abcde cdeab cdeab eabcd eabcd

cdeab eabcd eabcd abcde abcde deabc
bcdea deabc deabc eabcd eabcd deabc
abcde cdeab cdeab deabc deabc deabc
eabcd bcdea bcdea cdeab cdeab deabc
deabc abcde abcde bcdea bcdea deabc

deabc eabcd cdeab eabcd cdeab cdeab
cdeab deabc bcdea deabc bcdea cdeab
bcdea cdeab abcde cdeab abcde cdeab
abcde bcdea eabcd bcdea eabcd cdeab
eabcd abcde deabc abcde deabc cdeab

eabcd eabcd abcde deabc eabcd bcdea
deabc deabc eabcd cdeab deabc bcdea
cdeab cdeab deabc bcdea cdeab bcdea
bcdea bcdea cdeab abcde bcdea bcdea
abcde abcde bcdea eabcd abcde bcdea





Или, просто номерами блоков:

























01234C0

41442C1

31100C2

21313C3

11021C4















01234

41442

31100

21313

11021

R0R1R2R3R4







То есть для получения того же решения достаточно матрицы из (C-1)x(C-1) блоков













0123С0

4144С1

3110С2

2131С3

R0R1R2R3R4





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













00000C0

01234C1

02413C2

04152C3

05321C4

R0R1R2R3R4R5





Некоторые простые замечанию позволяют значительно ускорить перебор 
таких блоков. Например, переносом столбцов все блоки в первом ряду
можно привести к 0, также как и все блоки в первой колонке переносом 
строк. Во второй строке блоков переносом столбцов блоков можно 
расставить блоки по неубыванию, также как и во втором столбце. 
Для C = 10 удается сделать полный перебор. Возможна только матрица 8x8 
таких блоков и, соответственно, решение G10|90. 




Группы ортогональных латинских квадратов

Для полноты картины. Если есть группа ОЛК, то легко получаются 
и нужные нам решения. Например, возьмем 4 ортогональных квадрата 
пятого порядка 











01234 01234 01234 01234
12403 24310 30142 43021
24310 30142 43021 12403
30142 43021 12403 24310
43021 12403 24310 30142





Если рассматривать элементы этих квадратов как позицию цвета (a) в 
колонке, получаем уже знакомую нам картину:











Остается только дополнить решение справа C-матрицами. 




Конечные проективные плоскости

Еще один вариант построения Gp|p*p (p - простое или степень простого числа) - 
использование метода построения конечных проективных плоскостей. 
Рассмотрим метод на примере p=9. Возьмем таблицы сложения и умножения в GF(9). 













+
0
1
2
3
4
5
6
7
8
*
0
1
2
3
4
5
6
7
8

0
0
1
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0

1
1
2
0
4
5
3
7
8
6
1
0
1
2
3
4
5
6
7
8

2
2
0
1
5
3
4
8
6
7
2
0
2
1
6
8
7
3
5
4

3
3
4
5
6
7
8
0
1
2
3
0
3
6
2
5
8
1
4
7

4
4
5
3
7
8
6
1
2
0
4
0
4
8
5
6
1
7
2
3

5
5
3
4
8
6
7
2
0
1
5
0
5
7
8
1
3
4
6
2

6
6
7
8
0
1
2
3
4
5
6
0
6
3
1
7
4
2
8
5

7
7
8
6
1
2
0
4
5
3
7
0
7
5
4
2
6
8
3
1

8
8
6
7
2
0
1
5
3
4
8
0
8
4
7
3
2
5
1
6





Возьмем строку из девяти блоков 9x9. Рассматривая элементы таблицы сложения 
как смещение цвета (a) в строке соответствующего блока получаем:











 ----0---- ----1---- ----2---- ----3---- ----4---- ----5---- ----6---- ----7---- ----8----
 a........ .a....... ..a...... ...a..... ....a.... .....a... ......a.. .......a. ........a 
 .a....... ..a...... a........ ....a.... .....a... ...a..... .......a. ........a ......a..
 ..a...... a........ .a....... .....a... ...a..... ....a.... ........a ......a.. .......a.
 ...a..... ....a.... .....a... ......a.. .......a. ........a a........ .a....... ..a......
 ....a.... .....a... ...a..... .......a. ........a ......a.. .a....... ..a...... a........
 .....a... ...a..... ....a.... ........a ......a.. .......a. ..a...... a........ .a.......
 ......a.. .......a. ........a a........ .a....... ..a...... ...a..... ....a.... .....a...
 .......a. ........a ......a.. .a....... ..a...... a........ ....a.... .....a... ...a.....
 ........a ......a.. .......a. ..a...... a........ .a....... .....a... ...a..... ....a....





Подставляя блоки в таблицу умножения получаем следующую таблицу (показана только ее часть):











----0---- ----0---- ----0----       ----0----
a........ a........ a........       a........ 
.a....... .a....... .a.......       .a....... 
..a...... ..a...... ..a......       ..a...... 
...a..... ...a..... ...a.....       ...a..... 
....a.... ....a.... ....a....  ...  ....a.... 
.....a... .....a... .....a...       .....a... 
......a.. ......a.. ......a..       ......a.. 
.......a. .......a. .......a.       .......a. 
........a ........a ........a       ........a 
                                    
----0---- ----1---- ----2----       ----8----
a........ .a....... ..a......       ........a 
.a....... ..a...... a........       ......a.. 
..a...... a........ .a.......       .......a. 
...a..... ....a.... .....a...       ..a...... 
....a.... .....a... ...a.....  ...  a........ 
.....a... ...a..... ....a....       .a....... 
......a.. .......a. ........a       .....a... 
.......a. ........a ......a..       ...a..... 
........a ......a.. .......a.       ....a.... 
 
   ...       ...       ...     ...     ...    
         
----0---- ----8---- ----4----       ----6---- 
a........ ........a ....a....       ......a.. 
.a....... ......a.. .....a...       .......a. 
..a...... .......a. ...a.....       ........a 
...a..... ..a...... .......a.       a........ 
....a.... a........ ........a  ...  .a....... 
.....a... .a....... ......a..       ..a...... 
......a.. .....a... .a.......       ...a..... 
.......a. ...a..... ..a......       ....a.... 
........a ....a.... a........       .....a... 





Циклическим сдвигом вправо дополняем таблицу другими цветами и получаем 
решение G9|81. Собственно, полученая таблица - это часть матрицы
инцидентности для конечной проективной плоскости 9-го порядка. Недостающая 
часть достраивается очень легко и из полной матрицы можно мы получаем решение 
G10|91. 




Добавление C+1 строк при увеличении количества цветов на 1


  Gc|n → Gc+1|n+(c+1) 



Этот варинат расширения мы уже рассматривали выше. Это простое добавление 
R, C-матриц. Мы по-прежнему используем решения из циклически заполненных блоков.
Важное свойство таких блоков, необходимое для расширения - блок является 
латинским квадратом. 




Добавление C+3 строк при увеличении количества цветов на 1


  Gc|n → Gc+1|n+2+(c+1) 



Вернемся к решению, построенному по проективной плоскости. По сути это 
расширение strong 9-coloring прямоугольника 81x9 до квадрата 81x81. 
Взглянем на исходный strong 9-coloring прямоугольник 81x9 (ниже слева).
Его можно рассматривать и как strong 10-coloring прямоугольник, что дает 
нам решение 81x90. Кроме того, видно, что прямоугольник можно дополнить 
одной строкой из девяток. Ниже в примере девятки заменены символом A, 
чтобы были видны изменения. Вторую строку можно добавить, если заменить 
девяткой некоторые из ячеек выше. В данном случае для второй строки 
был использован простенький перебор. 









Замены подобраны так, что каждый из блоков (теперь их стало 10) по-прежнему 
остается латинским квадратом и, следовательно, мы можем дополнить справа 
и снизу R,C-матрицами. Получаем прямоугольник 93x100.




Добавление C+2 строк при увеличении количества цветов на 1


  Gc|n → Gc+1|n+1+(c+1)  



Исторически это решение было получено ранее предыдущего. При добавлении 
одного цвета это решение не дает нам ничего нового, но от него проще перейти 
к следующему решению для добавления двух цветов. 




Используемые нами выше в почти всех решениях блоки имеют одно интересное 
свойство. При циклическом заполнении всегда используется один 
вид диагоналей. Это приводит к тому, что для блоков нечетного размера
второй вид диагоналей содержит разные цвета. Возьмем, например, блок 
с кодом 0. Прямые диагонали содержат ячейки одинакового цвета, 
обратные - разного.













abcde

eabcd

deabc

cdeab

bcdea





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

























acebd

Fbcde

eabcF

deaFc

cdFab

bFdea
















aFbcde

deabcF

bdeaFc

ecdFab

cbFdea
















acebd

aFbcde

deabcF

bdeaFc

ecdFab

cbFdea
















aFcebd

Fabcde

deabcF

bdeaFc

ecdFab

cbFdea








Обратите внимание на последнюю замену. Верхний левый угловой элемент можно 
заполнить новым цветом (F), но можно сделать и обратную замену цветов. В 
данном случае элемент заполнен цветом (a), а в основном блоке цвет (a),
который был вынесен, возвращен обратно и вместо него в верхнюю строку 
и левую колонку вынесен цвет (F).
 



Зайдем с другой стороны. Возьмем строку блоков из решения G5|25:











abcde eabcd deabc cdeab bcdea 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 





Вынесем из первой строки цвета (a) вверх и заменим их цветом (F).











a      a      a      a      a
Fbcde eFbcd deFbc cdeFb bcdeF 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 





Это то же самое, как если бы мы разделили строку на две части - одна 
часть - цвета (a), другая все остальные цвета. Естественно, после такого 
деления решение остается корректным. Заменив пустые места цветом (F) 
мы тоже не утратим правильность, т.к. эти позиции ранее занимал цвет (a). 




Аналогично, можно вынести цвет (с ) из последней строки, цвет (e) из 
предпоследней строки: 











ac     ac     ac     ac c   a
Fbcde eFbcd deFbc cdeFb bcdeF 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bFdea abFde eabFd deabF Fdeab 





и так далее. В результате верняя строка будет заполнена полность, а 
цвет (F) займет в каждом блоке обратную диагональ.




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




Теперь возьмем готовое решение, полученном из конечных геометрий, и 
применим эту процедуру к верхней строке и левой колонке блоков: 
G5|25 → G6|32:













Исходный квадратРезультат












abcde eabcd deabc cdeab bcdea 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 

bcdea eabcd bcdea bcdea deabc 
abcde deabc abcde abcde cdeab 
eabcd cdeab eabcd eabcd bcdea 
deabc bcdea deabc deabc abcde 
cdeab abcde cdeab cdeab eabcd 

cdeab eabcd eabcd abcde abcde 
bcdea deabc deabc eabcd eabcd 
abcde cdeab cdeab deabc deabc 
eabcd bcdea bcdea cdeab cdeab 
deabc abcde abcde bcdea bcdea 

deabc eabcd cdeab eabcd cdeab 
cdeab deabc bcdea deabc bcdea 
bcdea cdeab abcde cdeab abcde 
abcde bcdea eabcd bcdea eabcd 
eabcd abcde deabc abcde deabc 

eabcd eabcd abcde deabc eabcd 
deabc deabc eabcd cdeab deabc 
cdeab cdeab deabc bcdea cdeab 
bcdea bcdea cdeab abcde bcdea 
abcde abcde bcdea eabcd abcde 









a|Fcebd daceb bdace ebdac cebda|abcdeF
-|-----------------------------|------
F|abcde eFbcd deFbc cdeFb bcdeF|abcdeF
d|eabcF Feabc cFeab bcFea abcFe|abcdeF
b|deaFc cdeaF Fcdea aFcde eaFcd|abcdeF
e|cdFab bcdFa abcdF Fabcd dFabc|abcdeF
c|bFdea abFde eabFd deabF Fdeab|abcdeF
 |                             |
c|bFdea eabcd bcdea bcdea deabc|bcdeFa
a|Fbcde deabc abcde abcde cdeab|bcdeFa
d|eabcF cdeab eabcd eabcd bcdea|bcdeFa
b|deaFc bcdea deabc deabc abcde|bcdeFa
e|cdFab abcde cdeab cdeab eabcd|bcdeFa
 |                             |
e|cdFab eabcd eabcd abcde abcde|cdeFab
c|bFdea deabc deabc eabcd eabcd|cdeFab
a|Fbcde cdeab cdeab deabc deabc|cdeFab
d|eabcF bcdea bcdea cdeab cdeab|cdeFab
b|deaFc abcde abcde bcdea bcdea|cdeFab
 |                             |
b|deaFc eabcd cdeab eabcd cdeab|deFabc
e|cdFab deabc bcdea deabc bcdea|deFabc
c|bFdea cdeab abcde cdeab abcde|deFabc
a|Fbcde bcdea eabcd bcdea eabcd|deFabc
d|eabcF abcde deabc abcde deabc|deFabc
 |                             |
d|eabcF eabcd abcde deabc eabcd|eFabcd
b|deaFc deabc eabcd cdeab deabc|eFabcd
e|cdFab cdeab deabc bcdea cdeab|eFabcd
c|bFdea bcdea cdeab abcde bcdea|eFabcd
a|Fbcde abcde bcdea eabcd abcde|eFabcd
-|-----------------------------|------
F|aaaaa bbbbb ccccc ddddd eeeee|Fabcde
a|bbbbb ccccc ddddd eeeee FFFFF|Fabcde
b|ccccc ddddd eeeee FFFFF aaaaa|Fabcde
c|ddddd eeeee FFFFF aaaaa bbbbb|Fabcde
d|eeeee FFFFF aaaaa bbbbb ccccc|Fabcde
e|FFFFF aaaaa bbbbb ccccc ddddd|Fabcde





еще один вариант 












Добавление C+10 строк при увеличении количества цветов на 2


  Gc|n → Gc+2|n+8+(c+2) 



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











. acebd . daceb . bdace . ebdac . cebda 
                                  
a Fbcde e FGbcd c deGbF a cdeGb d bcFeG 
d eabcF c GeabF a cGeFb d bcGea b aFcGe 
b deaFc a cdeFG d GcFea b aGcde e FaGcd 
e cdFab d bcFGa b aFcdG e Gabcd c dGabF 
c bFdea b aFGde e FabGd c deabG a GdeFb 
                                  
. daceb . ebdac . daceb . daceb . cebda 
                                  
c bFdGa e Fabcd d bcFGa d bcFGa c dGabF 
a FbGde c deabF b aFGde b aFGde a GdeFb 
d eGbcF a cdeFb e FGbcd e FGbcd d bcFeG 
b GeaFc d bcFea c GeabF c GeabF b aFcGe 
e cdFaG b aFcde a cdeFG a cdeFG e FaGcd 
                                  
. acebd . ebdac . ebdac . bdace . bdace 
                                  
e cdFab e Fabcd e Fabcd b aFcdG b aFcdG 
c bFdea c deabF c deabF e FabGd e FabGd 
a Fbcde a cdeFb a cdeFb c deGbF c deGbF 
d eabcF d bcFea d bcFea a cGeFb a cGeFb 
b deaFc b aFcde b aFcde d GcFea d GcFea 
                                  
. cebda . ebdac . acebd . ebdac . acebd 
                                  
b dGaFc e Fabcd a cdGFb e Fabcd a cdGFb 
e GdFab c deabF d bGFea c deabF d bGFea 
c bFdeG a cdeFb b GFcde a cdeFb b GFcde 
a FbcGe d bcFea e FabcG d bcFea e FabcG 
d eaGcF b aFcde c deaGF b aFcde c deaGF 
                                  
. ebdac . ebdac . bdace . cebda . ebdac 
                                  
d GabcF e Fabcd b aFcdG c dGabF e Fabcd 
b deaFG c deabF e FabGd a GdeFb c deabF 
e cdFGb a cdeFb c deGbF d bcFeG a cdeFb 
c bFGea d bcFea a cGeFb b aFcGe d bcFea 
a FGcde b aFcde d GcFea e FaGcd b aFcde 





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











a Fcebd . daceb . bdace . ebdac . cebda 
                                  
F abcde e FGbcd c deGbF a cdeGb d bcFeG 
d eabcF c GeabF a cGeFb d bcGea b aFcGe 
b deaFc a cdeFG d GcFea b aGcde e FaGcd 
e cdFab d bcFGa b aFcdG e Gabcd c dGabF 
c bFdea b aFGde e FabGd c deabG a GdeFb 
                                  
. daceb e Fbdac . daceb . daceb . cebda 
                                  
c bFdGa F eabcd d bcFGa d bcFGa c dGabF 
a FbGde c deabF b aFGde b aFGde a GdeFb 
d eGbcF a cdeFb e FGbcd e FGbcd d bcFeG 
b GeaFc d bcFea c GeabF c GeabF b aFcGe 
e cdFaG b aFcde a cdeFG a cdeFG e FaGcd 
                                  
. acebd e Fbdac e Fbdac . bdace . bdace 
                                  
e cdFab F eabcd F eabcd b aFcdG b aFcdG 
c bFdea c deabF c deabF e FabGd e FabGd 
a Fbcde a cdeFb a cdeFb c deGbF c deGbF 
d eabcF d bcFea d bcFea a cGeFb a cGeFb 
b deaFc b aFcde b aFcde d GcFea d GcFea 
                                  
. cebda e Fbdac . acebd e Fbdac . acebd 
                                  
b dGaFc F eabcd a cdGFb F eabcd a cdGFb 
e GdFab c deabF d bGFea c deabF d bGFea 
c bFdeG a cdeFb b GFcde a cdeFb b GFcde 
a FbcGe d bcFea e FabcG d bcFea e FabcG 
d eaGcF b aFcde c deaGF b aFcde c deaGF 
                                  
. ebdac e Fbdac . bdace . cebda e Fbdac 
                                  
d GabcF F eabcd b aFcdG c dGabF F eabcd 
b deaFG c deabF e FabGd a GdeFb c deabF 
e cdFGb a cdeFb c deGbF d bcFeG a cdeFb 
c bFGea d bcFea a cGeFb b aFcGe d bcFea 
a FGcde b aFcde d GcFea e FaGcd b aFcde 





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











a....
.e...
.ee..
.e.e.
.e..e





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











1     2       3         4            5              6                7
----------------------------------------------------------------------------------
.     . 0     . 0 0     . 0 0 0      . 0 0 0 1      . 0 0 0 1 1      . 1 1 1 0 0 0 
      0 .     0 . 0     0 . 0 1      0 . 0 1 0      0 . 0 1 1 0      0 . 1 0 1 1 0 
              0 0 .     0 0 . 1      0 0 . 1 1      0 0 . 1 0 1      0 0 . 1 1 0 1 
                        0 1 1 .      0 1 1 . 1      1 0 1 . 1 0      0 1 0 . 0 1 1 
                                     1 0 1 1 .      0 1 1 0 . 1      1 0 0 1 . 1 0 
                                                    1 1 0 1 0 .      1 0 1 0 0 . 1 
                                                                     1 1 0 0 1 0 . 





Для квадрата 8x8 найдено решение с восемью дырками (кроме диагонали):











8:8 -> 
. 1 . 1 1 0 0 0 
1 . 1 1 0 1 0 . 
. 0 . 0 1 1 1 0 
1 1 0 . 0 . 1 0 
. 0 0 1 . 0 1 1 
1 . 0 0 1 . 0 1 
0 1 1 0 0 0 . 1 
0 0 1 . 1 . 0 . 





Для квадрата 9x9 найдено только решение с 14-ю дырками (кроме диагонали)










9:14 ->
. 1 . 1 . 1 0 0 0 
1 . 1 . 0 0 0 . 1 
. 1 . 0 1 0 . 0 1 
1 . 0 . 0 1 1 0 . 
. 0 0 0 . 1 0 1 1 
0 1 1 0 0 . 1 1 0 
1 0 . 1 1 0 . 1 0 
0 . 0 1 . 0 1 . 1 
0 0 1 . 1 1 . 0 . 





Возвращаясь к нашей задаче для C = 15,21 удалось найти расположение
угловых элементов 8x8, которое можно дополнить двумя цветами. Поэтому при 
увеличении цвета на 2 размер квадрата увеличивается на (8+(c+2)), естественно
для c ≥ 8. 






Остальные угловые элементы я заполнял используя алгоритм "отжига". Этим методом 
удалось получить G15|197 (т.е. заполнены все угловые элементы) 
и G21|400 (осталась незаполненной одна строка и одна колонка). 












1↑Extremely Complex 4-Colored Rectangle-Free Grids



2↑Rectangle Free Coloring of Grids



3↑М.Холл. Комбинаторика.













31 августа 2012





 

    
Downloads

      

        
        

    all solutions (sl_ms.zip) (690 Кб, просмотров:  1285
)
        

        
      

   
 
 

    

      

      
Comments
          

      

      
01.09.2012 07:25  Сергей Беляев  
 Поздравляю с победой!

03.10.2012 07:45  Наталия  
 \"...зато существует 10 вариантов (C-1)x(C-1). Один из них...\"
 Хотелось бы увидеть остальные 9 матриц. 
 

03.10.2012 08:28  alexBlack  
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0 
 0 1 2 3 4   0 1 3 4 5   0 1 2 3 4   0 1 3 4 5   0 2 3 4 5 
 0 2 5 1 3   0 2 5 1 3   0 2 4 1 3   0 2 5 1 4   0 3 5 1 4 
 0 3 1 4 2   0 3 1 5 2   0 4 1 5 2   0 4 2 5 3   0 4 2 5 3 
 0 5 4 2 1   0 5 4 3 1   0 5 3 2 1   0 5 4 3 2   0 5 4 2 1 
                      
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0 
 0 1 2 3 5   0 1 2 3 5   0 1 2 4 5   0 1 2 4 5   0 2 3 4 5 
 0 2 5 1 4   0 3 5 1 4   0 2 4 1 3   0 3 5 2 4   0 3 5 2 4 
 0 3 1 4 2   0 4 1 5 3   0 3 1 5 2   0 4 1 5 3   0 4 1 5 2 
 0 4 3 2 1   0 5 3 2 1   0 4 3 2 1   0 5 4 3 2   0 5 4 3 1 


25.07.2022 04:03  ClezeripLover  
  
  
           
  
  
  
           
  
 
 

09.08.2022 12:34  ClezeripLover  
  
  
           
  
  
  
           
  
 
 

28.11.2022 05:19  ClezeripLover  
  
  
           
  
  
  
           
  
 
 

      

      

      
      

      
Вы можете оставить комментарий или задать вопрос
         

         


           

                          Ваше имя: 

             

             Текст сообщения:
             
             
             

             

              
           


         

         
         

      
 
      


      
 
      

    







Copyright © 2009-2014 by