Prime Sums

[mertz]

I had some constraints on even N so I missed 896. How to transform to canonical representation? Can I shift rows, columns and diagonals? Or is it more complicated? I am not a math person.

[Nataly-Mak]

mertz в сообщении #665781 писал(а):

Can I shift rows, columns and diagonals?

4,10,8,10,4#0,2,0,2,1,3,2,0,2,0,3,1,1,3,1,3,2,4,3,1,3,1,4,2,1,3,1,3,2,4,3,1,3,1,4,2

Вы это имели в виду?

-- Вт янв 01, 2013 04:35:16 --

Последние часы конкурса

Самый активный конкурсант -

Цитата:

30 Yirmy Yasovsky 48.884300 01-01-2013 @ 03:16:41

Играет до последнего
Послединие дни был очень активен, однако планку в 49 баллов так и не преодолел.
Видимо, алгоритм нахождения оптимальных решений для N>7 он не расколол.

Ну, что же, ещё чуть-чуть и можно будет начинать поздравления

[mertz]

Search produces

"887/1777 (4,10,9,8,5)" "3,1,2,0,2,1,2,4,1,3,1,4,3,1,2,0,2,1,1,3,0,2,0,3,4,2,3,1,3,2,2,4,1,3,1,4" 
"887/1777 (5,8,9,10,4)" "4,1,3,2,3,2,2,3,1,4,1,4,3,0,2,1,2,1,1,2,0,3,0,3,4,1,3,2,3,2,1,2,0,3,0,3" 
"887/1777 (4,10,9,8,5)" "4,2,3,1,3,2,1,3,0,2,0,3,3,1,2,0,2,1,2,4,1,3,1,4,3,1,2,0,2,1,2,4,1,3,1,4" 
"887/1777 (4,10,9,8,5)" "0,2,1,3,0,3,2,0,3,1,2,1,1,3,2,4,1,4,3,1,4,2,3,2,1,3,2,4,1,4,2,0,3,1,2,1" 
"887/1777 (4,10,9,8,5)" "1,4,1,3,2,4,2,1,2,0,3,1,0,3,0,2,1,3,3,2,3,1,4,2,1,4,1,3,2,4,2,1,2,0,3,1" 
"887/1777 (4,10,9,8,5)" "0,2,0,3,1,3,2,0,2,1,3,1,1,3,1,4,2,4,3,1,3,2,4,2,1,3,1,4,2,4,2,0,2,1,3,1" 
"887/1777 (5,8,9,10,4)" "2,4,1,3,1,4,4,2,3,1,3,2,1,3,0,2,0,3,4,2,3,1,3,2,1,3,0,2,0,3,3,1,2,0,2,1" 
"887/1777 (5,8,9,10,4)" "0,3,1,2,0,3,2,1,3,0,2,1,0,3,1,2,0,3,3,2,4,1,3,2,1,4,2,3,1,4,3,2,4,1,3,2" 
"887/1777 (5,8,9,10,4)" "0,3,1,3,0,2,3,2,4,2,3,1,0,3,1,3,0,2,2,1,3,1,2,0,1,4,2,4,1,3,3,2,4,2,3,1" 

How do you put into standard form to find duplicates?

[Nataly-Mak]

mertz в сообщении #665790 писал(а):

How do you put into standard form to find duplicates?

К сожалению, я не могу ответить на этот вопрос.
Приведённые мной уникальные схемы принадлежат whitefox.
Подождём его.

[Nataly-Mak]

Уже можно поздравлять что ли?
По моим часам конкурс закончился, у меня 8:30 (мск), в США должна быть полночь (+30 минут).

Только что скопировала таблицу результатов (топ-10):

Цитата:

1 Vladimir Chirkov 50.000000 11-10-2012 @ 15:20:54
2 Valery Pavlovsky 50.000000 12-13-2012 @ 13:15:14
3 Wes Sampson 49.993000 11-07-2012 @ 01:52:19
4 Dmitry Kamenetsky 49.990800 11-01-2012 @ 04:17:50
5 Alex Chernov 49.990800 11-04-2012 @ 20:18:58
6 Robert Gerbicz 49.986400 10-23-2012 @ 22:11:05
7 Herbert Kociemba 49.986400 11-03-2012 @ 13:09:12
8 Serg Belyaev 49.985100 10-31-2012 @ 22:12:29
9 not involved 49.985100 12-01-2012 @ 12:39:54
10 Rick Hennig 49.985100 12-26-2012 @ 08:42:38

