Да, удивительно вероятностный алгоритм реагирует на количество существующих магических квадратов из данного массива. Если таких квадратов существует очень много, то они находятся сразу.
Отчаявшись найти магический квадрат из произвольных смитов с минимальной константой
5856, я решила попробовать квадраты с другими константами.
Представлю первые пять потенциальных массивов для магического квадрата 8-го порядка из произвольных смитов.
Во всех вариантах сначала берётся массив из 64 первых смитов: 4, …, 1678. Далее в каждом случае производится замена одного числа в этом первоначальном массиве. Получаются такие варианты:
1. заменить число 1642 на число 1736, S = 5856;
2. заменить число 1626 на число 1736, S = 5858;
3. заменить число 1642 на число 1776, S = 5861;
4. заменить число 1626 на число 1776, S = 5863;
5. заменить число 1581 на число 1755, S = 5866.
Итак, квадрат с минимальной магической константой
5856 пока никак не получается. Существует ли он вообще?
Попробовала второй потенциальный массив, наборы из 8 строк тоже генерируются плохо, не дождалась даже хотя бы одного набора.
Следующий массив оказался очень хорошим. Наборы из 8 строк генерируются сразу, ПМК из набора строится довольно быстро и уже пятый ПМК превратился в магический квадрат (проверку выполняла по программе svb).
Вот магический квадрат порядка 8 из произвольных смитов с магической константой
5861:
Код:
454 121 728 1219 517 535 1633 654
1581 438 265 852 666 1086 58 915
588 274 166 1111 1449 645 346 1282
913 1507 778 706 355 378 648 576
94 319 1626 825 729 1376 202 690
526 1284 391 762 895 958 562 483
27 1255 985 4 1165 22 1776 627
1678 663 922 382 85 861 636 634
Таким образом, задача частично решена: магический квадрат 8-го порядка из произвольных смитов найден. Но опять же повисли в воздухе два потенциальных массива. То есть нет уверенности в том, что построенный магический квадрат является наименьшим. Вполне возможно, что и квадраты с константами
5856 и
5858 тоже существуют.
Ещё лучше оказался потенциальный массив № 5, для него вообще всё получилось с первой попытки!
Это магический квадрат с константой
5866:
Код:
861 825 1678 535 562 85 654 666
378 121 728 778 1376 1449 274 762
202 1507 895 94 454 1284 913 517
958 391 346 1255 645 915 627 729
1642 382 166 1111 1165 4 690 706
663 576 922 22 355 985 1755 588
636 438 648 852 1282 58 319 1633
526 1626 483 1219 27 1086 634 265
Продолжаю работать над квадратом с константой
5856. Наборов из 8 строк сгенерировала уже более 20, ПМК получено только 8. Набор из 8 строк генерируется долго, да ещё не из каждого набора получается ПМК. Одним словом, если такой магический квадрат существует, то, наверное, всего один (с точностью до эквивалентности), ну, или их очень мало. И найти его с помощью вероятностного алгоритма чрезвычайно трудно.
Если кто-то желает поработать с полученным мной материалом для построения магического квадрата с константой
5856 (наборы из 8 строк, полумагические квадраты), пишите, я всё вышлю.
Вопросы к
12d3:
пытались ли вы по своему алгоритму сделать программу построения ВСЕХ магических квадратов порядка 7 из заданного массива?
если пытались, что не получилось?
не могли бы вы описать свой алгоритм подробнее?
Я поняла его примерно так: сначала вы генерируете все упорядоченные (оригинальные) наборы из n чисел, так что сумма всех чисел в наборе равна магической константе квадрата (вы называете эти наборы цепочками). Этот этап понятен.
Далее из полученных наборов вы каким-то образом составляете полумагические квадраты. И на последнем этапе делаете в ПМК диагонали.
Вот эти два этапа не совсем понятны.
Вопрос к
ice00:
как у вас продвигаются дела с реализацией какого-нибудь алгоритма для построения квадратов порядка 7? Мной уже предложено два таких алгоритма, которые должны дать полную проверку заданного массива на предмет составления из него магического квадрата. Первый алгоритм был предложен давно (он изложен здесь применительно к квадратам порядка 6). Второй алгоритм я здесь тоже представила. Именно с помощью этого алгоритма я получила оба магических квадрата 7-го порядка. Но он сработал у меня как вероятностный! Его необходимо реализовать так, чтобы он работал на полную проверку.
Что вы можете сказать о возможности реализации этих алгоритмов?
У меня есть и третий алгоритм, который является вариантом первого алгоритма с изменением количества строк в наборе с 5 на 4. Это намного уменьшит количество вариантов наборов, которые надо будет затем достраивать до полного квадрата.
На форуме наверняка есть эксперты по оценке эффективности алгоритмов, но они, к сожалению, не дают оценок предложенным мной алгоритмам.
В то же время, составление такой программы, которая позволит давать однозначный ответ о возможности построения магического квадрата 7-го порядка из заданного массива 49 чисел, - это очень сложная и важная задача. Насколько мне известно, такой программы не существует.
Я пока не говорю об аналогичных программах для порядков 8-9.
Хотя, как мне помнится, ice00 высказывал мнение, что предложенный мной алгоритм можно реализовать и для данных порядков.
А воз и ныне там!
