Magic Squares

December 12, 2014

Our function is tedious but not difficult:

(define (magic n start up/down left/right dir)
  (define (incr x) (modulo (+ x 1) n))
  (define (decr x) (modulo (- x 1) n))
  (let ((square (make-matrix n n 0))
        (row (cond ((eq? start 'top) 0)
                   ((eq? start 'bottom) (- n 1))
                   (else (quotient n 2))))
        (col (cond ((eq? start 'left) 0)
                   ((eq? start 'right) (- n 1))
                   (else (quotient n 2)))))
    (let loop ((i 1) (row row) (col col))
      (if (< (* n n) i) square
        (let ((next-row (if (eq? up/down 'up) (decr row) (incr row)))
              (next-col (if (eq? left/right 'left) (decr col) (incr col))))
          (when (positive? (matrix-ref square next-row next-col))
            (cond ((eq? dir 'up)
                    (set! next-row (decr row)) (set! next-col col))
                  ((eq? dir 'down)
                    (set! next-row (incr row)) (set! next-col col))
                  ((eq? dir 'left)
                    (set! next-row row) (set! next-col (decr col)))
                  ((eq? dir 'right)
                    (set! next-row row) (set! next-col (incr col)))))
          (matrix-set! square row col i)
          (loop (+ i 1) next-row next-col))))))

There are eight rules that work, two starting from each side; from whichever side you start, the first parameter moves outside the square, the second parameter moves in either perpendicular direction, and the third parameter is opposite the first. Here are the eight rules applied to order-3 magic squares:

> (magic 3 'top 'up 'left 'down)
#(#(6 1 8) #(7 5 3) #(2 9 4))
> (magic 3 'top 'up 'right 'down)
#(#(8 1 6) #(3 5 7) #(4 9 2))
> (magic 3 'left 'left 'up 'right)
#(#(4 8 3) #(1 5 9) #(7 2 6))
> (magic 3 'left 'left 'down 'right)
#(#(4 8 3) #(1 5 9) #(7 2 6))
> (magic 3 'right 'right 'up 'left)
#(#(4 3 8) #(9 5 1) #(2 7 6))
> (magic 3 'right 'right 'down 'left)
#(#(4 3 8) #(9 5 1) #(2 7 6))
> (magic 3 'bottom 'down 'left 'up)
#(#(2 9 4) #(7 5 3) #(6 1 8))
> (magic 3 'bottom 'down 'right 'up)
#(#(4 9 2) #(3 5 7) #(8 1 6))

We used matrices from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/fW3wzmKI, where you will also see a function that neatly displays a magic square, like this:

> (display-square (magic 13 'top 'up 'left 'down))
  91  76  61  46  31  16   1 168 153 138 123 108  93
  92  90  75  60  45  30  15  13 167 152 137 122 107
 106 104  89  74  59  44  29  14  12 166 151 136 121
 120 105 103  88  73  58  43  28  26  11 165 150 135
 134 119 117 102  87  72  57  42  27  25  10 164 149
 148 133 118 116 101  86  71  56  41  39  24   9 163
 162 147 132 130 115 100  85  70  55  40  38  23   8
   7 161 146 131 129 114  99  84  69  54  52  37  22
  21   6 160 145 143 128 113  98  83  68  53  51  36
  35  20   5 159 144 142 127 112  97  82  67  65  50
  49  34  19   4 158 156 141 126 111  96  81  66  64
  63  48  33  18   3 157 155 140 125 110  95  80  78
  77  62  47  32  17   2 169 154 139 124 109  94  79

Pages: 1 2

2 Responses to “Magic Squares”

  1. Mike said

    Python version. Accepts rule like “start top, move up and left, else down”. Leave out the non-direction words: “top up left down”, or abbreviate it to a string of the initial letters: ‘tuld’.

    import math, re
    
    def print_magic(sq):
        w = math.ceil(math.log10(len(sq)*len(sq)))
        fmt = "{{:{}}}".format(w).format
        for row in sq:
            print(*(fmt(col) for col in row))
    
            
    def magic(size=3, rule="start top, move up and right, else down"):
        if len(rule) > 5:
            pattern = r't(?=op)|b(?=ottom)|u(?=p)|d(?=own)|l(?=eft)|r(?=ight)'
            rule = re.findall(pattern, rule)
    
        r = 0 if rule[0] == 't' else size - 1 if rule[0] == 'b' else size // 2
        c = 0 if rule[0] == 'l' else size - 1 if rule[0] == 'r' else size // 2
        dr = -1 if 'u' in rule[1:3] else 1 if 'd' in rule[1:3] else 0
        dc = -1 if 'l' in rule[1:3] else 1 if 'r' in rule[1:3] else 0
        er = -1 if 'u' in rule[3:] else 1 if 'd' in rule[3:] else 0
        ec = -1 if 'l' in rule[3:] else 1 if 'r' in rule[3:] else 0
    
        square = [[None for c in range(size)] for r in range(size)]
        for n in range(1, size * size + 1):
            square[r][c] = n
            r = (r + dr) % size
            c = (c + dc) % size
            if square[r][c] is not None:
                r = (r - dr + er) % size
                c = (c - dc + ec) % size
        return square
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: