Given an odd integer N, the task is to find the magic square of order N.
Examples:
Input: N = 3
Output:
6 1 8
7 5 3
2 9 4
Input: N = 5
Output:
15 8 1 24 17
16 14 7 5 23
22 20 13 6 4
3 21 19 12 10
9 2 25 18 11
Approach Put the value 1 in the middle of the first row. Let the position be (i, j).
- Now move up one cell and move left one cell. While moving up or left, if we go beyond the square’s boundary, then consider a box on the opposite side of the square. Let (row, col) is the position.
- If the value of the magic square at (row, col) is empty, then (i, j) <– (row, col).
- If the magic[row][col] is not empty, then move down from position (i, j) to the next row by incrementing i by 1. But, while moving down, if we go beyond the square’s boundary, then consider a box on the opposite side of the square.
- Insert next higher number in the magic square at position (i, j).
- Repeat through step 1 till all the squares are filled.
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;const int MAX = 10;// Function to print the generated squarevoid print(int mat[MAX][MAX], int n){ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << " " << mat[i][j]; } cout << '\n'; }}// Function to generate the magic// square of order nvoid magic_square(int magic[MAX][MAX], int n){ // Position of the first value int i = 0; int j = (n - 1) / 2; // First value is placed // in the magic square magic[i][j] = 1; for (int k = 2; k <= n * n; k++) { // Up position int row = (i - 1 < 0) ? (n - 1) : (i - 1); // Left position int col = (j - 1 < 0) ? (n - 1) : (j - 1); // If no item is present if (magic[row][col] == 0) { // Move up and left i = row, j = col; } // Otherwise else { // Move downwards i = (i + 1) % n; } // Place the next value magic[i][j] = k; }}// Driver codeint main(){ int magic[MAX][MAX] = { 0 }; int n = 3; if (n % 2 == 1) { // Generate the magic square magic_square(magic, n); // Print the magic square print(magic, n); } return 0;} |
Java
// Java implementation of the approach class GFG { final static int MAX = 10; // Function to print the generated square static void print(int mat[][], int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(mat[i][j] + " "); } System.out.println(); } } // Function to generate the magic // square of order n static void magic_square(int magic[][], int n) { // Position of the first value int i = 0; int j = (n - 1) / 2; // First value is placed // in the magic square magic[i][j] = 1; for (int k = 2; k <= n * n; k++) { // Up position int row = (i - 1 < 0) ? (n - 1) : (i - 1); // Left position int col = (j - 1 < 0) ? (n - 1) : (j - 1); // If no item is present if (magic[row][col] == 0) { // Move up and left i = row; j = col; } // Otherwise else { // Move downwards i = (i + 1) % n; } // Place the next value magic[i][j] = k; } } // Driver code public static void main (String[] args) { int magic[][] = new int[MAX][MAX]; int n = 3; if (n % 2 == 1) { // Generate the magic square magic_square(magic, n); // Print the magic square print(magic, n); } } }// This code is contributed by AnkitRai01 |
Python 3
# Python 3 implementation of the approachMAX = 10# Function to print the generated squaredef printf(mat, n): for i in range(n): for j in range(n): print(mat[i][j], end = " ") print("\n", end = "")# Function to generate the magic# square of order ndef magic_square(magic,n): # Position of the first value i = 0 j = (n - 1) // 2 # First value is placed # in the magic square magic[i][j] = 1 for k in range(2, n * n + 1, 1): # Up position if(i - 1 < 0): row = (n - 1) else: row = (i - 1) # Left position if(j - 1 < 0): col = (n - 1) else: col = (j - 1) # If no item is present if (magic[row][col] == 0): # Move up and left i = row j = col # Otherwise else: # Move downwards i = (i + 1) % n # Place the next value magic[i][j] = k# Driver codeif __name__ == '__main__': magic = [[0 for i in range(MAX)] for j in range(MAX)] n = 3 if (n % 2 == 1): # Generate the magic square magic_square(magic, n) # Print the magic square printf(magic, n)# This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the approachusing System; class GFG { static int MAX = 10; // Function to print the generated square static void print(int [,]mat, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Console.Write(mat[i, j] + " "); } Console.WriteLine(); } } // Function to generate the magic // square of order n static void magic_square(int [,]magic, int n) { // Position of the first value int i = 0; int j = (n - 1) / 2; // First value is placed // in the magic square magic[i, j] = 1; for (int k = 2; k <= n * n; k++) { // Up position int row = (i - 1 < 0) ? (n - 1) : (i - 1); // Left position int col = (j - 1 < 0) ? (n - 1) : (j - 1); // If no item is present if (magic[row, col] == 0) { // Move up and left i = row; j = col; } // Otherwise else { // Move downwards i = (i + 1) % n; } // Place the next value magic[i, j] = k; } } // Driver code public static void Main(String[] args) { int [,]magic = new int[MAX, MAX]; int n = 3; if (n % 2 == 1) { // Generate the magic square magic_square(magic, n); // Print the magic square print(magic, n); } } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar MAX = 10;// Function to print the generated squarefunction print( mat, n){ for (var i = 0; i < n; i++) { for (var j = 0; j < n; j++) { document.write(mat[i][j]+" "); } document.write("<br>"); }}// Function to generate the magic// square of order nfunction magic_square(magic, n){ // Position of the first value var i = 0; var j = parseInt((n - 1) / 2); // First value is placed // in the magic square magic[i][j] = 1; for (var k = 2; k <= n * n; k++) { // Up position var row = (i - 1 < 0) ? (n - 1) : (i - 1); // Left position var col = (j - 1 < 0) ? (n - 1) : (j - 1); // If no item is present if (magic[row][col] == 0) { // Move up and left i = row, j = col; } // Otherwise else { // Move downwards i = (i + 1) % n; } // Place the next value magic[i][j] = k; }}// Driver codevar magic = Array.from(Array(MAX), ()=> Array(MAX).fill(0));var n = 3;if (n % 2 == 1) { // Generate the magic square magic_square(magic, n); // Print the magic square print(magic, n);}</script> |
Output:
6 1 8 7 5 3 2 9 4
Time Complexity: O(N ^ 2).
Auxiliary Space: O(N ^ 2).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
