You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
🧩 Constraint Solving POTD:Problem of the Day: Magic Squares
#79797
Fill an n × n grid with the integers 1..n2, each used exactly once, so that every row, every column, and both main diagonals sum to the same magic constant
Input:n. Output: all (or one) grids satisfying the constraints.
We verified the solution counts by exhaustive search: 8 for n = 3 and 7040 for n = 4. All 8 solutions for n = 3 are rotations or reflections of the grid above, so they form a single symmetry class.
Why It Matters
Balanced allocation: Splitting distinct items (tasks, staff, samples) into groups with equal totals uses the same pattern: AllDifferent plus linear sum constraints. The magic square is the grid version of that model.
Solver benchmarking: Magic squares combine a global distinctness constraint with many overlapping linear constraints, which makes them a standard stress test for propagation strength. Unlike Sudoku or Latin squares, the sums force reasoning about values, not just distinctness.
Modeling Approaches
Approach A: Constraint programming (AllDifferent + linear equalities)
Variables: x[i][j] ∈ {1..N}, where N = n2
Constraints: AllDifferent(x); for each line L in the rows, columns, and two diagonals, Σ_{(i,j)∈L} x[i][j] = M
Trade-offs: Only N variables, and compact. AllDifferent gives strong domain filtering, but the sum constraints prune only by bounds, so they propagate more weakly than the distinctness constraint.
Variables: y[i][j][v] ∈ {0,1}, equal to 1 iff cell (i,j) holds value v
Constraints:
each cell gets one value: Σ_v y[i][j][v] = 1
each value is used once: Σ_{i,j} y[i][j][v] = 1
each line sums to M: Σ_{(i,j)∈L} Σ_v v · y[i][j][v] = M
Trade-offs: n4 binaries (256 for n = 4), which is easy to express. The LP relaxation is weak here: setting every y = 1/N satisfies all constraints, so the bound is uninformative. Solving depends on branching and integrality rather than on the LP.
Example Model (Pseudo-code, Approach A)
model(n):
N ← n*n; M ← n*(N+1)/2
for i, j in [0..n): x[i][j] ∈ {1..N}
AllDifferent(x[0][0], ..., x[n-1][n-1])
for i in [0..n):
Sum(x[i][0..n)) = M # row i
Sum(x[0..n][i]) = M # column i
Sum(x[i][i] for i) = M # main diagonal
Sum(x[i][n-1-i] for i) = M # anti-diagonal
# Symmetry breaking: one representative per D4 orbit
x[0][0] < x[0][n-1], x[0][0] < x[n-1][0], x[0][0] < x[n-1][n-1]
x[0][1] < x[1][0]
search: first-fail variable order, ascending values
Key Techniques
AllDifferent filtering. Régin's matching-based algorithm achieves generalised arc consistency for AllDifferent. It removes any value that appears in no maximum matching between cells and values. Most modern CP solvers (OR-Tools CP-SAT, Gecode, Chuffed) implement this or a close variant.
Bounds reasoning on sums. Suppose a line has k empty cells and needs remaining sum R. Feasibility requires that the sum of the k smallest unused values is at most R, and the sum of the k largest unused values is at least R. This check prunes heavily as the grid fills, and it is the pruning used in our verification search.
Symmetry breaking. The rotation and reflection group D4 has order 8, so a naive search visits each solution up to 8 times. Put the smallest corner at (0,0) and order the two cells beside it, as in the pseudo-code. Each symmetry class then has exactly one representative. For n = 4 this leaves 880 classes, and 7040 = 8 × 880.
Challenge Corner
Predict, then measure: Before running anything, predict how many 4×4 solutions your model finds with no symmetry breaking, and how many remain after it. Then check your prediction against the 7040 and 880 figures above.
Redundant constraints: Can you prove that the centre of any 3×3 magic square must be 5? (Hint: add up the four lines through the centre.) Does adding that fact as a constraint speed up your model?
Extension: Add the broken-diagonal constraints to get pandiagonal magic squares. For which values of n do solutions exist? Use your solver to investigate n = 4 and n = 5.
References
Rossi, van Beek & Walsh (eds.), Handbook of Constraint Programming, Elsevier, 2006. Standard reference for global constraints such as AllDifferent.
J.-C. Régin, "A filtering algorithm for constraints of difference in CSPs", AAAI 1994. The matching-based AllDifferent filtering used by modern solvers.
Google OR-Tools, CP-SAT solver documentation (developers.google.com/optimization). Practical reference for modeling AllDifferent and linear constraints.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
Problem Statement
Fill an
n × ngrid with the integers1..n2, each used exactly once, so that every row, every column, and both main diagonals sum to the same magic constantM = n(n2 + 1) / 2Instance (n = 3, M = 15):
Check: rows 15 / 15 / 15; columns 15 / 15 / 15; diagonals 2+5+8 = 15 and 6+5+4 = 15.
Input:
n. Output: all (or one) grids satisfying the constraints.We verified the solution counts by exhaustive search: 8 for
n = 3and 7040 forn = 4. All 8 solutions forn = 3are rotations or reflections of the grid above, so they form a single symmetry class.Why It Matters
AllDifferentplus linear sum constraints. The magic square is the grid version of that model.Modeling Approaches
Approach A: Constraint programming (AllDifferent + linear equalities)
x[i][j] ∈ {1..N}, whereN = n2AllDifferent(x); for each lineLin the rows, columns, and two diagonals,Σ_{(i,j)∈L} x[i][j] = MNvariables, and compact.AllDifferentgives strong domain filtering, but the sum constraints prune only by bounds, so they propagate more weakly than the distinctness constraint.Approach B: 0-1 integer programming (assignment model)
y[i][j][v] ∈ {0,1}, equal to 1 iff cell(i,j)holds valuevΣ_v y[i][j][v] = 1Σ_{i,j} y[i][j][v] = 1M:Σ_{(i,j)∈L} Σ_v v · y[i][j][v] = Mn4binaries (256 forn = 4), which is easy to express. The LP relaxation is weak here: setting everyy = 1/Nsatisfies all constraints, so the bound is uninformative. Solving depends on branching and integrality rather than on the LP.Example Model (Pseudo-code, Approach A)
Key Techniques
AllDifferent filtering. Régin's matching-based algorithm achieves generalised arc consistency for
AllDifferent. It removes any value that appears in no maximum matching between cells and values. Most modern CP solvers (OR-Tools CP-SAT, Gecode, Chuffed) implement this or a close variant.Bounds reasoning on sums. Suppose a line has
kempty cells and needs remaining sumR. Feasibility requires that the sum of theksmallest unused values is at mostR, and the sum of theklargest unused values is at leastR. This check prunes heavily as the grid fills, and it is the pruning used in our verification search.Symmetry breaking. The rotation and reflection group
D4has order 8, so a naive search visits each solution up to 8 times. Put the smallest corner at(0,0)and order the two cells beside it, as in the pseudo-code. Each symmetry class then has exactly one representative. Forn = 4this leaves 880 classes, and 7040 = 8 × 880.Challenge Corner
ndo solutions exist? Use your solver to investigaten = 4andn = 5.References
AllDifferent.AllDifferentfiltering used by modern solvers.developers.google.com/optimization). Practical reference for modelingAllDifferentand linear constraints.All reactions