Метод точных попарно ортогональных покрытий массива

[whitefox]

Someone в сообщении #1029330 писал(а):

В этом самом "online-решателе" наверняка можно указать, какие именно переменные Вы хотите выразить из системы.

Когда-то, давным-давно, пытался найти в сети подобный "решатель". Увы, ни один меня не устроил, пришлось писать свою программу (к сожалению, не сохранилась) . Возможно, сейчас ситуация улучшилась, не проверял.

[Dmitriy40]

Здесь задача сильно ограниченная (всё в целых числах, включая коэффициенты, все функции линейные) - потому написать программу для решения таких систем много-много проще универсального решателя. И в программе применить пусть даже не самый лучший алгоритм (Гаусса, не Гаусса), а просто любой рабочий - комп стерпит. Разобраться один раз и написать решатель, зато потом польза будет многократной.

PS. Специально отмечу, что "много-много проще" не означает что мне достаточно пары часов это написать и потому требовать с меня готовое решение в виде такой программы бессмысленно.

[Nataly-Mak]

Someone в сообщении #1029330 писал(а):

чего Вы мучаетесь. В этом самом "online-решателе" наверняка можно указать, какие именно переменные Вы хотите выразить из системы. Он Вам сразу и выдаст результат в требуемом виде.

Вы уверены, что в онлайн-решателе можно указать, какие переменные я хочу выразить?

Вот ссылка на онлайн-решатель, которым я пользуюсь:
http://wims.unice.fr/wims/en_tool~linea ... er.en.html

Эту ссылку мне дал совсем недавно 12d3. До этого я не знала ни одного онлайн-решателя систем линейных уравнений.

Итак, как я понимаю, задача оказалась совсем не так проста, как могло показаться.
whitefox сказал, что задачу можно решить только вручную, применив метод Гаусса.
Я на практической реализации вижу, что вариант этого метода (вроде то, что я сделала и есть в принципе то же самое, что и метод Гаусса) очень громоздкий и завёл меня в тупик.
whitefox утверждает, что никакого тупика быть не должно и что метод Гаусса всё это решит намного быстрее и легче.

whitefox
если это легко и быстро, может быть, продемонстрируете на моём конкретном примере?
(Нет, нет - не требую, как тут Dmitriy40 заволновался, что с него требовать будут; не имею никакого права от кого-то чего-то требовать; просто предлагаю продемонстрировать, как всё это просто и легко решить вручную методом Гаусса; может быть, в самом деле, легко и просто - для тех, кто умеет. Я не умею, увы.)

Далее утверждается, что с задачей элементарно может справиться и онлайн-решатель. Интересно!
Давайте попробуем.
Вот система линейных уравнений, которую мне надо решить:

x1+x2+x3+x4+x5+x6+x7+x8+x9=9k/2
x10+x11+x12+x13+x14+x15+x16+x17+x18=9k/2
x19+x20+x21+x22+x23+x24+x25+x26+x27=9k/2
x28+x29+x30+x31+x32+x33+x34+x35+x36=9k/2
x1+x10+x19+x28+x37-x36-x27-x18-x9=k/2
x2+x11+x20+x29+x38-x35-x26-x17-x8=k/2
x3+x12+x21+x30+x39-x34-x25-x16-x7=k/2
x4+x13+x22+x31+x40-x33-x24-x15-x6=k/2
x1+x18+x26+x34-x40-x32-x24-x16-x8=-k/2
x2+x10+x27+x35-x39-x31-x23-x15-x7=-k/2
x3+x11+x19+x36-x38-x30-x22-x14-x6=-k/2
x4+x12+x20+x28-x37-x29-x21-x13-x5=-k/2
x9+x10+x20+x30+x40-x32-x22-x12-x2=k/2
x8+x18+x19+x29+x39-x33-x23-x13-x3=k/2
x7+x17+x27+x28+x38-x34-x24-x14-x4=k/2
x6+x16+x26+x36+x37-x35-x25-x15-x5=k/2

Вот здесь в левых частях стоят переменные (16 штук), которые я хочу выразить, то есть это зависимые переменные. Это я переписала общую формулу (полученную в онлайн-решателе) вручную.

X(2)=-X(14)-X(32)-X(6)-X(16)-X(12)-X(22)+5K-X(24)-X(8)-X(4)
X(3)=-X(23)-X(32)-X(6)+X(34)+X(35)-X(16)-X(12)+X(18)+X(10)-X(2)-X(7)-X(22)+3K-X(24)-X(8)+X(29)+X(30)-X(4)
X(4)=X(21)-2X(32)-2X(6)+X(35)-X(36)+2X(10)+X(13)-2X(16)-X(12)-2X(7)+X(20)-2X(2)-X(22)+4K-X(24)-2X(8)+2X(30)+X(40)
X(6)=-X(11)-X(32)-X(34)+X(35)-2X(36)+2X(10)-X(16)-X(12)-2X(18)-X(7)+X(20)-2X(2)-X(22)+4K-X(26)-X(27)+X(28)-X(29)+2X(30)+2X(40)
X(7)=-X(17)-X(32)-X(6)-X(36)+X(10)-X(16)-X(12)-X(18)+X(20)-X(2)-X(22)+9K/2-X(8)-X(26)-X(27)+X(30)+X(40)
X(8)=X(1)-X(32)+X(34)-X(16)+X(18)+K/2-X(24)+X(26)-X(40)
X(10)=(-X(31)+X(32)+2X(6)-X(35)+X(36)-X(13)+X(16)+X(12)+X(18)+X(7)-X(20)+2X(2)+X(22)-2K+X(24)+X(8)+X(26)+X(27)-X(28)-2X(30)-2X(40))/2
X(12)=(-2X(33)-4X(32)-4X(6)-2X(34)-4X(36)+4X(10)+2X(13)-2X(16)-2X(18)-2X(7)+2X(20)-4X(2)-2X(22)+13K-2X(24)-2X(8)-2X(26)-2X(27)-2X(29)+2X(30)+4X(40))/2
X(13)=X(25)+X(32)+2X(6)+3X(34)-X(35)+3X(36)-4X(10)+X(16)+4X(18)+2X(7)-2X(20)-2X(3)+2X(2)+2X(22)-4K+3X(26)+2X(27)-2X(28)+2X(29)-3X(30)-X(4)-4X(40)
X(15)=3X(32)+3X(6)+X(34)-X(35)+3X(36)-4X(10)-X(13)+2X(16)+2X(12)+2X(18)+2X(7)-2X(20)+4X(2)+3X(22)-9K+X(24)+2X(8)+2X(26)+2X(27)-X(28)+X(29)-3X(30)+X(4)-3X(40)
X(16)=-X(37)-X(6)-X(34)+X(35)-X(36)+X(10)+X(12)-X(18)-X(7)+X(20)+X(3)-X(26)+X(28)-X(29)+X(30)+X(4)+X(40)
X(18)=X(38)-X(34)-X(36)+X(10)+X(20)-K-X(26)+X(28)+X(30)+X(40)
X(19) = -(-2*X(6)-4*X(34)+2*X(35)-4*X(36)+6*X(10)-6*X(18)-2*X(7)+4*X(20)+2*X(3) -2*X(2)-2*X(22)-3*K+2*X(24)+2*X(8)-4*X(26)-2*X(27)+4*X(28) -2*X(29)+4*X(30)+2*X(4)+6*X(40)) /2
X(20)=(2X(5)+4X(32)+2X(6)-2X(34)-2X(10)+2X(16)+2X(12)-2X(18)+2X(7)+2X(3)+4X(2)+2X(22)-9K+2X(24)+4X(8)-2X(26)-2X(30)+2X(4))/2
X(22)=(2X(9)-2X(32)+2X(10)-2X(12)+2X(20)-2X(2)-K+2X(30)+2X(40))/2
X(24)=(-2X(39)-6X(32)-8X(6)-4X(34)+4X(35)-8X(36)+12X(10)+4X(13)-4X(16)-4X(12)-8X(18)-6X(7)+6X(20)+2X(3)-8X(2)-6X(22)+17K-4X(8)-6X(26)-4X(27)+4X(28)-4X(29)+8X(30)+10X(40))/2

(не буду перечислять эти переменные, надеюсь, понятно; ещё: у меня в системе переменные записаны без скобок, а в формуле со скобками, надеюсь, это не мешает пониманию)

Свободных переменных должно быть 24 штуки из 40; это все те, которые не входят в список переменных, находящихся в левых частях. Константа ассоциативности квадрата k считается заданной, но её тоже можно считать переменной. Кстати, онлайн-решатель так и считает и иногда выдаёт решение, в котором k является зависимой переменной. Но в данном примере в решении k свободная переменная.

Когда я открываю онлайн-решатель, мне предлагают ввести систему уравнений в окно для ввода. Я ввожу систему и решатель её решает.
Где там можно указать зависимые переменные, я не видела. Подскажете

И это ещё не все пути решения задачи. Можно ещё и написать программу, как тут пишут.
Ну, что можно написать программу, которая решает систему, - это вроде и ёжику понятно.
Онлайн-решатель и есть такая программа.

Написать программу "много-много проще", как утверждает Dmitriy40.
Наверное, это так. Я не знаю. Программу такую писать не умею. Если бы умела, темы этой не было бы.

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

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

-- Пн июн 22, 2015 06:25:32 --

Может быть, в онлайн-решатель надо ввести систему уравнений вот в этом виде:

X(2)=-X(14)-X(32)-X(6)-X(16)-X(12)-X(22)+5K-X(24)-X(8)-X(4)
X(3)=-X(23)-X(32)-X(6)+X(34)+X(35)-X(16)-X(12)+X(18)+X(10)-X(2)-X(7)-X(22)+3K-X(24)-X(8)+X(29)+X(30)-X(4)
X(4)=X(21)-2X(32)-2X(6)+X(35)-X(36)+2X(10)+X(13)-2X(16)-X(12)-2X(7)+X(20)-2X(2)-X(22)+4K-X(24)-2X(8)+2X(30)+X(40)
X(6)=-X(11)-X(32)-X(34)+X(35)-2X(36)+2X(10)-X(16)-X(12)-2X(18)-X(7)+X(20)-2X(2)-X(22)+4K-X(26)-X(27)+X(28)-X(29)+2X(30)+2X(40)
X(7)=-X(17)-X(32)-X(6)-X(36)+X(10)-X(16)-X(12)-X(18)+X(20)-X(2)-X(22)+9K/2-X(8)-X(26)-X(27)+X(30)+X(40)
X(8)=X(1)-X(32)+X(34)-X(16)+X(18)+K/2-X(24)+X(26)-X(40)
X(10)=(-X(31)+X(32)+2X(6)-X(35)+X(36)-X(13)+X(16)+X(12)+X(18)+X(7)-X(20)+2X(2)+X(22)-2K+X(24)+X(8)+X(26)+X(27)-X(28)-2X(30)-2X(40))/2
X(12)=(-2X(33)-4X(32)-4X(6)-2X(34)-4X(36)+4X(10)+2X(13)-2X(16)-2X(18)-2X(7)+2X(20)-4X(2)-2X(22)+13K-2X(24)-2X(8)-2X(26)-2X(27)-2X(29)+2X(30)+4X(40))/2
X(13)=X(25)+X(32)+2X(6)+3X(34)-X(35)+3X(36)-4X(10)+X(16)+4X(18)+2X(7)-2X(20)-2X(3)+2X(2)+2X(22)-4K+3X(26)+2X(27)-2X(28)+2X(29)-3X(30)-X(4)-4X(40)
X(15)=3X(32)+3X(6)+X(34)-X(35)+3X(36)-4X(10)-X(13)+2X(16)+2X(12)+2X(18)+2X(7)-2X(20)+4X(2)+3X(22)-9K+X(24)+2X(8)+2X(26)+2X(27)-X(28)+X(29)-3X(30)+X(4)-3X(40)
X(16)=-X(37)-X(6)-X(34)+X(35)-X(36)+X(10)+X(12)-X(18)-X(7)+X(20)+X(3)-X(26)+X(28)-X(29)+X(30)+X(4)+X(40)
X(18)=X(38)-X(34)-X(36)+X(10)+X(20)-K-X(26)+X(28)+X(30)+X(40)
X(19) = -(-2*X(6)-4*X(34)+2*X(35)-4*X(36)+6*X(10)-6*X(18)-2*X(7)+4*X(20)+2*X(3) -2*X(2)-2*X(22)-3*K+2*X(24)+2*X(8)-4*X(26)-2*X(27)+4*X(28) -2*X(29)+4*X(30)+2*X(4)+6*X(40)) /2
X(20)=(2X(5)+4X(32)+2X(6)-2X(34)-2X(10)+2X(16)+2X(12)-2X(18)+2X(7)+2X(3)+4X(2)+2X(22)-9K+2X(24)+4X(8)-2X(26)-2X(30)+2X(4))/2
X(22)=(2X(9)-2X(32)+2X(10)-2X(12)+2X(20)-2X(2)-K+2X(30)+2X(40))/2
X(24)=(-2X(39)-6X(32)-8X(6)-4X(34)+4X(35)-8X(36)+12X(10)+4X(13)-4X(16)-4X(12)-8X(18)-6X(7)+6X(20)+2X(3)-8X(2)-6X(22)+17K-4X(8)-6X(26)-4X(27)+4X(28)-4X(29)+8X(30)+10X(40))/2

И тогда он поймёт, что выражать надо те переменные, которые стоят слева?
Это так - мысли вслух

-- Пн июн 22, 2015 06:39:12 --

Мысль опробовала. Увы! Решатель систему решил, решение выдал, но оно не такое, как мне нужно, то есть переменные не те выражаются (выражаются те переменные, что и раньше выражались; понятно, программа там одна и та же и решает она одинаково - в каком виде систему ни дай).

Вот решение:

{k = r3, x1 = -(-6 r9+4 r8-4 r6-8 r5+2 r4+21 r3+12 r25-6 r24-4 r23 +8 r22-6 r21-8 r20-14 r2+4 r19+6 r18+2 r17-12 r16 +2 r15-4 r14+4 r13-12 r12-8 r11+4 r10+2 r1) /8, x10 = r25, x11 = -(2 r9-4 r5+2 r4+ r3+4 r25-2 r24-2 r21-2 r2+4 r19+2 r18 +2 r17-4 r16-2 r15+2 r1) /4, x12 = r6, x13 = r19, x14 = (2 r9-4 r7+2 r4+ r3-4 r25+2 r24-4 r22+2 r21+4 r20+2 r2 -2 r18-2 r17+2 r15+4 r14+4 r11+2 r1) /4, x15 = r7, x16 = r12, x17 = -(2 r9-4 r8+4 r6+2 r4-19 r3+4 r25+2 r24-4 r23+2 r21 +2 r2+4 r19-2 r18+2 r17+4 r16+2 r15+4 r14+4 r13 +4 r12+4 r10+2 r1) /8, x18 = (2 r9-4 r8-4 r6-8 r5+2 r4+17 r3+12 r25-6 r24-4 r23 +8 r22-6 r21-8 r20-6 r2+4 r19+6 r18+10 r17-4 r16 -6 r15-4 r14+4 r13-4 r12-8 r11+4 r10+2 r1) /8, x19 = (10 r9+4 r8-8 r7-4 r6-8 r5+2 r4+25 r3+4 r25-6 r24-4 r23 +2 r21-6 r2+12 r19-2 r18+2 r17-12 r16+2 r15+4 r14 -4 r13-4 r12+4 r10+10 r1) /8, x2 = r11, x20 = r18, x21 = -(2 r9-4 r7-4 r5+2 r4-3 r3+4 r25-6 r24+4 r22+2 r21-2 r2 +4 r19+2 r18+2 r17-4 r16+2 r15+4 r14-4 r12+4 r10 +2 r1) /4, x22 = r21, x23 = (6 r9+4 r8-8 r7-4 r6-8 r5-2 r4+3 r3+12 r25-10 r24+4 r23 +8 r22-2 r21-2 r2+4 r19+2 r18+6 r17-4 r16-2 r15 +4 r14+4 r13-4 r12+12 r10+6 r1) /8, x24 = r9, x25 = -(10 r9+4 r8-4 r7-4 r6-4 r5-2 r4- r3+4 r25-2 r24+2 r21 -2 r2+4 r19+2 r18+2 r17-4 r16+2 r15+4 r14+4 r10 +6 r1) /4, x26 = r15, x27 = r14, x28 = r13, x29 = r23, x3 = r4, x30 = r22, x31 = (10 r9-4 r8+4 r6+8 r5+2 r4+ r3-4 r25+2 r24-4 r23-8 r22 +2 r21+2 r2-4 r19-2 r18-6 r17+4 r16+2 r15+4 r14 -4 r13+4 r12+8 r11-4 r10+2 r1) /8, x32 = r2, x33 = -(10 r9+4 r8+4 r6+8 r5+2 r4-35 r3-4 r25+2 r24+4 r23 +2 r21+8 r20+10 r2-4 r19-2 r18-6 r17+4 r16+2 r15 +4 r14+4 r13+4 r12+8 r11+4 r10+2 r1) /8, x34 = r8, x35 = r10, x36 = r20, x37 = -(14 r9+4 r8-8 r7-4 r6+8 r5-2 r4-21 r3-4 r25+6 r24 +4 r23-8 r22+6 r21+8 r20+6 r2+4 r19-6 r18-2 r17 +4 r16+6 r15+4 r14-4 r13+12 r12+8 r11-4 r10+6 r1) /8, x38 = (2 r9+4 r8-4 r6-8 r5+2 r4+25 r3+4 r25-6 r24-4 r23-6 r21 -6 r2+4 r19-2 r18+2 r17-4 r16+2 r15-4 r14-4 r13 -4 r12-8 r11+4 r10+2 r1) /8, x39 = r1, x4 = -(6 r9-4 r7+4 r6+4 r5+2 r4-19 r3-4 r25+2 r24-4 r22+6 r21 +4 r20+6 r2-2 r18-2 r17+4 r16+2 r15+4 r14+4 r12 +8 r11+2 r1) /4, x40 = r17, x5 = (6 r9+4 r8-8 r7-4 r6-8 r5-2 r4+15 r3+12 r25-10 r24-4 r23 +8 r22-2 r21-10 r2+4 r19+10 r18+6 r17-12 r16+6 r15 +4 r14+4 r13-4 r12-8 r11+4 r10+6 r1) /8, x6 = r5, x7 = r24, x8 = r16, x9 = (2 r6+ r3-2 r25-2 r22+2 r21+2 r2-2 r18-2 r17+2 r11)/2 }

В решателе написано о некоторых методах, которые, как я понимаю, можно использовать:

Цитата:

