We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Forming a Magic Square
  5. Discussions

Forming a Magic Square

Sort by

recency

|

1292 Discussions

|

  • lengistonjorry
     + 0 comments

    Forming a Magic Square is a fascinating mathematical exercise that involves arranging distinct numbers in a square grid so that the sum of the numbers in each row, column, and both main diagonals is the same. This constant sum is called the “magic constant www.getfluxusexecutor.com” or “magic sum.” Magic squares can be created using different techniques depending on whether the square has an odd, even, or doubly even order.

  • wifivop476
     + 0 comments

    Possible values range from 1 through 9, each entry of the array being distinct. So, possible solutions are permutations of the 9 digits. Furthermore, each row, column, and diagonal have to add to some magic number n = 15 as observed through the sample input and outputs. Since we have a fixed set of numbers, the total sum is fixed, and the sum for rows and columns must also be fixed. While exploring this, similar to learning about RF microneedling Santa Monica, try swapping some of the entries and you might end up with rows and columns that don't add to 15. Realize that the sample outputs can be rotated to obtain 4 solutions, and their mirrors for another 4.

  • iamhenry760
     + 0 comments

    Great discussion here — I found the insight about there being only eight valid 3×3 magic squares for the numbers 1-9 very helpful. That fact really simplifies the problem by turning it into a fixed comparison set. On a somewhat different note, while I was reading this I reflected on how the same principles of user-experience and efficient logic apply across tech domains. For example, I recently checked out the Black Hole Music APK — an Android app that emphasises smooth UI, ad-free listening, and high-quality audio. It reminded me that whether you’re solving a coding puzzle like designing a magic square or building a music app, attention to detail, performance, and clarity make the difference.

    Thanks for sharing all these approaches — they’re really helpful for understanding both the math and the implementation side of algorithmic challenges!

  • zettix1
     + 0 comments

    I first precomputed all magic squares. There's only one: 4 rotations and 4 mirrors, hence 8 representations of the same magic square. I then printed them and hard coded them.

    public static int formingMagicSquare(List<List<Integer>> s) {
// Write your code here
// precomputed all magic squares.
    int[][] allmagic = new int[][] {
    {2, 7, 6, 9, 5, 1, 4, 3, 8}, 
    {2, 9, 4, 7, 5, 3, 6, 1, 8}, 
    {4, 3, 8, 9, 5, 1, 2, 7, 6}, 
    {4, 9, 2, 3, 5, 7, 8, 1, 6}, 
    {6, 1, 8, 7, 5, 3, 2, 9, 4}, 
    {6, 7, 2, 1, 5, 9, 8, 3, 4}, 
    {8, 1, 6, 3, 5, 7, 4, 9, 2}, 
    {8, 3, 4, 1, 5, 9, 6, 7, 2}
    };
    int[] sint = new int[9];
    for (int y = 0; y < 3; y++) {
        for (int x = 0; x < 3; x++) {
            sint[x + y * 3] = s.get(y).get(x);
        }
    }
    int count = 9 * 9;
    for (int i = 0; i < allmagic.length;i++) {
        int mycount = 0;
        for (int j = 0; j < 9; j++) {
            mycount += Math.abs(allmagic[i][j] - sint[j]);
        }
        if (mycount < count) {
            count = mycount;
        }
    }
    return count;
}

  • acheong08
     + 1 comment

    I wanted to do it the naive way without Googling what the valid permutations are.

    package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
    "math"
)

func sum(s []int32) int32 {
    sum := int32(0)
    for i := range s {
        sum += s[i]
    }
    return sum
}


func isMagic(s [][]int32) bool {
    sums := []int32{
        sum(s[0]), sum(s[1]), sum(s[2]),
        s[0][0]+s[1][0]+s[2][0],                    
        s[0][1]+s[1][1]+s[2][1],                     
        s[0][2]+s[1][2]+s[2][2],                     
        s[0][0]+s[1][1]+s[2][2],                     
        s[0][2]+s[1][1]+s[2][0],                      
    }
    for i := range sums {
        if sums[i] != 15 {
            return false
        }
    }
    return true
}

func permutations(arr []int32)[][]int32{
    var helper func([]int32, int32)
    res := [][]int32{}

    helper = func(arr []int32, n int32){
        if n == 1{
            tmp := make([]int32, len(arr))
            copy(tmp, arr)
            res = append(res, tmp)
        } else {
            for i := 0; i < int(n); i++{
                helper(arr, n - 1)
                if n % 2 == 1{
                    tmp := arr[i]
                    arr[i] = arr[n - 1]
                    arr[n - 1] = tmp
                } else {
                    tmp := arr[0]
                    arr[0] = arr[n - 1]
                    arr[n - 1] = tmp
                }
            }
        }
    }
    helper(arr, int32(len(arr)))
    return res
}

func generateAllPossibleSquares() [][][]int32 {
    squares := permutations([]int32{1,2,3,4,5,6,7,8,9})
    validMagics := make([][][]int32, 8)
    validCounter := 0
    for _, s := range squares {
        square := [][]int32{s[0:3], s[3:6], s[6:9]}
        if isMagic(square) {
            validMagics[validCounter] = square
            validCounter += 1
        }
    }
    return validMagics
}

func cost(sq1 [][]int32, sq2 [][]int32) int32 {
    totalCost := int32(0)
    for i := range len(sq1) {
        for j := range len(sq1[i]) {
            totalCost += int32(math.Abs(float64(sq1[i][j] - sq2[i][j])))
        }
    }
    return totalCost
} 

/*
 * Complete the 'formingMagicSquare' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts 2D_INTEGER_ARRAY s as parameter.
 */

func formingMagicSquare(s [][]int32) int32 {
    // First, we need a function that calculates all the various sums. 
    // To find the closest magic square, we calculate the difference between each intersecting row
    // The smallest cost should be the difference between intersecting rows
    minCost := int32(math.MaxInt32)
    validMagics := generateAllPossibleSquares()
    for i := range validMagics {
        newCost := cost(s, validMagics[i])
        if newCost < minCost {
            minCost = newCost
        }
    }
    return minCost

}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    var s [][]int32
    for i := 0; i < 3; i++ {
        sRowTemp := strings.Split(strings.TrimRight(readLine(reader)," \t\r\n"), " ")

        var sRow []int32
        for _, sRowItem := range sRowTemp {
            sItemTemp, err := strconv.ParseInt(sRowItem, 10, 64)
            checkError(err)
            sItem := int32(sItemTemp)
            sRow = append(sRow, sItem)
        }

        if len(sRow) != 3 {
            panic("Bad input")
        }

        s = append(s, sRow)
    }

    result := formingMagicSquare(s)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}