JavaRush /Java блог /Random /Создание "Магического квадрата" в Java
Сергей Цехмистренко
15 уровень
Минск

Создание "Магического квадрата" в 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
Нечётный квадрат заполнялся не правильно из-за отработки условия 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. Вроде работает.
Андрей Уровень 15
22 октября 2020
Для матриц с размерностью (n), кратной 4 - матрица заполняется нулями; Матрица размерностью n = 3 и 5 (дальше не проверял) - не проходит условия магического квадрата
Dmitry Уровень 27
1 июня 2020
Интересный код. Но построенный квадрат не является магическим.
Zelimkhan Уровень 26
12 мая 2020
Отличная статья, молодец!
Юра Уровень 23
12 мая 2020
С 63 строкой явные проблемы.Наверно это она так отформатировалась пи вставке?
Антон Уровень 27
11 мая 2020
Интересно. А есть практическое применения для магических квадратов?
Денис Давыдов Уровень 38
11 мая 2020
Поправьте вначале "из чисел 1, 2, 3, ..., 2 n" на "из чисел 1, 2, 3, ..., n^2"
Orlov Boris Уровень 3
11 мая 2020
Серёга однозначно ты красава! Я рад белорусским талантам! Давай ещё контент. Запили также ролик в ютьюб на своём канале. Кто знает может и он хайпанётся!)
8 мая 2020
Еще раз прошу прощения, видимо тут стоит ограничение по размеру кода:(