3

enter image description here
I need to write an algorithm how i would solve this exercise, any suggestions?

Exercise:

We have a rectangle, divided into n x m squares, with natural numbers. Write a function that counts how many magic squares are inside this rectangle.

A magic square is an arrangement of k x k (k>=2) numbers , usually integers, in a square grid, where the numbers in each row, and in each column, and the numbers in the main and secondary diagonals, all add up to the same number.

TechnoA
  • 75
  • 1
  • 10
  • "distinct numbers" so shouldn't then 6,6,6,6 be magic? – Sopel Nov 19 '14 at 15:07
  • I edited the post, numbers don't have to be distinct – TechnoA Nov 19 '14 at 15:12
  • The only idea i have came with so far that first you have to find all the squares with minimum of 4 little squares and then check if they meet the requirements to be considered magic squares :/ – TechnoA Nov 19 '14 at 15:17

1 Answers1

1

Construct 4 arrays:

1: Every element is the element from original array + one to the left.

2: Every element is the element from original array + one to the top.

3: Every element is the element from original array + one to the top left.

4: Every element is the element from original array + one to the top right.

You would get something like this for your array. Now you have to check every possible square fitting in the array (There possibly is better solution, but I can't think of any) looking for something like this in other four. Since we keep sums in the array we can clearly see that when checking an array 3x3 (from top left) all sums are 15. It means it's a magic square.

When not starting in top left it's a little less obvious but still easy. Look at example below with second magic square highlighted. You can see that evey darker element minus corresponding lighter element is constant (in this case 12)

It would work same for the first magic square, but there would be zeroes, so we can skip it.

Sopel
  • 1,179
  • 1
  • 10
  • 15
  • but this only works when you know where your magic squares are, doesn't it? – TechnoA Nov 19 '14 at 16:19
  • I said, that you have to look every possible square in the array. It just makes searching faster because you don't have to recalculate everything. – Sopel Nov 19 '14 at 16:35