This application solves your linear systems. You may enter your system by one of the 3 methods:
• integral method (type equations in one block),
• matrix method (enter the coefficient matrix and the column of constants),
• individual method (type coefficients one by one).
The menu is actually under integral method. Click on the above links to change the method.

Что это за методы? Среди них нет того, который нам нужен, - с указанием списка зависимых переменных?

-- Пн июн 22, 2015 06:55:30 --

Ещё вариант: а матпакеты не умеют такую задачу решать?
Решить систему уравнений они, разумеется, могут.
Но нам надо не просто её решить, а решить относительно конкретных 16-ти переменных.
Вот так можно решить в матпакете?

[Nataly-Mak]

На всякий случай перечислю переменные, оносительно которых надо решить систему:

X2, X3, X4, X6, X7, X8, X10, X12, X13, X15, X16, X18, X19, X20, X22, X24

Это 16 зависимых переменных, остальные 24 (из 40 Xi) будут свободными.
Константа ассоциативности квадрата k тоже свободная.

[whitefox]

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

Вот ссылка на онлайн-решатель, которым я пользуюсь: http://wims.unice.fr/wims/en_tool~linea ... er.en.html

Спасибо за ссылку, солвер отличный
И свободные переменные в нём можно задать:

Цитата:

Remarks.

You may put parameters into your system. In this case, please give the names of your parameters here, so that they will not be taken to be variables:

(Separate the names by commas.)

Например, решим следующую систему относительно свободной переменной $x_1.$
Ввод:

Вложение:

Screenshot_4.png [ 10.13 Кб | Просмотров: 2320 ]

Красным обведён ответ на вопрос:

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

Где там можно указать зависимые переменные, я не видела. Подскажете

Только вводить надо не зависимые, а свободные переменные через запятую.

Вывод:

Вложение:

Screenshot_5.png [ 4.73 Кб | Просмотров: 2324 ]

-- 22 июн 2015, 08:50 --

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

Итак, как я понимаю, задача оказалась совсем не так проста, как могло показаться.
whitefox сказал, что задачу можно решить только вручную, применив метод Гаусса.
Я на практической реализации вижу, что вариант этого метода (вроде то, что я сделала и есть в принципе то же самое, что и метод Гаусса) очень громоздкий и завёл меня в тупик.
whitefox утверждает, что никакого тупика быть не должно и что метод Гаусса всё это решит намного быстрее и легче.

Ваш метод решает задачу тройным вложенным циклом, то есть его сложность $O(n^3),$ а метод Гаусса использует только двойной вложенный цикл и потому его сложность $O(n^2).$

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

whitefox
если это легко и быстро, может быть, продемонстрируете на моём конкретном примере?
(Нет, нет - не требую, как тут Dmitriy40 заволновался, что с него требовать будут; не имею никакого права от кого-то чего-то требовать; просто предлагаю продемонстрировать, как всё это просто и легко решить вручную методом Гаусса; может быть, в самом деле, легко и просто - для тех, кто умеет. Я не умею, увы.)

Оценка сложности показывает, что метод Гаусса в $n$ раз легче Вашего метода, что при ручном решении очень существенно. Но для больших систем он тоже утомителен, $O(n^2)$ всё таки.

[Nataly-Mak]

whitefox
большое спасибо за подсказки.
Сейчас вернулась из поездки в центр города; немного мозги остынут (у нас +35 в тени), буду пробовать.

-- Пн июн 22, 2015 14:43:36 --

whitefox в сообщении #1029260 писал(а):

Разумеется, обычные онлайн-солверы для подобного не предусмотрены. Нужно решать вручную.

Оказывается, вы немного отстали от жизни

[whitefox]

На оговорку "обычные" внимание обратили?
Я всегда могу сослаться на то, что данный солвер "не обычный".

Но таки, да, отстал.

[Nataly-Mak]

Ура! Кажется, получилось!

