Al Zimmermann: Reversing Nearness

[Herbert Kociemba]

Archimedes в сообщении #1421408 писал(а):

Чем больше копаюсь в задаче, тем больше удивляюсь. Казалось бы, причём тут число 17? Почему именно 17... :)

If you draw two lines with gradients (slopes) -1/4 and 4 onto the flat torus you get 17 squares.

[Herbert Kociemba]

I would like to discuss the case $N\to\infty$. If you code a coordinate $0\leqslant x < N$ as continuous hue value $h=x \frac{360}{N}$ of the hsv-color space the original board (left square x-coordinate, right square y-coordinate) looks like this. Here (0,0) = (red,red) is in the center of the board, x increases to the right, y increases upwards.

The indices of the 17 squares drawn into the y-coordinates (with only five squares drawn here) are not choosen arbitrary. We have

$square(k) = square(0)+\frac{k}{17} 360$

The equation should be read pointwise for corresponding points of square(0) and square(k) of course. square(k) is a color-shifted version of sqare(0).

Observe that the x-coordinate picture is just a 90° rotated version of the y-coordinate. What seems to be the "optimal" solution has the same property, so we only need to draw the y-coordinate picture.
The following picture gives the result of simulated annealing for N= 272, y-coordinate picture shown



It seems that this picture can be generated by slightly rearranging the points of the original squares in a continuous way and then interweaving the squares by sending square(k) to the position of square(2*k mod 17). So for example square(9) is sent to the position of square(1) since 2*9 = 1 mod 17.
If newsquare(k) denotes the slightly rearranged version of square(k) it is also remarkable that

$newsquare(k) = newsquare(0)+\frac{k}{17} 360$

