UPI Study › Courses › C++ Programming › Free lessons › Lesson 6.6 Free with a free account
The Magic Square Puzzle
C++ Programming · Chapter 6: ArraysSection 6.6 · lesson 42 of 84video coming soon
← Multi-Dimensional ArraysNext lesson: Characters and Text in C++ →
In this lesson
A logic and pattern recognition exercise.
- Compute the magic constant every line must reach
- Write a validator with all 4 checks
- Generate odd orders by the Siamese method
- Test a validator with near misses built to break it
Transcript
Everything said in the video, section by section (1,364 words). Read along, or search it.
Opening Hook
Four Tests for a Square Grid
A square grid where every row, every column, and both diagonals add to the same number. The definition takes one sentence. Checking it takes four separate tests, three of which everybody writes, and one of which everybody forgets. Building one is harder still, and yet for odd sizes there's a rule so simple you can follow it by hand. Nothing new is introduced here. This is a workout for the array and loop material you already have.
Definition
What Makes a Magic Square
A magic square of order n is an n by n grid, containing each whole number from 1 to n squared exactly once. It's arranged so that every row, every column, and both diagonals add to the same total. Here's the order-3 square. Eight, 1, 6. 3, 5, 7. 4, 9, 2. Every row adds to 15. So does every column, and so do both diagonals. Eight lines, one total, and the digits 1 to 9 each appear exactly once.
Key Formula
Deriving the Magic Constant
That total isn't a matter of choice. It follows from the definition. The numbers 1 to n squared add to n squared, times n squared plus 1, over 2. Those must be shared equally among n rows, so each row gets one n-th of that. It simplifies to n, times n squared plus 1, over 2. For order 3, that's 15. Order 4 gives 34, order 5 gives 65, and order 8 gives 260. Odd orders are built by the Siamese method. Orders divisible by 4 use the inversion pattern. And order 6, even but not divisible by 4, is covered by neither.
Validation Logic
Why Equal Sums Aren't Enough
Checking a candidate grid means answering four separate questions. Does every row sum to the constant? Every column? Both diagonals? Those three are about sums. The fourth is about which values appear: does every value from 1 to n squared appear exactly once? That's the one people forget. Here's why equal sums aren't enough. Fill every cell of a 3 by 3 grid with 5. Every row, every column, and both diagonals add to 15. And it isn't a magic square, because the values 1 to 9 don't appear. A validator built from sums alone accepts it. The distinct-values check is what separates magic from merely balanced.
Code Walkthrough
One Check Per Function Validator
Write the validator with one check per function. N is a constant, because the grid parameter needs a fixed column count. Magic constant computes n times n squared plus 1, over 2. Uses each value once keeps a counting array, seen, with one slot per possible value, all starting at zero. For each cell, it first rejects any value outside 1 to n squared. Then it counts the value in slot value minus 1, and rejects a repeat. Indexing by value minus 1 turns, have I seen this before, into a single lookup, rather than a search. And the range test comes before the value is used as an index. That's what stops the next line writing outside the array.
Code Walkthrough
Combining Row, Column, and Diagonal Checks
The checks go together in two more functions. One loops over i, checking row i and column i against the target. The other sums both diagonals. Down adds sq, i, i, from top left to bottom right. Up adds sq, i, n minus 1 minus i, from top right to bottom left. That second diagonal is the line everybody gets wrong once.
Odd Orders
The Siamese Method Step by Step
For any odd n, a rule discovered in the seventeenth century produces a magic square directly, with no searching and no backtracking. Place 1 in the middle of the top row. Then, for each next number, move one up and one right, wrapping around to the opposite edge when you step off the grid. If the cell you land on is already occupied, ignore that move, and go one down from where you were instead. On a 3 by 3: 1 goes in the middle of the top row. Up and right from 1 wraps to the bottom right, for 2. Up and right from 2 wraps to the middle left, for 3. And step 4 is the interesting one. Up and right from 3 is taken by 1, so 4 drops one row instead. Notice the up move is written as row minus 1 plus n, all mod n, not just row minus 1, mod n. From row 0, row minus 1 is minus 1, and the remainder operator doesn't wrap negative values around the way you might hope. It gives a negative index. Adding n first keeps the value positive, so row 0 wraps to row n minus 1, as intended. Moving right needs no adjustment, because column plus 1 is never negative.
Example Output
Order-5 Square Totals 65
The same code, with n equal to 5, builds the order-5 square, and prints each row with its total. Every row comes to 65, the magic constant for order 5.
Doubly Even Orders
The Inversion Pattern for Multiples of Four
When n is divisible by 4, a different and even simpler rule works. Fill the grid with 1 to n squared in plain reading order. Then replace the value in certain cells with its complement: n squared plus 1, minus the value. The cells to change are those where the row and column positions, taken mod 4, are either equal, or add to 3. For n equal to 4, the shaded cells are the two diagonals. 1 becomes 16, 6 becomes 11, and so on. Every row of the result reaches 34.
Limitations
Sizes Neither Method Covers
So odd sizes use the Siamese method, and sizes divisible by 4 use the inversion pattern. Sizes that are even, but not divisible by 4, such as 6, 10 and 14, are covered by neither. Squares of those orders exist, but building them needs a more elaborate construction. A program that reports, no method available for this size, rather than producing a wrong grid, is behaving correctly. And pass every square you generate through your validator, rather than taking it on trust.
Testing Strategy
Near Misses That Break a Validator
A validator that says yes to a real magic square has demonstrated very little. The useful tests are the near misses, each differing from a correct square in exactly one respect. The genuine article must be accepted. All fives must be rejected, by the distinct-values check only. Swapping two cells breaks a row and a column sum. Now exchange two whole rows. Every number is still there. Pause and predict: which check catches it? Only the diagonals. Every row total and every column total is untouched. That's the test that justifies checking diagonals separately. Changing a 9 to 0 must be caught by the range test, before any indexing. Changing a 9 to 5 must be caught by the repeat test.
Graded Exercise
Five Tasks to Complete
Now the graded exercise. One: write the validator, with all four checks as separate functions. Run it against the test grids, and print which check failed, not merely that the grid isn't magic. Two: implement the Siamese method for a size the user supplies. Five must give a constant of 65, and pass your own validator. Reject even sizes with a message. Three: trace the Siamese method for 5 by hand, up to the number 8, marking where the occupied rule was used. Four, the stretch task: implement the inversion method, and verify 4 and 8. Eight must give 260 on every line. And five: in under 200 words, explain why the distinct-values check can't be replaced by a sum check.
Key Terms
Order, Constant, and Complement Defined
A few key terms. The order of a magic square is its number of rows, which equals its number of columns. The magic constant is the common total. A doubly even order is divisible by 4. A singly even order is even, but not divisible by 4. The complement is n squared plus 1, minus a value. And a near miss is a test grid that differs from a correct square in exactly one respect.
Key Takeaways
Summary and Closing Question
To summarize. The magic constant follows from the definition. A validator needs four checks: rows, columns, diagonals, and distinct values. The Siamese method builds odd orders: up and right with wrapping, and down when blocked. Doubly even orders fill in order, then complement a pattern. And test a validator with near misses built to break it. Here's something to think about. When your validator rejects a grid, why is naming the failed check worth more than a plain no?
About C++ Programming at UPI Study
C++ Programming (Computer Science 242) is a self-paced online course of 84 video lessons in 11 chapters, from your first program to decisions, loops, arrays, functions, classes, files, pointers and inheritance. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take C++ Programming with UPI Study
Where the credit goes
Universities that work with NCCRS
C++ Programming carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About The Magic Square Puzzle
How do you calculate the magic constant of a magic square?
What checks does a magic square validator need?
How does the Siamese method build an odd-order magic square?
How do you test a magic square validator with near misses?
About the C++ Programming course
How many college credits is C++ Programming?
How much does C++ Programming cost and what is included?
Which universities accept UPI Study credits?
How long does C++ Programming take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in C++ Programming.
84 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →