'Magic Square' algorithm

Question

As an experiment, I'm trying to create a magic square program that checks every possible square with nine numbers. For those who do not know, a magic square is a 3x3 grid of numbers 1-9, where each row, column, and diagonal add up to 15. For example:

How would I go about checking each square using a table with Lua? I'm starting with the following table:

local sq = {
    1, 1, 1,
    1, 1, 1
    1, 1, 1
}

How would I go about checking each table in the correct order? I'm able to draw out my thinking on paper, but I'm not completely sure how to translate it to code. I already created the function to check if the square is 'magic' (following), but I'm not sure how to increase each number in the correct fashion.

local isMagic = function(s)
    return (
        s[1] + s[2] + s[3] == 15 and
        s[4] + s[5] + s[6] == 15 and
        s[7] + s[8] + s[9] == 15 and
        s[1] + s[4] + s[7] == 15 and
        s[2] + s[5] + s[8] == 15 and
        s[3] + s[6] + s[9] == 15 and
        s[1] + s[5] + s[9] == 15 and
        s[3] + s[5] + s[7] == 15
    )
end

The key word here is *backtracking*. See also http://stackoverflow.com/questions/4927778/brute-force-magic-squares. — lhf, Oct 20 '14 at 01:03
If you are looking to check all possible squares numbered 1-9, you could think about generating all the permutations of your array. Here's one solution, with a link to a simple code in Java: http://stackoverflow.com/questions/20272570/any-language-find-all-permutations-of-elements-in-a-vector-using-swapping — גלעד ברקן, Oct 20 '14 at 01:54
The questions "How would I go about checking each square using a table with Lua" as well as "How would I go about checking each table in the correct order" and "how to increase each number in the correct fashion" are not clear. You are already able to check if given square is magic, are you then trying to generate some solutions? Normally the start square has 1 2 or 3 cells already populated. — Oliver, Oct 20 '14 at 02:34

user3378649 · Answer 1 · 2014-10-20T16:57:14.230

Based on what I am seeing here, there are three patterns:

1) if we can define step by 3, we compare columns: 
sum(tab[x] for x in range(step)) == sum(tab[x] for x in xrange(step+1,step*2))== sum(tab[x] for x in xrange(2*step+1,step*3))

2) raws:
sum(tab[x] for x in range(step*step) if x%step==0) == sum(tab[x] for x in range(step*step) if x%step==1)== sum(tab[x] for x in range(step*step) if x%step==2) ===> till we x%step== step-1

3) Diagonales: 
sum(tab[x] for x in range(step*step) if x%(step+1)==0) == sum(tab[x] for x in range(step*step) if x%(step+1)==step-1)

jawo · Answer 2 · 2014-10-21T08:06:27.783

First of all, you have a 2D set, why do you use a 1D List? I'd prefer your square to be like

square[1-3][1-3]

So you can just check every line at X and every line at Y and then check the 2 diagonals.

rather than

square[1-9]

You have to Hardcode the checkings in this solution, wich will not allow you to set other square sizes without coding stuff new.

Just like:

local square = {}
square[1] = {[1] = 2, [2] = 7, [3] = 6}
square[2] = {[1] = 9, [2] = 5, [3] = 1}
square[3] = {[1] = 4, [2] = 3, [3] = 8}

Here is my code for checking if a square is magic or not. You can set the size as you wish.

#!/usr/local/bin/lua

    function checkTheSquare(square, check_for)
        local dia_sum     = 0   -- we will add the diagonal(u.l. to l.r.) values here
        local inv_dia_sum = 0   -- we will add the diagonal(u.r. to l.l.) values here

      for i = 1, #square do     -- for every [i] line in square
        local temp_sum    = 0   -- just holds the values for the [i] line temporary

        for j = 1, #square do   -- for every [j] line in square
          temp_sum = temp_sum + square[i][j]   -- add the square[i][j] value to temp
        end

        dia_sum = dia_sum + square[i][i]  
        -- this will go like: [1][1] -> [2][2] -> [3][3] ...

        inv_dia_sum = inv_dia_sum + square[i][#square-i+1]
        -- this will go like: [1][3] -> [2][2] -> [3][1] ...            

        if temp_sum ~= check_for then return false end
        -- first possible find of wrong line -> NOT MAGIC

      end

      if dia_sum ~= check_for and inv_dia_sum ~= check_for then
        return false 
        -- due its not magic
      end

      return true
      -- ITS MAGIC! JUHUUU
    end


    local square = {}
    square[1] = {[1] = 16, [2] = 3,  [3] = 2,  [4] = 13}
    square[2] = {[1] = 5,  [2] = 10, [3] = 11, [4] = 8}
    square[3] = {[1] = 9,  [2] = 6,  [3] = 7,  [4] = 12}
    square[4] = {[1] = 4,  [2] = 15, [3] = 14, [4] = 1}

    local check_for = 34

    print(checkTheSquare(square, check_for) == true)

compared to your very own code, it looks more complicated but:

Yours isn't an algorithm, its a procedure.
Mine is dynamic. One could also add random values in the square-fields, would be interisting how many tries it'll take in average, to provide a magic square.

'Magic Square' algorithm

2 Answers2

Linked