So all squares are distorted in the same way and there essentially is only one square. square(0) has obviously additional symmetry (point reflection with color change h -> 360 - h. The same seems to hold for newsquare(0).

[Herbert Kociemba]

First of all congratulations to the winners of this great contest! I was very curious to see finally the best results and to visualize them. Here is an analysis of the optimal solution for N=30, appropriately transformed by a score preserving transformation, left square x-coordinates, right square y-coordinates:

For any N you always can draw the black grid lines with slopes -1/4 and 4 in such a way, that the lines and in particular the "square" in the center have rotational symmetry. To do so you start in the upper left corner with 2 units to the right (r), 1 unit down (d) and then repeat 4 r and 1 d until you are back in the upper left corner. For the perpendicular line you start in the upper right corner (which of course topologically is the same as the upper left corner) and go 2 d, 1 left (l) and then repeat 4 d and 1 l until you are back.

- The solution nicely fits into this grid, there is only 1 of the 900 cells which does not match the grid (the red square in the upper right of square 6 of the y-coordinates).

- If you rotate the y-coordinates picture 90° clockwise, you do not get exactly the x-coordinates picture but still the resemblance is impressive. Many of the best solutions for smaller N have perfect symmetry.

- If you compare the y-coordinates picture with the y-coordinates picture of the "continuous" case (N=272) I showed in my last post it looks like a rasterized version of the latter.

[Herbert Kociemba]

For N=19 the optimal solution given in the final report also is not completly symmetric. But such solutions exist, here the optimal solution I submitted:



Not only is the the x-coordinate picture exactly the y-coordinate picture rotated by 90°. There also is a point symmetry with color change hue h -> 360 - h.

(EF, EG, RD, RE, SG, RN, SN, AO, BP, SD, AE, BE, BF, DG, BM, CO, DP, EP, FP),
(EE, FE, FF, GF, FL, GO, AM, AN, BO, AD, BD, CE, CF, DF, CM, CN, DO, EO, GP),
(ED, FD, GE, HF, GM, GN, HN, HO, JO, ID, CC, CD, DD, DE, DM, DN, EN, FO, DC),
(FC, GC, GD, HE, GL, HM, IN, IO, KO, IC, JD, JE, KE, KL, EL, EM, FM, FN, EC),
(HB, HC, HD, IE, HL, IL, IM, JN, IB, JC, KC, KD, LE, KK, LM, LN, MN, LO, GB),
(ND, OD, PD, IK, JK, JL, JM, KN, JB, KB, LC, LD, ME, LK, LL, MM, NN, ON, NC),
(OB, OC, QD, PK, PL, PM, QM, KM, KA, LA, LB, MC, MD, MK, ML, NL, NM, MA, NB),
(PB, PC, QC, PJ, QK, QL, RM, SM, RB, SC, AC, MB, MJ, NJ, NK, OL, OM, NA, OA),
(PA, QB, RC, QJ, RK, RL, SL, RA, SA, SB, AB, BC, AJ, BK, BL, OJ, OK, OS, PS),
(QS, QA, QI, RI, RJ, SK, AL, RS, SS, AA, BB, CB, AI, BJ, CK, CL, DL, DA, DB),
(EB, FB, FJ, FK, SI, SJ, AK, SR, AS, BS, BA, CA, BI, CI, CJ, DK, CR, DS, EA),
(FA, GA, FH, FI, GJ, GK, HK, HS, AR, BR, CS, BH, CH, DI, DJ, EK, DR, ER, ES),
(GS, HA, GH, GI, HI, HJ, HQ, HR, IS, IA, JA, JH, DH, EH, EI, EJ, DQ, FR, FS),
(GR, FG, GG, HH, II, IJ, HP, IQ, IR, JS, KS, JG, KH, KI, KJ, LJ, EQ, FQ, GQ),
(NS, IF, HG, IG, IH, JJ, IP, JQ, JR, KR, LS, KG, LH, LI, MI, LP, MQ, MR, MS),
(PR, OG, OH, PH, PI, JI, JP, KP, KQ, LR, JF, LF, LG, MH, NI, MP, NQ, NR, OR),
(QR, OF, PG, QG, QH, QP, QQ, RQ, RR, LQ, KF, MF, MG, NG, NH, MO, NP, OQ, PQ),
(NE, PF, QF, RG, RH, QO, RO, RP, SQ, AQ, SF, AG, AH, NF, OI, NO, OO, OP, PP),
(OE, PE, QE, RF, SH, QN, SO, SP, AP, BQ, SE, AF, BG, CG, BN, CP, CQ, PN, PO)

[Archimedes]

Также поздравляю всех с окончанием конкурса, Herbert'а с 20-м местом, себя с 44-м.
Как обычно, постараюсь максимально точно описать свой путь решения.

Прочитал условия задачи почти сразу после старта, написал самую простую программу с методом Монте-Карло, какую только можно себе представить. Если мне не изменяет память, то этот алгоритм дал не только "пристрелочные" решения до 5х5, но и один реальный - 6х6.
Скажу также, что в этот раз решил использовать для программ язык Java, а не C#, как в прошлые разы. В общем, совмещал приятное с полезным - нужно было освежить навыки написания программ на Java.
К сожалению, на основной работе был аврал, поэтому вернулся к задаче только в середине августа, да и то урывками. В тот момент я переписал алгоритм так, что он стал реализовывать случайные блуждания по совокупности всех вариантов матриц, естественно с ограничениями по удалению от найденного промежуточного оптимума. Это позволило получить решения по N=8 включительно.

Было понятно что для накопления статистики нужно ускорять алгоритм пересчёта рейтинга при перестановке двух ячеек. Алгоритм, реализующий 2*n операций вместо n*n, был написан довольно-таки быстро: день на написание и день на отладку. Получилась такая функция:

(Оффтоп)

public static long Swap2Cells(int i, int j, long lastRate)
{
return Swap2Cells(i, j, lastRate, false);
}


public static long Swap2Cells(int i, int j, long lastRate, boolean bForce)
{
long deltaRate = 0;
long deltaAllRate = 0;
int x1,x2,x3,x4,y1,y2,y3,y4;
int i1 = i;
int j1 = j;
if (i1 > j1)
{
i1 = j;
j1 = i;
}

// Запоминаем старые частные рейтинги
for (int i2=0; i2<fsize; i2++)
tempRate[i2] = field.Rate[i2];

// Пересчитываем i1 на j1
if (i1 > 0)
{
deltaAllRate = tempRate[i1-1];
deltaRate = 0;

for (int i2 = 0; i2 < i1; i2++)
{
x1 = abs(i1 % Dim - i2 % Dim);
y1 = abs(i1 / Dim - i2 / Dim);
x2 = abs(field.Coor[j1] % Dim - field.Coor[i2] % Dim);
y2 = abs(field.Coor[j1] / Dim - field.Coor[i2] / Dim);

deltaRate += Way[x1][y1] * Way[x2][y2];
}
deltaAllRate += deltaRate;
tempRate[i1] = deltaAllRate;
}

// Заменяем по одному числу между i1 и j1
for (int i2=i1+1; i2<j1; i2++)
{
x1 = abs(i1%Dim-i2%Dim);
y1 = abs(i1/Dim-i2/Dim);
x2 = abs(field.Coor[i1]%Dim-field.Coor[i2]%Dim);
y2 = abs(field.Coor[i1]/Dim-field.Coor[i2]/Dim);
x3 = abs(field.Coor[j1]%Dim-field.Coor[i2]%Dim);
y3 = abs(field.Coor[j1]/Dim-field.Coor[i2]/Dim);

tempRate[i2] = tempRate[i2-1] + Way[x1][y1] * (Way[x3][y3] - Way[x2][y2]) + field.Rate[i2] - field.Rate[i2-1];
}

// Пересчёт точки j1
deltaAllRate = tempRate[j1-1];
deltaRate = 0;

for (int i2 = 0; i2 < j1; i2++)
{
x1 = abs(j1 % Dim - i2 % Dim);
y1 = abs(j1 / Dim - i2 / Dim);
if (i2 == i1)
{
x2 = abs(field.Coor[i1] % Dim - field.Coor[j1] % Dim);
y2 = abs(field.Coor[i1] / Dim - field.Coor[j1] / Dim);
}
else
{
x2 = abs(field.Coor[i1] % Dim - field.Coor[i2] % Dim);
y2 = abs(field.Coor[i1] / Dim - field.Coor[i2] / Dim);
}

deltaRate += Way[x1][y1] * Way[x2][y2];
}
deltaAllRate += deltaRate;
tempRate[j1] = deltaAllRate;

// Пересчёт по 2 числа выше j1
deltaAllRate = tempRate[j1];
deltaRate = 0;

for (int i2=j1+1; i2<fsize; i2++)
{
x1 = abs(i1%Dim-i2%Dim);
y1 = abs(i1/Dim-i2/Dim);
x2 = abs(field.Coor[i1]%Dim-field.Coor[i2]%Dim);
y2 = abs(field.Coor[i1]/Dim-field.Coor[i2]/Dim);
x3 = abs(field.Coor[j1]%Dim-field.Coor[i2]%Dim);
y3 = abs(field.Coor[j1]/Dim-field.Coor[i2]/Dim);
x4 = abs(j1%Dim-i2%Dim);
y4 = abs(j1/Dim-i2/Dim);

deltaRate = (Way[x1][y1] - Way[x4][y4])*(Way[x3][y3] - Way[x2][y2]);
deltaAllRate += deltaRate + field.Rate[i2] - field.Rate[i2-1];
tempRate[i2] = deltaAllRate;
}

if ((lastRate > tempRate[fsize-1]) | bForce)
{
int tmp = field.Coor[i1];
field.Coor[i1] = field.Coor[j1];
field.Coor[j1] = tmp;

for (int i2=0; i2<fsize; i2++)
field.Rate[i2] = tempRate[i2];
}
return field.Rate[fsize-1];
}

Естественно, постарался все константы вычислить до основного блока.
Этот алгоритм дал решения до N=11 включительно. Дальше нужно было думать.
Решений было уже 6, особенно интересными были N = {9, 10 и 11}. Попробовал проследить как ведут себя строки, столбцы и диагонали исходной матрицы при преобразовании.

На первой картинке - в разные цвета окрашены строки, на второй - столбцы, на третьей - диагонали.
Уже это решение показывает все особенности, если знать куда смотреть. Видно что строки разбиваются на четыре сегмента, которые собираются по двое около двух центров, отстоящих друг от друга на расстояние N/2 по горизонтали или по вертикали.
Используя эту особенность, я написал блок, определяющий координаты центров для каждого цвета (для каждой строки исходной матрицы), и ограничил перебор перестановок только теми ячейками, которые попадают в ограничение по расстоянию от этих центров.
Этот алгоритм дал решения до N=17 включительно.
Пришлось немного оптимизировать его в плане используемых в переборе констант, а также взаимодействия потоков, перебирающих варианты одинаковых N. Это также дало некоторое ускорение.

Далее я заметил что кандидаты на оптимальные решения для N>17 не имеют более чем 17 областей ячеек, которые в первоначальной матрице стояли не далее 2-х клеток друг от друга.
Например, кандидат для N=18:

Здесь видно что областей всего 17.
Herbert написал здесь после моего вопроса почему это происходит, но я к тому времени уже и сам догадался.
Вот с тем как применить полученное знание для получения результата, у меня были большие проблемы. Я попытался дополнительно ограничить перебор, используя координаты этих "криволинейных квадратов", но это не дало никакого результата.
Очевидно что нужно было заново переписывать программу, реализуя новый алгоритм уже на этапе заполнения матриц-кандидатов в оптимумы, но времени уже не оставалось.
За день до окончания я написал небольшой алгоритм, переставляющий близлежащие ячейки. Я пропустил через него свои кандидаты в оптимумы, и это дало ещё маленькое дополнение к рейтингу - примерно +0,002.
На этом всё закончилось. :)

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

Всем спасибо, всем благ и успехов!