Кубик Рубика имеет сложную конструкцию, для игры в шахматы нужны фигурки и доска, для многочисленных карточных игр необходимы колоды карт разного объёма, для древнейшей игры в кости требуются аккуратно изготовленные кубики. И только для игры в судоку не нужно ничего, кроме листа бумаги и карандаша.
Примерно год назад я рассматривал тему использования GPU на примере вычисления «магических квадратов» 4х4. Там все довольно-таки очевидно, этих квадратов всего 7040, и вычислить их можно практически на чем угодно, хоть на Ардуине (но это не точно). Аналогичным способом я решил найти все квадраты 5х5, и результаты оказались весьма интересными, забегая вперед, скажу сразу, найти их я так и не смог.
Если кому интересно, подробности решения пятничной «несложной задачи» под катом.
Привет habr.
Тема «магических квадратов» достаточно интересна, т.к. с одной стороны, они известны еще с древности, с другой стороны, вычисление «магического квадрата» даже сегодня представляет собой весьма непростую вычислительную задачу. Напомним, чтобы построить «магический квадрат» NxN, нужно вписать числа 1..N*N так, чтобы сумма его горизонталей, вертикалей и диагоналей была равна одному и тому же числу. Если просто перебрать число всех вариантов расстановки цифр для квадрата 4х4, то получим 16! = 20 922 789 888 000 вариантов.
Подумаем, как это можно сделать более эффективно.
Читать полностью »