Поздравляю с блистательной победой Владимира и Валерия!
Второй раз подряд россияне берут два первых места. Это радует.

Поздравляю Алексея и Сергея с довольно высокими результатами, войти в десятку сильнейших очень даже хорошо.

Вдвойне приятно, что почти все - мои коллеги (по магическим квадратам), кроме Владимира.

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

Поздравляю моего нового коллегу и члена команды Алексея Белышева!
Куда он подевался, ума не приложу
Без него я, конечно же, не поднялась бы так высоко.

Теперь ждём "откровений"

P.S. Я ничего не напутала с часами? Не рано поздравляю?

-- Вт янв 01, 2013 09:04:14 --

Неплохо выступил россиянин Alexander Ponomarev:

Цитата:

32 Alexander Ponomarev 48.056700 12-02-2012 @ 13:39:53

Примерно на этом уровне была бы я, если бы ко мне не присоединился whitefox.

А на конкурсе мёртвая тишина, никаких признаков жизни
Ну да, у них же Новый Год наступил, встречают, значит

[dmd]

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

Выберем в квадрате NxN 2N линий (строки, колонки, диагонали и обратные диагонали). По выбранным линиям можно составить схему пересечений. Такого вида:


В каждой ячейке, число означает количество пересечений выбранных линий в ячейке. Посчитаем количество ячеек с пересечениями каждого вида (a0,a1,a2,a3,a4).
Тогда можно посчитать оценку:
Sum1=a1+a2+a3+a4
Sum2=a2+a3+a4
Sum3=a3+a4
Sum4=a4
Min= [Sum1(Sum1+1)/2]+[Sum2(Sum2+1)/2]+[Sum3(Sum3+1)/2]+[Sum4(Sum4+1)/2]

Все допустимые наборы (a0,a1,a2,a3,a4), соответствующие конкретному минимуму, можно было получить в Математике так:

n=6;min=887;expr=(s1(s1+1)+s2(s2+1)+s3(s3+1)+s4(s4+1))/2/.{s1->a1+a2+a3+a4,s2->a2+a3+a4,s3->a3+a4,s4->a4};{ToRules[Reduce[{expr==min,a0==n^2-a1-a2-a3-a4,a0>=0,a1>=0,a2>=0,a3>=0,a4>=0},{},Integers]]}[[All,All,2]]

её ответ:

{{0,16,16,3,1},{0,17,12,5,2},{0,17,13,2,4},{0,21,2,9,4},{1,13,20,1,1},{1,16,8,10,1},{1,19,1,14,1},{1,19,5,1,10},{2,11,18,4,1},{2,11,19,1,3},{2,12,14,6,2},{2,13,11,7,3},{2,15,8,3,8},{2,16,3,14,1},{2,16,7,1,10},{2,17,1,14,2},{2,18,1,7,8},{2,18,4,0,12},{3,8,24,1,0},{3,11,13,2,7},{3,14,3,16,0},{3,14,6,4,9},{4,7,18,4,3},{4,9,13,3,7},{4,10,8,13,1},{4,10,9,8,5},{4,10,10,5,7},{4,13,6,1,12},{5,4,23,2,2},{5,6,14,11,0},{5,6,16,3,6},{5,7,11,13,0},{5,7,14,2,8},{5,8,9,10,4},{5,10,7,4,10},{5,11,2,14,4},{5,11,3,10,7},{5,11,4,7,9},{6,2,23,4,1},{6,2,24,1,3},{6,5,12,10,3},{6,7,7,12,4},{6,7,10,3,10},{6,8,9,1,12},{6,9,2,18,1},{6,9,5,6,10},{7,1,19,8,1},{7,1,20,4,4},{7,3,13,9,4},{7,4,12,5,8},{7,7,4,11,7},{7,10,1,5,13},{8,2,11,11,4},{8,3,8,15,2},{8,3,10,7,8},{8,3,13,0,12},{8,4,6,14,4},{8,4,7,10,7},{8,4,8,7,9},{8,5,4,14,5},{8,9,1,3,15},{9,5,0,20,2},{9,5,3,8,11},{9,5,6,1,15},{10,1,5,19,1},{10,1,6,13,6},{10,1,10,2,13},{10,6,1,3,16},{11,0,4,18,3},{11,0,7,7,11},{11,1,6,5,13},{11,2,0,19,4},{11,2,2,11,10},{11,3,1,9,12},{13,1,0,8,14},{13,2,2,0,19},{14,0,2,2,18}}

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

