JavaRush/Java блог/Random/Создание "Магического квадрата" в Java

Создание "Магического квадрата" в Java

Статья из группы Random
участников
Магическим квадратом порядка n называется квадратная матрица размера nxn, составленная из чисел 1, 2, 3, ..., n^2 так, что суммы по каждому столбцу, каждой строке и каждой из двух больших диагоналей равны между собой. Первое что вспомнилось это судоку :) Создание "Магического квадрата" в Java - 1ссылка из википедии, для тех кто не понял. Поэкспериментировав с составлением собственных алгоритмов для заполнения, я пришел к выводу, что без помощи других людей мне не справиться. Поэтому, прошерстив с десяток ссылок реализовал 3 алгоритма, которые в сумме реализуют заполнение любой матрицы “n” размерности. В начале кода сможете найти комментарии к методам, которые будут использоваться ниже. Ссылки на алгоритмы и другие (полезные?) комментарии сможете найти в теле соответствующих методов. Я в Telegram: @sergey3ts Ну и Linkedin конечно (Добавляйтесь, для меня это важно :)
// magicSquareOfOddOrder(int n);       метод для n нечетной размерности (3, 7, 9, и тд)
 // magicSquareOfEvenOddOrder(int n);   метод для n четно-нечетной размерности (n кратно 2 но не крастно 4)
 // magicSquareOfEvenOddOrder(int n);   метод для n четн-четной размерности (n кратно и 2 и 4);
 // magicSquare(int n);                 общий метод, который определяет кратность n и вызывает соотв. метод

 // Вспомогательные методы
 // standardMatrixFillingAscending(n); заполняет матрицу от 1 по возростанию
 // standardMatrixFillingDescending(n); заполняет матрицу от n*n по убыванию

 // Извиняюсь за косяки в коде (непонятные переменные(возможно(нет(да)))) :)
