# ============================================================
# Generate all 4x4 magic squares containing only 0 and 1.
# A "magic square" here means:
# - All rows sum to the same target
# - All columns sum to the same target
# - Both diagonals also sum to that same target
#
# Because entries are only 0 or 1, the row/column sums can only
# be 0, 1, 2, 3, or 4. We try all possibilities.
#
# The algorithm:
# 1. Precompute all 4‑element binary rows and group them by sum.
# 2. For each possible magic sum S:
# - Build all 4‑row combinations whose row sums are S.
# - Prune early by checking column sums as rows are added.
# - When 4 rows are placed, check diagonals.
# 3. Collect and print all valid squares.
#
# This avoids brute‑forcing all 2^16 grids and instead uses
# structured pruning, which is dramatically faster.
# ============================================================
# Generate all binary rows of length 4
ROWS = (0..15).map { |n| "%04b" % n }.map { |s| s.chars.map(&:to_i) }
# Group rows by their sum
ROWS_BY_SUM = ROWS.group_by { |r| r.sum }
# Store results
magic_squares = []
# Try all possible magic sums
(0..4).each do |target_sum|
candidate_rows = ROWS_BY_SUM[target_sum]
# Backtracking search
build = []
# Column accumulator
col_sums = [0, 0, 0, 0]
# Recursive function to assemble rows
define_method(:place_row) do |idx|
# If 4 rows placed, check diagonals
if idx == 4
main_diag = build[0][0] + build[1][1] + build[2][2] + build[3][3]
anti_diag = build[0][3] + build[1][2] + build[2][1] + build[3][0]
if main_diag == target_sum && anti_diag == target_sum
magic_squares << build.map(&:dup)
end
return
end
candidate_rows.each do |row|
# Try placing this row
valid = true
# Update column sums and prune early
4.times do |c|
new_sum = col_sums[c] + row[c]
# If column exceeds target sum, prune
if new_sum > target_sum
valid = false
break
end
end
next unless valid
# Apply row
build << row
old_cols = col_sums.dup
4.times { |c| col_sums[c] += row[c] }
# Continue
place_row(idx + 1)
# Undo row
build.pop
col_sums.replace(old_cols)
end
end
place_row(0)
end
# Print results
magic_squares.each_with_index do |sq, i|
puts "Magic square ##{i + 1}:"
sq.each { |row| puts row.join(" ") }
puts
end
# run:
#
# Magic square #1:
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
#
# Magic square #2:
# 0 0 0 1
# 0 1 0 0
# 1 0 0 0
# 0 0 1 0
#
# Magic square #3:
# 0 0 0 1
# 1 0 0 0
# 0 0 1 0
# 0 1 0 0
#
# Magic square #4:
# 0 0 1 0
# 0 1 0 0
# 0 0 0 1
# 1 0 0 0
#
# Magic square #5:
# 0 0 1 0
# 1 0 0 0
# 0 1 0 0
# 0 0 0 1
#
# Magic square #6:
# 0 1 0 0
# 0 0 0 1
# 0 0 1 0
# 1 0 0 0
#
# Magic square #7:
# 0 1 0 0
# 0 0 1 0
# 1 0 0 0
# 0 0 0 1
#
# Magic square #8:
# 1 0 0 0
# 0 0 0 1
# 0 1 0 0
# 0 0 1 0
#
# Magic square #9:
# 1 0 0 0
# 0 0 1 0
# 0 0 0 1
# 0 1 0 0
#
# Magic square #10:
# 0 0 1 1
# 0 1 0 1
# 1 0 1 0
# 1 1 0 0
#
# Magic square #11:
# 0 0 1 1
# 1 1 0 0
# 0 0 1 1
# 1 1 0 0
#
# Magic square #12:
# 0 0 1 1
# 1 1 0 0
# 1 1 0 0
# 0 0 1 1
#
# Magic square #13:
# 0 1 0 1
# 0 1 0 1
# 1 0 1 0
# 1 0 1 0
#
# Magic square #14:
# 0 1 0 1
# 1 0 1 0
# 1 0 1 0
# 0 1 0 1
#
# Magic square #15:
# 0 1 0 1
# 1 1 0 0
# 0 0 1 1
# 1 0 1 0
#
# Magic square #16:
# 0 1 1 0
# 0 1 1 0
# 1 0 0 1
# 1 0 0 1
#
# Magic square #17:
# 0 1 1 0
# 1 0 0 1
# 0 1 1 0
# 1 0 0 1
#
# Magic square #18:
# 1 0 0 1
# 0 1 1 0
# 1 0 0 1
# 0 1 1 0
#
# Magic square #19:
# 1 0 0 1
# 1 0 0 1
# 0 1 1 0
# 0 1 1 0
#
# Magic square #20:
# 1 0 1 0
# 0 0 1 1
# 1 1 0 0
# 0 1 0 1
# Magic square #21:
# 1 0 1 0
# 0 1 0 1
# 0 1 0 1
# 1 0 1 0
#
# Magic square #22:
# 1 0 1 0
# 1 0 1 0
# 0 1 0 1
# 0 1 0 1
#
# Magic square #23:
# 1 1 0 0
# 0 0 1 1
# 0 0 1 1
# 1 1 0 0
# Magic square #24:
# 1 1 0 0
# 0 0 1 1
# 1 1 0 0
# 0 0 1 1
#
# Magic square #25:
# 1 1 0 0
# 1 0 1 0
# 0 1 0 1
# 0 0 1 1
#
# Magic square #26:
# 0 1 1 1
# 1 1 0 1
# 1 1 1 0
# 1 0 1 1
#
# Magic square #27:
# 0 1 1 1
# 1 1 1 0
# 1 0 1 1
# 1 1 0 1
#
# Magic square #28:
# 1 0 1 1
# 1 1 0 1
# 0 1 1 1
# 1 1 1 0
#
# Magic square #29:
# 1 0 1 1
# 1 1 1 0
# 1 1 0 1
# 0 1 1 1
#
# Magic square #30:
# 1 1 0 1
# 0 1 1 1
# 1 0 1 1
# 1 1 1 0
#
# Magic square #31:
# 1 1 0 1
# 1 0 1 1
# 1 1 1 0
# 0 1 1 1
#
# Magic square #32:
# 1 1 1 0
# 0 1 1 1
# 1 1 0 1
# 1 0 1 1
#
# Magic square #33:
# 1 1 1 0
# 1 0 1 1
# 0 1 1 1
# 1 1 0 1
#
# Magic square #34:
# 1 1 1 1
# 1 1 1 1
# 1 1 1 1
# 1 1 1 1
#
