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

[Nataly-Mak]

До начала следующего конкурса осталось

Цитата:

Since we have 9 votes for October 5th, and 8 votes for later dates, I'll split the difference a little and say the official start date will tentatively be October 12th @ 8PM EST (GMT-5). Good luck everyone, and don't forget to donate if you can, every little bit helps.

Администратор писал, что в новом конкурсе будут участвовать простые числа.
Тема древняя и вечная. Вот только как они будут участвовать? Что с ними надо будет делать?

Предлагаю вниманию форумчан свою математическую новеллу "Простые числа":
http://narod.ru/disk/10037356000/prost.pdf.html

Новелла написана в свободном, популярном стиле. Но некоторое представление о простых числах получить можно

[Nataly-Mak]

А это строго диагональное решение C2N4, выданное программой whitefox:



Как я уже отмечала, эта программа работает до первого найденного решения; в данном случае первым найдено строго диагональное решение.

Понятно, что диагональных решений C2N5 не существует по той простой причине, что для С=2 вообще максимальное решение N=4.

[Nataly-Mak]

Процедура достраивания диагональных решений

Эту процедуру я выполняю вручную в программе Эда.
Пример достраивания диагонального решения C4N12 до диагонального решения C4N13. Оба решения не строго диагональные.
Вводим решение C4N12 в программу Эда, добавляем строку и столбец:



Продлеваем диагонали:



В этом примере после продления диагоналей не возникло ни одной ошибки.
Подбором делаем уголок:



Решение C4N13 готово.

Но не всегда так легко удаётся достроить решение вручную; после продления диагоналей возникает очень много ошибок и подбором их уничтожить трудно.
А что если эту процедуру реализовать программно?

Эта процедура помогла мне построить такие диагональные решения, которые уже не берёт программа whitefox (в смысле очень много времени уже требуется, программа надолго задумывается).
Например, мне удалось найти по программе не строго диагональное решение C9N59.
Запустила поиск решения C9N60, всё! Слишком большой перебор, решение быстро не находится; сколько потребуется времени, чтобы его найти, одному Богу известно.
Тогда пробую ручное достраивание, и... легко получаю решение C9N60, а потом из этого решения ещё и решение C9N61.

Конечно, не строго диагональные решения C9N60, C9N61 можно запросто получить из строго диагонального решение C9N73 (Herbert Kociemba) путём удаления строк и столбцов (как и все другие решения для N<73), но... мало интереса
Все эти решения будут однотипные и не интересные. Интересно идти именно от малых N к большим, а не наоборот.

[Nataly-Mak]

Закончила работу над новой версией базы данных строго диагональных решений.
В БД представлено 67 решений.
В основном это решения Herbert Kociemba, но добавлено несколько решений svb и whitefox. Ну, и совсем немного моих решений, построенных вручную.

Выложила БД на форуме конкурса:
http://infinitesearchspace.dyndns.org/c ... -aftermath

[формат pdf, 1.7 Мб]

Плохо, что здесь нельзя прикреплять файлы. Не хочется ещё и на файлообменник загружать.

Просьба написать о замеченных ошибках, опечатках, неточностях.
Вторая просьба: если есть у кого решения CxNy, отсутствующие в БД, присылайте, пожалуйста.

[Nataly-Mak]

dimkadimon на форуме конкурса писал:

Цитата:

I would really like to find C5N26, because I am confident that it exists. Meanwhile it would be nice to find 16x31 at least. Please update this topic with your findings.

dimkadimon
откуда такая уверенность, что решение C5N26 существует?

А прямоугольник 16х31 5-coloring существует?
У меня такой прямоугольник меньше, чем с 8 ошибками, не получается.

(Оффтоп)