x10 = (x5-2x37+x32+x31+2x25+x23+x21-x14-x11-x1-k+2 r7-2 r6-2 r5 +2 r3+2 r2) /2 
x12 = r1 
x13 = -(x5+x40-x39-x37+x32+x31+2x25+x23+x21+x17-x1-6k+2 r7-2 r6 +2 r3+2 r2) /2 
x15 = -(x5+x40-x39-x38-3x37+x32+2x25-x23-2x21-x14+2x11-2x1+6k -4 r8-4 r6-2 r4-2 r3+2 r2) /2 
x16 = r5 
x18 = (x5+2x40-2x39-x38-2x37+x32+2x25-x23-2x21-x17-2x14+x11-2x1 +10k-4 r8-4 r6-2 r4-2 r3+2 r2-2 r1) /2 
x19 = (x9+x38+x33-x25+x14-x11-2k+2 r6+2 r4)/2 
x2 = -(x5-2x39-2x37+x32-x31+2x25-x23-x21-x14+x11-x1+2k-2 r8+2 r7 -2 r6-2 r4+2 r2) /2 
x20 = -x9-x5-x40+x39+2x37-2x25+x14+x1+ r8-2 r7+2 r6+ r5-2 r2+ r1 
x22 = r3 
x24 = (x9+2x5+2x40-2x39-x38-4x37-x33+3x25-2x23-2x21-3x14+x11 -2x1+11k-4 r8+2 r7-6 r6-2 r5-2 r4-2 r3+4 r2-2 r1) /2 
x26 = r8 
x27 = r7 
x28 = (x9+x5+x40-x39-x38-x37-x33-x32-x31+x25-x23-x21-x17-x14+x11-x1+9k -2 r8-2 r6-2 r4-2 r3-2 r1) /2 
x29 = -(2x39+x38+2x37+x31-2x25+x21-x17+x14+x1-4k-2 r7+2 r6+2 r4 -2 r2) /2 
x3 = -(x9+x5-x40+x39+x37+x33-x32-x25+x23+2x21-x11+2x1-6k+2 r8+2 r6 -2 r5+2 r4) /2 
x30 = r4 
x34 = -(x9+2x5-2x39-x38-2x37+x33+3x25-x14-x11-k+2 r7-2 r6-2 r5 +4 r2-2 r1) /2 
x35 = r2 
x36 = (x5-x40+x39+x38+x37-x32+x23+2x21+x14-2x11+2x1-5k+2 r8+2 r6 -2 r5+2 r4+2 r3) /2 
x4 = (x9+2x5-2x39-2x37+x33-x31+3x25+x21+x17-2x14-x11-x1+4 r7 -2 r6-2 r5+4 r2-2 r1) /2 
x6 = r6 
x7 = (x5+x40-x39-x38-3x37+x32+2x25-x23-x14-2x1+4k-2 r8+2 r7-4 r6 -2 r5+4 r2) /2 
x8 = -(2x9+3x5+2x40-2x39-x38-4x37+x32+4x25-x23+x17-2x14-x11-2x1 -k-2 r8+4 r7-4 r6-2 r5+6 r2-2 r1) /2

Ещё не проверила.
Да, воспользовалась советом 12d3 на форуме ПЕН, что вводить не обязательно все свободные переменные.
Ввела только те, что лежат у меня на 4-х цепочках (это 16 штук) плюс константу ассоциативности k.
Остальные 8 свободных переменных решатель выбрал сам.

Сейчас приведу к привычному виду и проверю.

[Nataly-Mak]

Итак, альтернативная общая формула идеального квадрата 9-го порядка, позволяющая "посадить" квадрат на 4 цепочки, содержащие центральный элемент:

