Arvi the Hacker (Арви Хэкер) (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} arvi) wrote,@ 2008-02-04 18:33:00 |
|
1 2 3 4 1 2 3 4 +---------------- +---------------- 1| 1 2 15 16 1| 16 1 15 2 2| 12 14 3 5 2| 5 8 10 11 3| 13 7 10 4 3| 4 13 3 14 4| 8 11 6 9 4| 9 12 6 7
Любопытно, экспериментировал ли кто-нибудь с магическим квадратом недавно, на гигагерцовых машинках? У меня получается, что если кодировать задачу по поиску всех магических квадратов в лоб, то даже при некоторых интеллектуальных ограничениях перебора им решаются лишь квадраты 3x3 (мгновенно, все 8 поворотов и отражений одного квадрата) и 4x4 (если написать перебор на чистом FreePascal'е, все 7040 вариантов на 1,8ГГц машинке получаются меньше, чем за 20 секунд). На врезке справа приведены два полученных магических квадрата 4x4, а именно №0 и №7039. В принципе, можно влёгкую переписать проверку IsMagic на ассемблере. Это увеличит скорость ещё в несколько раз и поможет сделать время счёта для 5x5 разумным, но большие квадраты требуют алгоритмических резервов.
1 2 3 4 5 +-------------------- 1| 1 2 13 24 25 2| 6 18 17 4 20 3| 21 16 15 10 3 4| 23 7 11 19 5 5| 14 22 9 8 12
Это я к тому, что в понедельник мне приснилась задачка по вычислению магического квадрата 10x10. Будто я лет на 10-15 моложе и снова сдаю вступительный в МГУ. Или сессию, пересдачу. Или ещё куда-то, что явно связано с Университетом. Лиц не помню. Помню лишь ощущение, что люди, передавшие задание мне лично, были спокойны, доброжелательны и уверены, что я справлюсь. И вот та программка, которая уже часами в фоне щёлкает 5x5 (первый её результат дан слева), использует обычный перебор с простейшими эвристиками из тех, которые я придумал во сне для более требовательной задачи.
Кто-нибудь ещё возился с такими (и большими) квадратами? Даже 80-символьный экран позволяет отображать квадраты 19x19, а ведь 80 символов в строке сейчас далеко не предел… Вначале я думал, что при современных гигагерцах/гигабайтах любые отображаемые квадраты должны щёлкаться, как орешки — даже брутфорсом. Что основная проблема (в том числе по быстродействию) будет с выводом квадратов. Ан нет, компьютеры всё ещё слабы и даже задачка 5x5 по-прежнему бросает вызов.
P.S. Погуглил. Хе-хе. Даже если моя программка найдёт все решения 5x5, пусть без отражений и поворотов, винчестер всё равно переполнится быстрее. Новый вариант тратит на поиск магического квадрата меньше 10 секунд, десятки тысяч их уже найдены. Все квадраты будут найдены лет через 70, но на всякий случай освобожу гигабайтик-другой уже сейчас… :-)
1 2 3 4 5 6 7 8 9 10 +---------------------------------------- 1| 3 0 7 4 51 48 95 92 99 96 2| 1 2 5 6 49 50 93 94 97 98 3| 23 20 71 68 67 64 15 12 79 76 4| 21 22 69 70 65 66 13 14 77 78 5| 83 80 63 60 56 59 39 36 11 8 6| 81 82 61 62 57 58 37 38 9 10 7| 88 91 24 27 43 40 72 75 16 19 8| 89 90 25 26 41 42 73 74 17 18 9| 52 55 84 87 32 35 28 31 44 47 10| 54 53 86 85 34 33 30 29 46 45
P.P.S. Применив к любому квадрату 5x5 из найденных LUX-метод Конвея (упомянутый алгоритмический резерв), получаем требуемый магический квадрат 10x10. Справа расположен квадрат, полученный из первого магического квадрата 5x5. Кстати, во сне на построение магического квадрата 10x10 отводился день (было утро, моё решение отдадут на проверку следующим утром). Мне ещё тогда было ясно, что задание несложное и суток для него достаточно. Действительно, уложился без особой спешки и теперь могу спать спокойно. :-))) Более того, моя программа эти магические квадраты 10x10 уже печёт сотнями (к утру их было больше 300Кб). Жаль лишь, что полный перебор (пока?) долгий и не дал результата.
А вообще-то задание интересное и напоминает второе задание вступительного 1998 года, про Тупого Сержанта. Всем советую. Возможно, действительно буду использовать магический квадрат в качестве вступительного для старших учеников — при составлении заданий 1998 года я об этом задумывался, но в то время счёл излишне сложным.
