# Magic Squares (#124)

**URL:** <https://www.ruby-forum.com/t/magic-squares-124/104975>\
**Category:** Ruby\
**Created:** [May 24, 2007, 2:19pm UTC](https://www.ruby-forum.com/t/magic-squares-124/104975 "2007-05-24T14:19:16Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [May 24, 2007, 2:19pm UTC](https://www.ruby-forum.com/t/magic-squares-124/104975/1 "2007-05-24T14:19:16Z")

</div>

I was pleasantly surprised by the number of people that tackled the  
extra credit  
this time around. Essentially, there are different algorithms for  
building  
magic squares depending on the size of the square. There are in fact  
three  
different algorithms: one for odd sizes, one for doubly even (divisible  
by 4)  
sizes, and another for singly even (divisible by 2 but not 4) sizes.

One solution that did handle all three cases came from David T…  
Let’s dive  
right into how David constructs the squares:

class MagicSquare

```
def initialize(size = 3)
  raise "Error: size must greater than 2." if size < 3
  @magic_square = if (size % 2 != 0)
    OddMagicSquare.new(size)
  elsif (size % 4 == 0)
    DoublyEvenMagicSquare.new(size)
  else
    SinglyEvenMagicSquare.new(size)
  end
end

# ...

```

Here we see the initialization deferred to various classes based on the  
requested square size. These are just the conditions for the various  
algorithms  
I mentioned earlier.

One point of interest is that this solution won’t construct a magic  
square of  
size one, though they are legal:

±–+  
| 1 |  
±–+

Let’s see some of the other methods in this class:

```
# ...

def size
  @magic_square.size
end

def [](i,j)
  @magic_square[i,j]
end

# ...

```

These two methods just delegate to the inner square object. Nothing  
tricky  
there.

Next we have the pretty printer:

```
# ...

def to_s
  digits = (size * size).to_s.size
  divider = '+' + '-' * ((digits + 2) * size + (size - 1)) + "+\n"
  (0...size).inject(divider) do |s, i|
    (0...size).inject(s + "|") do |s, j|
      s + " #{self[i,j].to_s.rjust(digits)} |"
    end + "\n" + divider
  end
end

# ...

```

Most solutions included a routine pretty similar to this. You first  
have to  
find the width of the largest number and assemble a properly size  
border. Then  
you can iterate over the rows and cells printing them at the proper  
width and  
with borders between.

David also included a method that verifies his work:

```
# ...

def is_magic_square?
  size = self.size
  n = size * size

  array = Array.new(n)
  (0...size).each do |i|
    (0...size).each do |j|
      index = self[i,j] - 1
      return false if (index < 0) || (index >= n) || array[index]
      array[index] = true
    end
  end
  return false unless array.all?

  sum = size * (size * size + 1) / 2
  (0...size).each do |i|
    return false if sum != (0...size).inject(0) { |s,j| s + 

```

self[i,j] }  
return false if sum != (0…size).inject(0) { |s,j| s +  
self[j,i] }  
end  
return false if sum != (0…size).inject(0) { |s,i| s + self[i,i]  
}  
return false if sum != (0…size).inject(0) { |s,i|  
s + self[i, size-1-i]  
}  
true  
end

```
# ...

```

This method begins by calculating a few sizes. It then launches into  
verifying  
that all the numbers in the expected range were used. This code works  
by  
filling an Array the length of all the numbers with nils. It then walks  
all  
numbers of the square, replacing that index with a true value. Finally  
it  
checks that they are all true. The rest of the method does the standard  
magic  
square validation by row, column, and diagonal.

We’re now ready to examine the three individual algorithms:

```
# ...

private
class OddMagicSquare
  attr_reader :size

  def initialize(size)
    @size = size
    n = @size * @size
    @array = Array.new(n)
    i, j = 0, @size/2
    (1..n).each do |v|
      @array[get_index(i,j)] = v
      a, b = i-1, j+1
      i, j = self[a,b] ? [i+1, j] : [a, b]
    end
  end

  def [](i, j)
    @array[get_index(i,j)]
  end

  private
  def get_index(i, j)
    (i % @size) * @size + (j % @size)
  end
end

# ...

```

The algorithm for odd size magic squares is pretty straightforward. You  
begin  
by placing a one in the top center of the of the square. From there you  
just  
count, placing each number you come to in the square above and to the  
right of  
the last square you filled. The board “wraps” for these movements, so  
moving  
off the top brings you to the bottom and moving off the right side  
returns you  
to the left. If a normal move would take you to a filled square, you  
drop one  
square instead.

The above is a Ruby implementation of this algorithm. The values are  
all  
calculated at the time of object construction and stored in an instance  
variable. They can then be accessed at any time via the [] method which  
uses  
row major indexing.

```
# ...

class DoublyEvenMagicSquare
  attr_reader :size

  def initialize(size)
    @size = size
  end

  def [](i, j)
    i, j = i % @size, j % @size
    value = (i * @size) + j + 1
    i, j = i % 4, j % 4
    ((i == j) || (i + j == 3)) ? (@size*@size+1-value) : value
  end
end

# ...

```

Doubly even squares use an easy algorithm that can calculate a given  
value given  
just the coordinates. Because of that, no effort is made to  
pre-calculate the  
values here and all the work is done in the method.

This algorithm divides the overall grid into two kinds of squares. One  
type is  
all squares that land on any diagonal created by subdividing the grid  
into four  
by four subgrids. All other squares make up the other type. Once you  
know  
which type of square you are dealing with, simple counting, from left to  
right  
and top to bottom, will give you the value of the square. Diagonal  
squares  
count down from the highest number and the other squares count up from  
one.

We have one more algorithm to go:

```
class SinglyEvenMagicSquare
  attr_reader :size

  L = [4, 1, 2, 3]
  U = [1, 4, 2, 3]
  X = [1, 4, 3, 2]

  def initialize(size)
    @size = size
    @odd_magic_square = MagicSquare.new(@size/2)
  end

  def [](i, j)
    i, j = i % @size, j % @size
    ii, jj = i / 2, j / 2
    center = @size / 2 / 2
    value = @odd_magic_square[ii, jj]
    case
      when ii < center then L
      when ii == center then (jj == center) ? U : L
      when ii == center+1 then (jj == center) ? L : U
      else X
    end [i%2*2 + j%2] + 4 * (value - 1)
  end
end

```

end

# …

The final algorithm is the trickiest. You divide the grid into two by  
two  
subgrids. Each subgrid is assigned a letter: L, U, or X. The first  
(size - 2)  
/ 4 + 1 rows are L’s, there’s one row of U’s, and the rest of the rows  
are X’s.  
You also swap the center U with the L just above it. The letters  
describe the  
order you fill subgrids. You can see these orders defined in constants  
at the  
top of David’s class. The only other element you need to know is the  
order to  
fill in the subgrids. That is determined by building a size / 2 magic  
square  
using the odd pattern described early. The order of those numbers  
dictate the  
order the subgrids are filled in.

The final piece of the puzzle is the application code:

# …

if **FILE** == $0  
puts MagicSquare.new(ARGV[0].to\_i)  
end

This just builds and prints the correct square object from the choices  
we have  
been examining. Note that to\_s() is called implicitly by puts().

My thanks to all the brave souls who went above and beyond the quiz  
requirements  
to show us great solutions.

Tomorrow we will play with some fractal fun…