[Pavlovsky]

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

[svb]

Пока спят главные герои

1. Задание схемы
Существуют 4 типа линий: горизонтали, вертикали, прямые и обратные диагонали. Для задания $2N$ линий можно можно задать $2N$ пар $(x,t)$, где $x$ - некоторое число $0 \le x < N$, $t = 0...3$ - тип линии. В качестве $x$ можно взять, например, номер горизонтали, которую пересекает линия (для вертикальных линий - номер вертикали).
Отправляясь от заданного набора линий $line[x,t]$ легко считаются параметры схемы (паскаль):

procedure getmet;
var i,j:integer;
begin
  for i:=0 to n-1 do for j:=0 to n-1 do met[i,j]:=0;
  for i:=0 to 2*n-1 do begin
    case line[i,1] of
      0:for j:=0 to n-1 do inc(met[line[i,0],j]);
      1:for j:=0 to n-1 do inc(met[j,line[i,0]]);
      2:for j:=0 to n-1 do inc(met[(line[i,0]+j)mod n,j]);
      3:for j:=0 to n-1 do inc(met[(n+line[i,0]-j)mod n,j]);
    end;
  end;
end;

procedure sco;
var i,j,nn:integer;nco:longint;
begin
  nn:=n*n;nco:=2*nn*(nn+1);
  for i:=0 to 4 do a[i]:=0;
  for i:=0 to n-1 do for j:=0 to n-1 do inc(a[met[i,j]]);
  co:=a[4]*(4+4*a[4]+6*a[3]+4*a[2]+2*a[1])+a[3]*(3+3*a[3]+4*a[2]+2*a[1])+
      a[2]*(2+2*a[2]+2*a[1])+a[1]*(1+a[1]);
  cmin:=co div 2;
  cmax:=nco-co
end;

$met[i,j]$ - матрица пересечений, $cmin, cmax, a[0..4]$ - основные характеристики рассматриваемой схемы.

Возможен случайный выбор линий. Например, по $N/2$ линий каждого типа. Далее осуществляется процедура замены линий (по одной) для достижения необходимого нам значения $cmin$. Это происходит достаточно быстро, в редких случаях локального минимума просто выбираем новый случайный набор.

Случайный выбор оказался достаточным для всех $N$, кроме $N=7$ - этот случай нужно рассматривать отдельно (пропускаем ).

2. Выбор наборов $M_0, M_1,..., M_4$
$M_k$ - это числа, которые расположены в клетках $(i,j)$, для которых $met[i,j]=k$. Задание набора $M_k$ полностью определяет результат. При $N>7$ этот набор почти однозначен, иногда нужно изменить на 1 для достижения четной суммы результата.

3. N>7
После выбора линий и наборов $M_k$ производится перебор для получения $2N$ простых значений для каждой линии. Как это делать? Интуитивно было понятно, что чем больше на линии точек, для которых $met=1$, тем позднее ее можно рассматривать при переборе. Странно, но этого простого соображения оказалось достаточно, хотя и планировался более глубокий анализ.
Итак, после предварительной сортировки линий начинается перебор. В отличии от совсем уж традиционного перебора существовало требование выбора очередного числа из наперед заданного набора $M_k$.
Все. Никаких особых хитростей просто не потребовалось

4. Далее должно начаться самое интересное. Ждем Павловского

[Pavlovsky]

Основной алгоритм построения квадрата.
Входными данными для основного алгоритма являются:
1) Схема (2N зачетных линий)
2) Распределение чисел от 1 до N^2 по группам, согласно заданной схеме.
3) Схема и распределение чисел по группам однозначно задают сумму сумм зачетных линий, то есть сумму решения, которое будет получено в результате выполнения алгоритма.
4) Набор 2N простых чисел.

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

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

Процедура А.
Простые числа упорядочены по возрастанию (если ищем решение-минимум). На каждом шаге выбираем минимально возможное простое число. Такая простая эвристика позволяет на каждом шаге выбирать простое число, которое сложнее всего получить заполнением доступных чисел. Тем самым облегчить задачу заполнения линий на завершающих шагах перебора.
Для каждой незаполненной линии вычисляем минимально и максимально возможную сумму, которую можно получить заполняя их еще доступными числами. Составляем список линий, в которых теоретически возможно выставить выбранное простое число. Случайным выбором определяем линию.

Процедура Б.
Итак мы выбрали линию, каждую ячейку которой мы должны заполнить числами из соответствующей группы чисел. Так чтобы сумма ячеек линии равнялось выбранному простому числу. Получилась такая задача:
Дано: m множеств A1,A2,...,Am. Элементами каждого множества Ai является некоторый набор натуральных чисел. Также задан вектор чисел K1,K2,...,Km. Еще задано число S.
Необходимо: Из каждого множества Ai выбрать Ki чисел, так чтобы сумма выбранных чисел равнялась числу S.
Задача является NP-полной. Причем NP-полной в сильном смысле, для нее не существует псевдополиномиального алгоритма.
Поэтому сделаем так. Для всех Ki>1, разобьем, случайным образом, множество Ai на Ki частей. Тогда у нас получится следующая задача.
Дано: m множеств A1,A2,...,Am. Элементами каждого множества Ai является некоторый набор натуральных чисел. Еще задано число S.
Необходимо: Из каждого множества Ai выбрать ровно одно число, так чтобы сумма выбранных чисел равнялась числу S.
Эта задача тоже является NP-полной. Но ее уже можно решить псевдополиномиальным алгоритмом.

Итак мы заполнили выбранную линию числами. Настал черед описать главную секретную идею. Пусть в нашей линии есть K(K>1) ячеек которые заполнены числами из одной и той же группы. Тогда у нас существует K! способов разместить выбранные числа по этим ячейкам. Поступим так. На текущем этапе не будем однозначно фиксировать числа за ячейками. Просто создадим новую группу чисел! Это позволит на текущем шаге не перебирать K! вариантов, а отложить это на более поздние шаги алгоритма. А на более поздних шагах перебора у нас появится дополнительные возможности выбора.

[Nataly-Mak]

Я что-то не понимаю, меня все в игнор записали что ли?
Между прочим, я поздравила персонально и Pavlovsky, и svb.
По моим устаревшим понятиям не отвечать на поздравления просто невежливо.

Ну, раз я в игноре у всех, то мне здесь делать нечего...

[svb]

Nataly-Mak

[mertz]

I can only reduce to 13.

"887/1777 (4,10,9,8,5) 021213203031132324314142021213314142" 
"887/1777 (4,10,9,8,5) 020313313242131424202131131424202131" 
"887/1777 (5,8,9,10,4) 021213203031132324203031132324314142" 
"887/1777 (4,10,9,8,5) 020313202131131424202131131424313242" 
"887/1777 (5,8,9,10,4) 020313202131131424313242020313313242" 
"887/1777 (5,8,9,10,4) 020313313242020313313242131424202131" 
"887/1777 (5,8,9,10,4) 020313202131020313313242131424313242" 
"887/1777 (5,8,9,10,4) 020313313242020313202131131424313242" 
"887/1777 (4,10,9,8,5) 020313202131131424313242131424202131" 
"887/1777 (4,10,9,8,5) 021213203031021213314142132324314142" 
"887/1777 (5,8,9,10,4) 021213314142132324203031132324203031" 
"887/1777 (4,10,9,8,5) 021213314142021213203031132324314142" 
"887/1777 (5,8,9,10,4) 020313313242131424202131020313313242" 
count= 13 

I am missing a transformation or have an error.

[dmd]

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

Входными данными для основного алгоритма являются:
1) Схема (2N зачетных линий)

Как Вы выбирали схему?

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

4) Набор 2N простых чисел.

Как выбирался набор простых? Для N=5 и его максимума 790 существует более 3500 вариантов сочетаний простых, дающих в сумме 790. Конечно, не все варианты допустимы. Но как тогда отобрать допустимые, или хотя бы случайно ткнуть именно в допустимый вариант? Для больших N количество вариантов сочетаний растёт экспоненциально.