16,31,A,B,B,B,C,C,C,D,D,D,D,E,E,E,E,E,D,B,A,E,C,B,A,D,C,B,A,E,D,C,B,A,B,B,E,C,C,A,D,D,B,E,C,
E,C,A,D,B,E,B,D,A,C,E,B,D,A,C,E,E,B,D,A,C,C,B,C,D,C,D,E,D,E,A,B,E,A,B,C,D,B,C,C,C,D,D,D,E,E,
E,E,A,A,A,A,A,E,C,B,A,D,C,B,E,D,C,B,A,E,D,C,B,C,C,A,D,D,B,E,E,C,A,D,A,D,B,E,C,A,C,E,B,D,A,C,E
,B,D,A,A,C,E,B,D,D,C,D,E,D,E,A,E,A,B,C,A,B,C,D,E,C,D,D,D,E,E,E,A,A,C,A,B,B,B,B,B,A,D,C,B,E,D,
C,A,E,D,C,B,A,E,D,C,D,D,B,E,E,C,A,A,D,B,E,B,E,C,A,C,B,D,A,C,E,B,D,A,C,E,B,B,D,A,C,E,E,D,E,A,E
,A,B,A,B,C,D,B,C,D,E,A,D,E,E,E,A,A,A,B,B,B,B,C,C,C,C,D,B,E,D,C,A,E,D,B,A,E,D,C,B,A,E,C,E,E,C,
A,A,D,B,B,E,C,A,C,A,D,B,D,C,E,B,D,A,C,E,B,D,A,C,C,E,B,D,A,A,E,A,B,A,B,C,B,C,D,E,C,D,E,A,B,E,
A,A,A,B,B,B,C,C,C,C,D,D,D,D,E,C,A,E,D,B,A,E,C,B,A,E,D,C,B,A,E,A,A,D,B,B,E,C,C,A,D,B,D,B,E,C,
A,D,A,C,E,B,D,A,C,E,B,D,D,A,C,E,B,B,A,B,C,B,C,D,C,D,E,A,D,E,A,B,D,E,A,B,C,A,B,E,A,B,C,D,A,B,
C,D,D,D,B,C,D,B,C,D,B,C,D,E,B,C,D,E,A,E,C,D,E,C,D,B,C,D,E,A,C,D,E,A,B,A,D,E,A,D,E,A,D,E,A,B,
D,E,A,C,C,B,D,A,B,E,A,B,E,A,B,C,E,A,B,C,D,C,E,D,C,E,B,C,A,A,A,B,E,D,C,B,D

[dimkadimon]

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

dimkadimon
откуда такая уверенность, что решение C5N26 существует?

Потому что можно раскрасить 26х26 с 138 единичками, а нужно всего 136.

[Nataly-Mak]

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

Потому что можно раскрасить 26х26 с 138 единичками, а нужно всего 136.

Ну и что? Как отсюда следует, что можно к этим 138 единичкам одного цвета залить ещё 4 цвета без конфликтов?

Ещё хотелось бы увидеть ответ по поводу не строго диагонального решения C5N26.
Вопрос задан чуть выше, приведена цитата из вашего давнего сообщения, где вы писали, что у вас не получилось построить такое решение.

[dimkadimon]

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

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

Потому что можно раскрасить 26х26 с 138 единичками, а нужно всего 136.

Ну и что? Как отсюда следует, что можно к этим 138 единичкам одного цвета залить ещё 4 цвета без конфликтов?

Ещё хотелось бы увидеть ответ по поводу не строго диагонального решения C5N26.
Вопрос задан чуть выше, приведена цитата из вашего давнего сообщения, где вы писали, что у вас не получилось построить такое решение.

Значит есть хороший шанс что 26х26 есть. Не строго диагональное C5N26 у меня не получилось, думаю его нет. Вот самый лучший результат с 54 ошибками:

(Оффтоп)

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

[Nataly-Mak]

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

Значит есть хороший шанс что 26х26 есть.