x(10)= (x(5)-2*x(37)+x(32)+x(31)+2*x(25)+x(23)+x(21)-x(14)-x(11)-x(1)-k+2*x(27)-2*x(6)-2*x(16)+2*x(22)+2*x(35))/2
x(13)= -(x(5)+x(40)-x(39)-x(37)+x(32)+x(31)+2*x(25)+x(23)+x(21)+x(17)-x(1)-6*k+2*x(27)-2*x(6)+2*x(22)+2*x(35))/2
x(15)= -(x(5)+x(40)-x(39)-x(38)-3*x(37)+x(32)+2*x(25)-x(23)-2*x(21)-x(14)+2*x(11)-2*x(1)+6*k -4*x(26)-4*x(6)-2*x(30)-2*x(22)+2*x(35)) /2
x(18)= (x(5)+2*x(40)-2*x(39)-x(38)-2*x(37)+x(32)+2*x(25)-x(23)-2*x(21)-x(17)-2*x(14)+x(11)-2*x(1 )+10*k-4*x(26)-4*x(6)-2*x(30)-2*x(22)+2*x(35)-2*x(12)) /2
x(19)= (x(9)+x(38)+x(33)-x(25)+x(14)-x(11)-2*k+2*x(6)+2*x(30))/2
x(2)= -(x(5)-2*x(39)-2*x(37)+x(32)-x(31)+2*x(25)-x(23)-x(21)-x(14)+x(11)-x(1)+2*k-2*x(26)+2*x(27 )-2*x(6)-2*x(30)+2*x(35)) /2
x(20)= -x(9)-x(5)-x(40)+x(39)+2*x(37)-2*x(25)+x(14)+x(1)+ x(26)-2*x(27)+2*x(6)+ x(16)-2*x(35)+ x(12)
x(24)= (x(9)+2*x(5)+2*x(40)-2*x(39)-x(38)-4*x(37)-x(33)+3*x(25)-2*x(23)-2*x(21)-3*x(14)+x(11 )-2*x(1)+11*k-4*x(26)+2*x(27)-6*x(6)-2*x(16)-2*x(30)-2*x(22)+4*x(35)-2*x(12)) /2
x(28)= (x(9)+x(5)+x(40)-x(39)-x(38)-x(37)-x(33)-x(32)-x(31)+x(25)-x(23)-x(21)-x(17)-x(14)+x(11)-x(1)+9*k-2*x(26)-2*x(6)-2*x(30)-2*x(22)-2*x(12)) /2
x(29)= -(2*x(39)+x(38)+2*x(37)+x(31)-2*x(25)+x(21)-x(17)+x(14)+x(1)-4*k-2*x(27)+2*x(6)+2*x(30 )-2*x(35))/2
x(3)= -(x(9)+x(5)-x(40)+x(39)+x(37)+x(33)-x(32)-x(25)+x(23)+2*x(21)-x(11)+2*x(1)-6*k+2*x(26)+2*x(6 )-2*x(16)+2*x(30)) /2
x(34)= -(x(9)+2*x(5)-2*x(39)-x(38)-2*x(37)+x(33)+3*x(25)-x(14)-x(11)-k+2*x(27)-2*x(6)-2*x(16)+4*x(35)-2*x(12)) /2
x(36)= (x(5)-x(40)+x(39)+x(38)+x(37)-x(32)+x(23)+2*x(21)+x(14)-2*x(11)+2*x(1)-5*k+2*x(26)+2*x(6 )-2*x(16)+2*x(30)+2*x(22)) /2
x(4)= (x(9)+2*x(5)-2*x(39)-2*x(37)+x(33)-x(31)+3*x(25)+x(21)+x(17)-2*x(14)-x(11)-x(1)+4*x(27)-2*x(6)-2*x(16)+4*x(35)-2*x(12)) /2
x(7)= (x(5)+x(40)-x(39)-x(38)-3*x(37)+x(32)+2*x(25)-x(23)-x(14)-2*x(1)+4*k-2*x(26)+2*x(27)-4*x(6 )-2*x(16)+4*x(35)) /2
x(8)= -(2*x(9)+3*x(5)+2*x(40)-2*x(39)-x(38)-4*x(37)+x(32)+4*x(25)-x(23)+x(17)-2*x(14)-x(11)-2*x(1 )-k-2*x(26)+4*x(27)-4*x(6)-2*x(16)+6*x(35)-2*x(12)) /2

Схема квадрата такая:



В зелёных ячейках расположены свободные элементы.
Не знаю пока, насколько эффективной окажется эта формула. Надо экспериментировать.
Формулу проверила на конкретном решении.

Спасибо всем!

whitefox
а метод точных попарно ортогональных покрытий ещё впереди. Всё это только отдалённые подходы к нему.
У вас ещё осталось желание мне помогать?

[Someone]

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

Вы уверены, что в онлайн-решателе можно указать, какие переменные я хочу выразить?

Там же написано:

Linear solver писал(а):

You may put parameters into your system. In this case, please give the names of your parameters here, so that they will not be taken to be variables:

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

-- Пн июн 22, 2015 17:57:21 --

Упс! Уже объяснили. Ну и хорошо.

[Nataly-Mak]

Это моё лучшее решение по идеальным квадратам 9-го порядка из различных простых чисел:

2843 149 1973 2039 971 1031 2141 293 1619
2063 563 1811 113 2549 1601 2633 1721 5
2393 503 1613 2381 1193 41 2411 101 2423
173 2711 2879 773 1583 1493 461 443 2543
569 83 821 311 1451 2591 2081 2819 2333
359 2459 2441 1409 1319 2129 23 191 2729
479 2801 491 2861 1709 521 1289 2399 509
2897 1181 269 1301 353 2789 1091 2339 839
1283 2609 761 1871 1931 863 929 2753 59

$K=2902$, $S=13059$

Сейчас напишу программу по новой формуле и на этом решении её протестирую.
Замечу, что это решение и по первой общей формуле было получено очень быстро. Правда, к формуле был добавлен ещё удачный шаблон.

А вот минимальное решение с магической константой $S=12249$ пока никак получить не удаётся.
Буду пробовать по новой формуле.
Может быть, оно и не существует, но это ещё надо доказать.

[Nataly-Mak]

Программу написала и протестировала. Всё работает замечательно.

Теперь беру вот это приближение к решению с магической константой $S=12249$ с 4 дырками:

2699 281 809 1499 479 2633 389 911 2549
59 1571 2129 1493 2339 659 1613 2273 113
2591 1289 1901 191 1013 11 2693 101 2459
683 2069 1559 2411 2003 1439 773 743 569
1019* 179 431* 509 1361 2213 2291* 2543 1703*
2153 1979 1949 1283 719 311 1163 653 2039
263 2621 29 2711 1709 2531 821 1433 131
2609 449 1109 2063 383 1229 593 1151 2663
173 1811 2333 89 2243 1223 1913 2441 23

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