public class MatrixSolution16 {
    public static void main(String[] args) {
        magicSquare(6);
    }
   public static int [][] magicSquare(int n) {
        if (n % 2 !=0) return magicSquareOfOddOrder(n);             // метод для n нечетной размерности (3, 7, 9, и тд)
        else if (n % 4 != 0) return magicSquareOfEvenOddOrder(n);   // метод для n четно-нечетной размерности (n кратно 2 но не кратно 4)
        return magicSquareOfEvenOddOrder(n);                        // метод для n четн-четной размерности (n кратно и 2 и 4);
    }
   private static int[][] magicSquareOfOddOrder(int n) {
        // "Сиамский метод" - один из самых просты для восприятия
        // https://ru.xcv.wiki/wiki/Siamese_method
        // Оставлю без комментариев (gif по ссылке наглядно показывает как он работает)
        // код не сложный
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(matrix[i], 0);
        }
        int count = 1, y = 0, x = matrix.length/2;
        while (true){
            matrix[y][x] = count;

            count++;
            if (((y == 0) && (x >= n-1)) && (matrix[n-1][0] != 0)){
                y++;
            }
            else {
                y--;
                if (y < 0) {
                    y = n - 1;
                }
                x++;
                if (x == n) {
                    x = 0;
                }
                if(matrix[y][x]!=0){
                    y+=2;
                    x--;
                }
            }

            if(count==n*n+1) break;
        }
        return matrix;
    }
   private static int[][] magicSquareOfEvenOddOrder(int n) {
        // Метод "анонима" спасибо человеку, который его придумал
        // Вот ссылка на подробное описание метода http://www.klassikpoez.narod.ru/mojmetod.htm
        // Оставлю этот код без комментариев уж очень он большой
        // Надеюсь прочитав описание метода сможете понять(или нет?)
        int half = n/2;

        int[][] matrix = new int[n][n];
        int[][] tempMatrix;
        tempMatrix = magicSquareOfOddOrder(half);

        // 1/4 матрицы
        for (int i = 0; i < half; i++) {
            for (int j = 0; j < half; j++) {
                matrix[i][j] = tempMatrix[i][j];
            }
        }
        // 2/4 матрицы
        for (int i = 0; i < half; i++) {
            for (int j = half; j < n; j++) {
                int x = j-half;
                matrix[i][j] = (tempMatrix[i][x]+2*half*half);
            }
        }
        // 3/4 матрицы
        for (int i = half; i < n; i++) {
            for (int j = 0; j < half; j++) {
                int x = i-half;

                matrix[i][j] = (tempMatrix[x][j]+3*half*half);
            }
        }
        // 4/4 матрицы
        for (int i = half; i < n; i++) {
            for (int j = half; j < n; j++) {
                int x = i-half, y = j-half;
                matrix[i][j] = (tempMatrix[x][y]+half*half);
            }
        }
        int move = 0;
        for (int i = 6; i < n; i++) {
            if((i%4!=0)&&(i%2==0)) move++;
        }
        for (int j = matrix.length/2-move; j <= matrix.length/2+move-1; j++) {
            for (int i = 0; i < tempMatrix.length; i++) {

                int key = matrix[i][j];
                matrix[i][j] = matrix[half+i][j];
                matrix[half+i][j] = key;
            }
        }
        for (int j = 0; j <= 1; j++) {
            if (j == 0) {
                int key = matrix[0][0];
                matrix[0][0] = matrix[half][0];
                matrix[half][0] = key;
            }
            if (j == 1) {
                int key = matrix[half - 1][0];
                matrix[half - 1][0] = matrix[n - 1][0];
                matrix[n - 1][0] = key;
            }
        }
        for (int j = half+1; j < n-1; j++) {
            for (int i = 1; i < half-1; i++) {
                int key = matrix[i][1];
                matrix[i][1] = matrix[half+i][1];
                matrix[half+i][1] = key;
            }
        }
        return matrix;
    }
    private static int[][] evenMatrixSquare(int n){
        // Метод Раус-Болла хорошое описание нашел тут:
        // https://rep.bntu.by/bitstream/handle/data/62327/Magicheskie_kvadraty.pdf?sequence=1&isAllowed=y
        // Страница 8, 9
        int[][] matrix = WorkWithMatrix.standardMatrixFillingAscending(n);
        int[][] tempMatrix = WorkWithMatrix.standardMatrixFillingDescending(n);

        int size = 4;    // Размерность каждого квадрата (4х4 тафтология)
                         // можно заменить простой цифрой
        int x = 0;       // x, y - движение по кадратам (посмотрите как изменяются в ходе программы)
        int y = 0;
        for (int i = 0; i < (n*n/16); i++) {                // Смотрим сколько квадратов 4х4 помещается в матрице nxn
            if (x == (int)Math.sqrt(n*n/16)) {              // x, y переменные для движения по квадратам 4х4
                                                            // х проходит по первому ряду квадратов, достигая последнего
                                                            // обнуляется, а y увеличивается
                x = 0;
                y++;
            }
            // x и y должны лишь обеспечивать проход по квадратам
            for (int j = 0; j < 4; j++) {
                matrix[size*y+j][size*x+j] = tempMatrix[size*y+j][size*x+j];  // главная диагональ квадратов 4х4
                matrix[size*y+j][size*x+size-1-j] = tempMatrix[size*y+j][size*x+size-1-j]; // побочная диагональ
            }
            x++;
        }
        return matrix;
    }
}
Комментарии (24)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Максим Силевич
Уровень 24
3 марта 2021, 15:39
Нечётный квадрат заполнялся не правильно из-за отработки условия if (matrix[matrix.length-1-y][x] != 0) y--; данное условие говорит нам, что если далее по алгоритму, ячейка матрицы уже заполнена, то нужно перейти на строчку ниже от предыдущей позиции (это логичное условие), но так как алгоритм уже поменял координаты на следующую позицию, то y-- это уже не сделает и поменяет позицию на неправильную. Я не смог придумать, как сделать алгоритм рабочим с этим условием, хотя уверен, что истина на поверхности, но я ее в упор не вижу, поэтому взял другое условие, которое проверяет кратность вставляемого числа на порядок матрицы (как оказалось, оно каким то чудом тоже работает), тогда y-- подойдёт. while (true){ twoArray[(twoArray.length - 1) - y][x] = count; if (twoArray[twoArray.length - 1 - y][x] % n == 0) { y--; } else { if (x == twoArray.length - 1) x = -1; if (y >= twoArray.length - 1) y = -1; y++; x++; } count++; Второй момент, раз уж мы вставляем числа по порядку от 1 до n * n, то, насколько я понял, код int count1=0; for (int[] array:twoArray) { for (int z :array) { if(z == 0) count1++; } } if (count1==0) break; } который проверяет все ли элементы матрицы заполнены - избыточен, и его можно заменить на if (count > n * n) break; либо использовать цикл for вместо while. Вроде работает.
Максим Силевич
Уровень 24
3 марта 2021, 16:01
О "Сиамском методе" заполнения квадрата нечётного порядка можно почитать тут: http://www.natalimak1.narod.ru/metody1.htm#:~:text=%E2%80%9D%D0%98%D0%BD%D0%B4%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9%20%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%20%D1%81%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F%20%D0%BC%D0%B0%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85%20%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2,%D1%87%D0%B5%D1%80%D0%B5%D0%B7%20%D1%84%20%E2%80%93%20%E2%80%9C%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%84%D0%BC%E2%80%9D.
Андрей
Уровень 15
22 октября 2020, 13:07
Для матриц с размерностью (n), кратной 4 - матрица заполняется нулями; Матрица размерностью n = 3 и 5 (дальше не проверял) - не проходит условия магического квадрата
Dmitry
Уровень 27
1 июня 2020, 20:37
Интересный код. Но построенный квадрат не является магическим.
Zelimkhan
Уровень 26
12 мая 2020, 10:36
Отличная статья, молодец!
12 мая 2020, 11:05
Спасибо)
Юра
Уровень 23
12 мая 2020, 07:05
С 63 строкой явные проблемы.Наверно это она так отформатировалась пи вставке?
12 мая 2020, 09:02
Да, сейчас все исправлю)
12 мая 2020, 09:20
Отправил запрос на форматирование)
Антон
Уровень 27
11 мая 2020, 16:09
Интересно. А есть практическое применения для магических квадратов?
11 мая 2020, 19:18
Насколько я знаю, используют в криптографии)
Алексей
Уровень 22
12 мая 2020, 08:27
а вообще есть что-то еще годное по математике в джава? Например: Линейная алгебра и работа с матрицми и векторами (в смысле косинусное расстояние)
Юра
Уровень 23
12 мая 2020, 18:32
Если интересует, советую углубить свои знания по алгоритмам. Почитайте Тима Рафгардена , Совершенные алгоритмы.
12 мая 2020, 18:43
Как раз вчера начал читать)
Юра
Уровень 23
12 мая 2020, 19:42
Ещё одна книга в более компактном изложении и с интерестной подачей материалла: Грокаем алгоритмы, Адитья Бхаргава.
12 мая 2020, 19:57
Читаешь мои мысли) Я скачал, но она довольно трудно усвояемая)
Денис Давыдов
Уровень 38
11 мая 2020, 13:59
Поправьте вначале "из чисел 1, 2, 3, ..., 2 n" на "из чисел 1, 2, 3, ..., n^2"
11 мая 2020, 19:18
Спасибо, все исправил)
Денис Давыдов
Уровень 38
12 мая 2020, 05:09
Прошу прощения за въедчивость, но теперь 2^n на n^2)
12 мая 2020, 06:33
Прошу прощения за невнимательность)
Orlov Boris
Уровень 3
11 мая 2020, 13:25
Серёга однозначно ты красава! Я рад белорусским талантам! Давай ещё контент. Запили также ролик в ютьюб на своём канале. Кто знает может и он хайпанётся!)
11 мая 2020, 19:19
Большое спасибо)) Если найду что-нибудь интересное, то обязательно)
8 мая 2020, 14:19
Еще раз прошу прощения, видимо тут стоит ограничение по размеру кода:(
Hanna Moruga Chief editor @ JavaRush
8 мая 2020, 14:56
Сергей, если возникут еще какие-либо вопросы, связанные с публикацией постов в разделе "Статьи", можете написать мне в личку 🙌