-- Вт янв 01, 2013 21:23:59 --

svb в сообщении #665864 писал(а):

Интуитивно было понятно, что чем больше на линии точек, для которых $met=1$, тем позднее ее можно рассматривать при переборе.

Вот до этой эвристики я не додумался. Учесть отпечаток выбранной схемы на каждой конкретной линии.

[Vovka17]

Имеем следующие обязательные требования для принятия решения:
а)для зачетных линий (суммы зачетных линий должны быть уникальными простыми числами):

$$\begin{cases} L_i\in\mathbb{P},&i=1,2,\ldots,2N;\\ L_m\neq L_n,&m=2,3,\ldots,2N,\quad n=1,2,\ldots,m-1, \end{cases}\eqno(1.1)$$

где $\mathbb{P}$ - множество всех простых чисел, $L_i$ - сумма элементов $i$-ой зачетной линии;


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

$$L'_i\notin\mathbb{P},\qquad \text{если $L'_i \neq L_m$ для всех $m=1,2,\ldots,2N,$}\quad (i=1,2,\ldots,2N)\eqno(1.2)$$

где $L'_i$ - сумма элементов $i$-ой второстепенной линии;


в)для общей суммы (общая сумма должна быть равна или лучше заданной):

$$\sum\limits_{i=1}^{2N}L_i \ ^{\leq S^{\ast}&\text{для Min}}_{\geq S^{\ast}&\text{для Max}}\eqno(1.3)$$

где $S^{\ast}$- заданная сумма для поиска.


Для произвольного заполнения квадрата имеем:
а)отклонения значений зачетных линий от уникальных простых:

$$\Delta_i=\lvert L_i-P_i\rvert, \qquad i=1,2,\ldots,2N;\eqno(2.1)$$

где $P_i$ - уникальное простое число ближайшее к $L_i$.
Для каждой зачетной линии "помечаем" ближайшее простое число. Очевидно, что при таком подходе сумма всех отклонений будет зависеть от порядка, в котором мы отмечали простые. Например, вот два одинаковых случая, различающихся только порядком, в котором рассмотрели зачетные линии:

Но мы на всё это не обращаем внимания (главное, что если ошибок нет, то и сумма всех отклонений равна 0, независимо от порядка):


б)ошибки значений вспомогательных линий:
$$\xi_i=\begin{cases} 0,&\text{если $L'_i \neq P_m$ для всех $m=1,2,\ldots,2N,$;}\\ 1,&\text{для остальных значений $L'_i$;} \end{cases}\quad (i=1,2,\ldots,2N)\eqno(2.2)
где $P_i$ ближайшее к $L_i$ уникальное простое число.


в)ошибка для общей суммы:

$$\Delta_S=\begin{cases} 0,&\text{если $\sum\limits_{i=1}^{2N}L_i \ ^{\leq S^{\ast}&\text{для Min}}_{\geq S^{\ast}&\text{для Max}}$;}\\ \Bigl\lvert S^{\ast}-\sum\limits_{i=1}^{2N}L_i \Bigr\rvert,&\text{если $\sum\limits_{i=1}^{2N}L_i \ ^{> S^{\ast}&\text{для Min}}_{< S^{\ast}&\text{для Max}}$;}\\ \end{cases}\eqno(2.3)$$

Итоговая формула для ошибки заполнения квадрата:

$$\boxed{E=k_1\sum\limits_{i=1}^{2N}\Delta_i+k_2\sum\limits_{i=1}^{2N}\xi_i+k_3\Delta_S}\eqno(3)$$

где $k_1$, $k_2$, $k_3$ - коэффициенты пропорциональности для различных составляющих $E$. Я использовал $k_1=1$, $k_2=1$, $k_3=4$. Эти значения выбраны методом "научного тыка" и "чутья" и некритичны (всё будет работать и при $k_1=k_2=k_3=1$, но, возможно, хуже, а, возможно, лучше - я не проверял).
Главное - то, что при $E=0$ из формулы (3) следует, что выражения (2.1), (2.2) и (2.3) также равны 0, а это автоматически приводит к тому, что условия (1.1), (1.2) и (1.3) выполняются и решение найдено!

Несколько слов о схемах:
Для четных $8\leq N\leq16$ легко выявить оптимальное расположение линий полным перебором (или даже общими соображениями) и продлить это решение на все четные $N\geq8$.
Для нечетных $N>8$, у меня нет строгого алгоритма. Были, не очень сложно, получены оптимальные схемы, но для разных N использовались разные методы... Поэтому, мне здесь говорить нечего, а лучше будет самому послушать других конкурсантов, более успешных в этой части задачи.
Ну и вот, наконец, самое "интересное" - $N=5,6,7$... Да уж ... В общем, дело было так:
Начинал я решать задачу (и успешно решил для $N\geq8$) с использованием двух языков - жутко медленного в работе Нокийского HITа, и жутко медленного в написании FASMа (я очень медленно кодю). В это время, выпросил у наших программистов VS (понимая, что нужна мне и скорость в работе и удобство в написании), установил себе, и начал не торопясь разбираться и переписывать свои алгоритмы уже на C# (параллельно обдумывая как же попроще будет "почистить" изоморфные схемы).
В это время Wes нашел новый рекорд для $N=7$ $Min=1806$. Я попробовал свою совершенно сырую программу и (неожиданно!) за несколько минут нашел $Min=1802$ для $N=7$. Что делать? Вводить это решение сейчас (когда у меня ещё нет 5 топовых результатов), запрограммировать за несколько дней свои мысли о изоморфных схемах и получить недостающие решения, или побыстрому доделать то, что есть и постараться получить результат "здесь и сейчас"... Исходя из совершенно непроверенного допущения, что "изоморфные схемы располагаются во всем множестве схем довольно равномерно" (ключевая фраза - довольно равномерно), был принят третий вариант. Таким образом у меня нет абсолютно никакого отбора схем. Поэтому и писал раньше, что у меня "очень плохой алгоритм...". Совершенно тупой перебор и всё! (Вначале не было времени программить, а потом - желания). Стоит однако заметить, что, например, из тех шести с лишним миллионов схем потенциально подходящих для топов $N=7$, в которых копался алгоритм, ни разу, за 5-6 попыток, не было перебрано более 1% схем (решение находилось раньше) - то есть фраза довольно равномерно - вполне себе работает!..

Далее всё просто. Определяем $E$ из выражения (3) - назовем это энергией. Делаем случайную перестановку пары элементов, опять определяем $E$, методом иммитации отжига (aka SA) стремимся к $E=0$ (начальную температуру выбирал, вопреки рекомендациям, достаточно малую, число итераций - большим)...

Это - всё! (не перечитывал всю свою писанину - наверное ошибок куча , ну да ладно)

Всех с Новым Годом! Ура!!!

[dimkadimon]

Для начала поздравляю всех с Новом Годом!

Поздравляю победителей конкурса Владимира, Валерия и Wes! Горжусь достижением Россиян на етом конкурсе. Приятно была общаться на форуме и читать ваши идеи. Даже понравился "международный скандал" - который я надеюсь приведет к написанию строгих правил. В итоге мне кажется что конкурс удался и выбор 2N был правильным. Задача оказалась может не такой интересной как MonoRectangles, но она была сложной и я многому научился. Я впервые для себя открыл что иногда задача становится гораздо легче если предположить что оптимальное решение можно найти, как например для N>7. Впервые столкнулся с ситуацией где маленькие N решать сложнее.

Мой метод был такой:

1. Задается S которое мы пытаемся достичь.
2. Случайном образом определяем 2N зачетных линий который имеют оценку S или лучше. Для етого надо найти сколько раз каждая клетка будет использоваться в решении (от 0 до 4 раза).
3. Случайным образом раставляем цифры от 1 до N^2, но так чтобы можно было достичь S.
4. Потом используем метод отжига и пытаетмся достичь S. Делаем перестановку пары елементов. Главное: переставляем только те елементы которые зачитываются одинаковое количество раз (смотрите пункт 2) - ведь при етом есть гарантия что сумма решения не поменяется.

Таким образом смог найти 3086 и 1808 для N=7, a вот дальше никак. 19ого Декабря запустил программу для поиска лучших решений и через неделю проверю результаты (еще не смотрел). Есть маленький шанс что будут новые результаты. Возможно есть решения лучше 3090 и 1802.

Отдельное большое спасибо организаторам: Neil, Andrews и Roy.