О-о-о! Вспомнила, что другой товарищ прислал в сообщении ссылку на код программы.
Программа делает перестановку всех симметричных строк/столбцов в ассоциативном квадрате 10-го порядка с последующей проверкой полученных вариантов квадрата на пандиагональность.
Кажется, это Паскаль (?) И, насколько понимаю, программа написана для любого порядка квадрата N.
(Оффтоп)
Код:
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <set>
#include <stack>
typedef std::vector<int> Vec;
typedef std::set<Vec> Set;
typedef std::stack<Vec> Stack;
int N;
int S;
Set set;
Stack stack;
Vec best;
int best_n = 0;
void print_best(std::ostream &stream)
{
stream << best_n << std::endl;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
stream << best[i * N + j] << " ";
}
stream << std::endl;
}
}
void check(const Vec &square)
{
int num = 0;
for (int i = 0; i < N; ++i)
{
int sum1 = 0;
int sum2 = 0;
for (int j = 0; j < N; ++j)
{
int x = j + i;
if (x >= N)
{
x-= N;
}
sum1 += square[j * N + x];
sum2 += square[(N - j - 1) * N + x];
}
if (sum1 == S)
{
++num;
}
if (sum2 == S)
{
++num;
}
}
if (num > best_n)
{
best = square;
best_n = num;
}
}
void insert(const Vec &vec)
{
for (int i = N / 2; i < N; ++i)
{
if (vec[i] == 0) return;
}
if (set.insert(vec).second)
{
stack.push(vec);
}
}
void swap(Vec vec, int i, int j)
{
int t = vec[i];
vec[i] = vec[j];
vec[j] = t;
if (j != N - i - 1)
{
i = N - i - 1;
j = N - j - 1;
t = vec[i];
vec[i] = vec[j];
vec[j] = t;
}
insert(vec);
}
void process(const Vec &vec)
{
for (int i = 0; i < N / 2; ++i)
for (int j = i + 1; j < N; ++j)
swap(vec, i, j);
}
int main(int argc, char *argv[])
{
const char *in_name;
if (argc >= 2)
in_name = argv[1];
else
in_name = "in.txt";
const char *out_name;
if (argc >= 3)
out_name = argv[2];
else
out_name = "out.txt";
std::ifstream in(in_name);
std::ofstream out(out_name);
Vec square;
int v;
while (in >> v)
{
square.push_back(v);
}
N = sqrt(square.size());
S = 0;
for (int i = 0; i < N; ++i)
{
S += square[i];
}
Vec vec(N);
for (int i = 0; i < N; ++i)
{
vec[i] = i;
}
insert(vec);
while (!stack.empty())
{
vec = stack.top();
stack.pop();
process(vec);
}
std::vector<Vec> vecs;
for (Vec vec : set)
{
vecs.push_back(vec);
}
int Z = vecs.size();
std::cout << "N=" << N << ", S=" << S << ", Z=" << Z << std::endl;
Vec test(N * N);
int count = 0;
int total = Z * Z;
for (int r = 0; r < Z; r++)
for (int c = 0; c < Z; c++)
{
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
test[i * N + j] = square[vecs[r][i] * N + vecs[c][j]];
check(test);
if (++count % 100000 == 0)
{
std::cout << count << " / " << total << " (" << count * 100 / total << "%), best: " << best_n << std::endl;
}
}
print_best(std::cout);
print_best(out);
return 0;
}
Там же есть и исполняемая программа.
Если я всё правильно поняла, то программа сейчас мигом проверит все мои ассоциативные квадраты 9-го порядка
и предъявит идеальный квадрат.
Ушла проверять.
-- Пт июл 03, 2015 19:34:25 --Результат проверки первого ассоциативного квадрата:
Код:
6
479 2459 11 2531 1499 311 2621 389 1949
1433 1709 131 1901 1493 641 2609 719 1613
683 2069 173 2201 1571 383 2699 659 1811
743 2273 29 2543 1163 89 2663 593 2153
1283 1883 281 2213 1361 509 2441 839 1439
569 2129 59 2633 1559 179 2693 449 1979
911 2063 23 2339 1151 521 2549 653 2039
1109 2003 113 2081 1229 821 2591 1013 1289
773 2333 101 2411 1223 191 2711 263 2243
Всего 6 правильных диагоналей! До идеального квадрата очень далеко.
Сильно подозреваю, что и остальные 5 ассоциативных квадратов дадут примерно такой же результат.
Но... не буду забегать вперёд. Проверю.
-- Пт июл 03, 2015 19:43:13 --Ох, не то пока. Я ввела в качестве исходного квадрата не квадрат, а первое точное покрытие.
Снова ушла проверять первый ассоциативный квадрат
может, сейчас лучше получится.
-- Пт июл 03, 2015 19:55:36 --Да! Ура!
Вот он - идеальный квадрат, полученный из первого же ассоциативного квадрата:
Код:
18
2531 2621 1499 11 1949 311 479 2459 389
59 449 1979 2129 179 1559 2633 569 2693
683 2069 1571 173 383 1811 2201 2699 659
1709 641 2609 1901 1433 1613 1493 131 719
839 1439 509 2441 1361 281 2213 1283 1883
2003 2591 1229 1109 1289 821 113 2081 1013
2063 23 521 911 2339 2549 1151 653 2039
29 2153 89 1163 2543 593 743 2273 2663
2333 263 2243 2411 773 2711 1223 101 191
,
Proggerау
большое спасибо за программу. Вот и пригодилась
Только... почему-то очень много вариантов программа проверяет и работает у меня минут 5.
Ну ладно, главное - работает.
А сейчас возьму известный минимальный ассоциативный квадрат с магической константой
и проверю его. Очень интересно, что он даст!
-- Пт июл 03, 2015 20:13:13 --Ввела в программу известный минимальный ассоциативный квадрат 9-го порядка из различных простых чисел:
Код:
1283 311 1811 2213 1571 569 2039 1163 1289
773 653 2243 1619 2063 593 2693 383 1229
1979 1499 2699 641 821 89 809 2003 1709
1613 2531 101 131 2333 2441 2663 263 173
113 179 2711 449 1361 2273 11 2543 2609
2549 2459 59 281 389 2591 2621 191 1109
1013 719 1913 2633 1901 2081 23 1223 743
1493 2339 29 2129 659 1103 479 2069 1949
1433 1559 683 2153 1151 509 911 2411 1439
,
Результат проверки этого квадрата:
Код:
6
1619 773 2243 653 2063 383 2693 1229 593
2213 1283 1811 311 1571 1163 2039 1289 569
131 1613 101 2531 2333 263 2663 173 2441
641 1979 2699 1499 821 2003 809 1709 89
449 113 2711 179 1361 2543 11 2609 2273
2633 1013 1913 719 1901 1223 23 743 2081
281 2549 59 2459 389 191 2621 1109 2591
2153 1433 683 1559 1151 2411 911 1439 509
2129 1493 29 2339 659 2069 479 1949 1103
Максимум 6 правильных диагоналей.
Итак, теперь перед нами два пути к решению поставленной задачи (поиск минимального идеального квадрата 9-го порядка из различных простых чисел) методом точных ортогональных покрытий:
а) проверять все пары ортогональных покрытий массива на предмет построения из них идеального квадрата
(путь очень длинный, может растянуться на много недель и даже месяцев);
б) искать комплекты из 4-х точных попарно ортогональных покрытий массива и тоже проверять на предмет построения идеального квадрата; процедура проверки теперь есть
(ещё не знаю, как искать такие комплекты; пока не удалось ни одного комплекта найти).
Если будет доказано, что ни одного такого комплекта не существует, это будет равносильно доказательству несуществования искомого минимального квадрата.
.