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 (осталась незаполненной одна строка и одна колонка).




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

31 августа 2012

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

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 

27.08.2017 08:23 FXBrokerNuh
   Agjentët e këmbimit valutor rangut.  fx-brokers-review.com/index_al.ht
 ml 
 
28.08.2017 08:04 UserAdorb
 Лучшего места наверно и не найти, у лингвинума все как положено, оплаты не задерживают. Да
 же промокод есть, но на него надо какое то время потрудиться. Мок код LINGVINIUM#3825
 
31.08.2017 09:16 Adorb
 С другом давно работаем в компании Lingvinium. Оплату за задания отправляют без промахов. 
 
 Можно дополнительно подработать с кодами. Мой промокод ЛИНГВИНИУМ 2345
 
31.08.2017 02:55 ander#19
 Изготовлениесветодиодных табло для спорта, бегущих строк, табло для АЗС
 
01.09.2017 05:08 RogerKargo
 In India you can buy best issues at a good price. Funky, even in black and white, the grap
 hics are enjoyable, diverse, and an ideal way to flesh out your wardrobe. Its news confere
 nce likes the sweet store filled with colour.footwear online shopping.
 
03.09.2017 11:22 DerrickTah
 Bfhuwe fwbihfwei wbfeihfiw jbfiwfv iwefibwe 87ty439hgg
 
03.09.2017 11:22 GeorgeSpite
 Uhwefwi ufhweifhw wnfjweof vbdnvweui wiefweh 47665yt34y
 
04.09.2017 04:46 DerrickTah
 Bfhuwe fwbihfwei wbfeihfiw jbfiwfv iwefibwe 87ty439hgg
 
15.09.2017 04:50 aterr#35
 Изготовлениесветодиодных электронных табло, бегущих строк, табло для АЗС
 
21.09.2017 08:03 Jamesmycle
 Hello everyone, I am new to, please look at a lot, thank you!
 
Вы можете оставить комментарий или задать вопрос
Ваше имя:

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


Copyright © 2009-2014 by