2699  2063  59  1109  479  89  2609  593  2549 
2711  1571  2039  389  2339  0  653  2273  0 
569  0  1901  743  1013  0  2693  1433  1559 
0  1619  2081  2411  2003  1439  263  131  0 
911  179  1499  509  1361  2213  1223  2543  1811 
0  2591  2459  1283  719  311  641  1103  0 
1163  1289  29  0  1709  1979  821  0  2153 
0  449  2069  0  383  2333  683  1151  11 
173  2129  113  2633  2243  1613  2663  659  23 

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

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

Получится ли полное решение? А чёрт его знает! Остаётся крутить и крутить программу.
Приближений у меня много. Каждое из них можно обрабатывать этой программой.
Если решение существует, то где-нибудь оно обязательно выпрыгнет.

[Nataly-Mak]

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

[Nataly-Mak]

И ещё один эксперимент обработки приближения к решению новой программой.
Беру приближение для магической константы $S=13023$ с двумя дырками:

2851 211 2143 421 1657 1063 1723 2221 733
97 2767 1327 523 2857 757 2791 883 1021
373 2293 2347 2287 1153 1231 1861 181 1297
1987 1201 2203 1423 61 163 811 2617 2557
1747* 877 613 7 1447 2887 2281 2017 1147*
337 277 2083 2731 2833 1471 691 1693 907
1597 2713 1033 1663 1741 607 547 601 2521
1873 2011 103 2137 37 2371 1567 127 2797
2161 673 1171 1831 1237 2473 751 2683 43

Ввожу данные в программу, за несколько минут находится решение, в котором не вычислены всего 5 элементов; с этого момента начинается торможение.
Полный перебор будет на 2-3 часа (может быть, и больше, так как здесь массив чисел больше, чем для магической константы 12249); прерываю.

2851 601 1663 1171 1657 1063 613 2671 733 
97 2767 103 1777 2857 1093 2137 883 0 
643 0 2347 1597 1153 0 1861 277 2437 
0 907 2473 1423 61 163 1201 373 0 
607 877 673 7 1447 2887 2221 2017 2287 
0 2521 1693 2731 2833 1471 421 1987 0 
457 2617 1033 0 1741 1297 547 0 2251 
0 2011 757 1801 37 1117 2791 127 2797 
2161 223 2281 1831 1237 1723 1231 2293 43

[Nataly-Mak]

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

Хорошо, завтра на свежую голову возьму первые 16 чисел массива и попробую из них составить все "живые" наборы по 4 цепочки.

Не забыла про этот эксперимент
Вот сейчас написала программку составления наборов цепочек из заданных 16 чисел и убедилась в правильности приведённой здесь формулы для количества наборов таких цепочек.
В программе заложила вывод первых 5 наборов цепочек, а потом программа только все их посчитала. Вот результат работы программы:

11  23  29  59  1361  2711  2699  2693  2663 
89  101  113  131  1361  2633  2621  2609  2591 
173  179  191  263  1361  2549  2543  2531  2459 
281  311  383  389  1361  2441  2411  2339  2333 

11  23  29  59  1361  2711  2699  2693  2663 
89  101  113  131  1361  2633  2621  2609  2591 
173  179  191  281  1361  2549  2543  2531  2441 
263  311  383  389  1361  2459  2411  2339  2333 

11  23  29  59  1361  2711  2699  2693  2663 
89  101  113  131  1361  2633  2621  2609  2591 
173  179  191  311  1361  2549  2543  2531  2411 
263  281  383  389  1361  2459  2441  2339  2333 

11  23  29  59  1361  2711  2699  2693  2663 
89  101  113  131  1361  2633  2621  2609  2591 
173  179  191  383  1361  2549  2543  2531  2339 
263  281  311  389  1361  2459  2441  2411  2333 

11  23  29  59  1361  2711  2699  2693  2663 
89  101  113  131  1361  2633  2621  2609  2591 
173  179  191  389  1361  2549  2543  2531  2333 
263  281  311  383  1361  2459  2441  2411  2339 

KOLICHESTVO NABOROV CEPOCHEK 63063000

Чудесно

Идём дальше в методе точных ортогональных покрытий массива. Массив у нас задан и состоит из 81 простых чисел (он приведён в начале темы).

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

Пример

1289 2213 2039 1163 1571 311 1283 1811 569
383 2243 1619 2693 2063 593 773 653 1229
2003 1499 641 1979 821 809 89 1709 2699
131 263 1613 173 2333 2531 2441 2663 101
11 113 179 449 1361 2273 2543 2609 2711
2621 59 281 191 389 2549 1109 2459 2591
23 1013 2633 1913 1901 743 2081 1223 719
1493 2069 1949 2129 659 29 1103 479 2339
2153 911 1439 2411 1151 1559 683 509 1433