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…