Если следовать вашей логике, то и для решения C5N27 есть хороший шанс, так как Tom Sirgedas нашёл заполнение квадрата 27х27 147 единичками, а надо 146 единичек
"Есть хороший шанс" ещё не означает полную уверенность в существовании этих решений.
Что-то они до сих пор не найдены, что даёт основание засомневаться в их существовании.
Однако и сомнения не могут означать, что решений точно не существует.

Цитата:

Не строго диагональное C5N26 у меня не получилось, думаю его нет.

Опять ваши предположения
Меня интересует точный ответ - существует или не существует?
Нужно выполнить полный перебор. Вы его выполнили?
Что значит "лучший результат"? Как получен этот лучший результат?

Вот я тоже могу привести некоторый "лучший результат". Этот результат найден по программе whitefox.
Программа выдала вектор длины 36 (нам нужен вектор длины 51 для построения полного решения):

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

В программе произошёл аварийный останов по непонятной причине, то есть полный перебор не выполнен.

По найденному вектору делаю раскраску:



И далее раскрашиваю сама то, что удаётся без ошибок:



Остались не раскрашены всего 7 диагоналей.

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

-- Вс сен 16, 2012 07:22:09 --

dimkadimon
в вашей раскраске С5N26 только 3 диагонали дают ошибки; вот убрала окраску этих диагоналей, и решение получилось без ошибок:



-- Вс сен 16, 2012 07:52:38 --

Ваше решение очень близко к строго диагональному решению, изменила цвет всего одной диагонали и получилось строго диагональное решение с 65 ошибками:



Но строго диагонального C5N26 решения точно не существует, поэтому это всего лишь некоторое приближение к этому решению. Однако очень хорошее приближение.

[Nataly-Mak]

Вот это не строго диагональное решение C3N9 я построила вручную, в нём 8 ошибок:



Для этого-то решения можно сделать полный перебор и дать точный ответ: существует или не сущуствует не строго диагональное решение.

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

Точно такая же ситуация для решений C4N16 и C5N25.

Может, есть желающие помочь?

[dimkadimon]

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

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

Значит есть хороший шанс что 26х26 есть.

Если следовать вашей логике, то и для решения C5N27 есть хороший шанс, так как Tom Sirgedas нашёл заполнение квадрата 27х27 147 единичками, а надо 146 единичек
"Есть хороший шанс" ещё не означает полную уверенность в существовании этих решений.
Что-то они до сих пор не найдены, что даёт основание засомневаться в их существовании.
Однако и сомнения не могут означать, что решений точно не существует.

Цитата:

Не строго диагональное C5N26 у меня не получилось, думаю его нет.

Опять ваши предположения
Меня интересует точный ответ - существует или не существует?
Нужно выполнить полный перебор. Вы его выполнили?
Что значит "лучший результат"? Как получен этот лучший результат?

Согласен C5N27 тоже может существовать, но больше шансов что C5N26 существует. На все ваши вопросы о существовании могу сказать только одно - я не знаю. Я не делал полного перебора. Я использовал метод отжига и искал все 51 диагонали (вместо 26ти). Не уверен что полный перебор возможен.

[Nataly-Mak]

Теперь понятен ответ
Ещё маленький вопросик:
вы все диагональные решения искали методом отжига?

[dimkadimon]

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

Теперь понятен ответ
Ещё маленький вопросик:
вы все диагональные решения искали методом отжига?

Да

[Nataly-Mak]

Ясно.

Сечас написала на скорую руку программку построения не строго диагональных решений C3N9 пока без проверки, выяснила, сколько кандидатов на не строго диагональное решение: 10374147.
Это программа посчитала мгновенно. Теперь надо каждого кандидата проверить
Это я писала программу для проверки в лоб. У меня нет программ для построения диагональных решений, я все их строила вручную.

Вот, например, кандидаты с 10000000 по 10000010, выданные программой:

(Оффтоп)

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 1 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 1 , 3 ,
 1 , 1 , 3 , 3 , 1 , 2 , 1 , 3 , 3 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 , 1 ,
 1 , 1 , 3 , 3 , 1 , 2 , 2 , 1 , 1 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 , 1 ,
 1 , 1 , 3 , 3 , 1 , 2 , 2 , 1 , 2 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 , 1 ,
 1 , 1 , 3 , 3 , 1 , 2 , 2 , 1 , 3 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 , 3 ,
 1 , 1 , 3 , 3 , 1 , 2 , 2 , 3 , 1 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 , 3 ,
 1 , 1 , 3 , 3 , 1 , 2 , 2 , 3 , 2 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 2 , 3 ,
 1 , 1 , 3 , 3 , 1 , 2 , 2 , 3 , 3 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 , 1 ,
 1 , 1 , 3 , 3 , 1 , 2 , 3 , 1 , 1 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 , 1 ,
 1 , 1 , 3 , 3 , 1 , 2 , 3 , 1 , 2 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 , 1 ,
 1 , 1 , 3 , 3 , 1 , 2 , 3 , 1 , 3 ,

9,9, 1 , 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 ,
 3 , 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 ,
 3 , 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 ,
 2 , 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 ,
 1 , 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 ,
 3 , 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 ,
 1 , 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 ,
 3 , 1 , 1 , 3 , 3 , 1 , 2 , 3 , 2 ,
 1 , 1 , 3 , 3 , 1 , 2 , 3 , 2 , 1 ,

Взяла одного из этих кандидатов и начала исправлять в программе Эда, получилось строго диагональное решение

[dimkadimon]

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

А что вы можете сказать по поводу не строго диагональных решений:

1. для $N=C^2$;
2. для $N>C^2$.

Я не могу найти не строго диагональные решения C3N9, C4N16, C5N25 и т.д.

Насчёт не строго диагональных решений. Я нашёл C3N9:

(Оффтоп)

2,1,1,3,2,1,2,3,3,
1,1,3,2,1,2,3,3,2,
1,3,2,1,2,3,3,2,3,
3,2,1,2,3,3,2,3,1,
2,1,2,3,3,2,3,1,1,
1,2,3,3,2,3,1,1,2,
2,3,3,2,3,1,1,2,1,
3,3,2,3,1,1,2,1,2,
3,2,3,1,1,2,1,2,3

Похоже что C3N10 не существует. Нашёл C4N15:

(Оффтоп)

4,1,1,4,3,4,3,1,2,4,3,3,2,2,1,
1,1,4,3,4,3,1,2,4,3,3,2,2,1,2,
1,4,3,4,3,1,2,4,3,3,2,2,1,2,4,
4,3,4,3,1,2,4,3,3,2,2,1,2,4,1,
3,4,3,1,2,4,3,3,2,2,1,2,4,1,1,
4,3,1,2,4,3,3,2,2,1,2,4,1,1,4,
3,1,2,4,3,3,2,2,1,2,4,1,1,4,3,
1,2,4,3,3,2,2,1,2,4,1,1,4,3,4,
2,4,3,3,2,2,1,2,4,1,1,4,3,4,3,
4,3,3,2,2,1,2,4,1,1,4,3,4,3,1,
3,3,2,2,1,2,4,1,1,4,3,4,3,1,2,
3,2,2,1,2,4,1,1,4,3,4,3,1,2,4,
2,2,1,2,4,1,1,4,3,4,3,1,2,4,3,
2,1,2,4,1,1,4,3,4,3,1,2,4,3,3,
1,2,4,1,1,4,3,4,3,1,2,4,3,3,2

Похоже что C4N16 не существует, хотя нашёл более 1000 строгих. Нашёл C5N24:

(Оффтоп)

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

Похоже что C5N25 не существует, хотя нашёл более 200 строгих. Нашёл C6N35:

(Оффтоп)

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

Возможно что есть и C6N36, но я их не нашёл. Для C=7 только смог найти N=41:

(Оффтоп)

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

Часто эти решения очень похожи на строго диагональные решения, только с небольшой модификацией.