Overkill: Using the Awesome Power of Modern Computing to Solve Middle School Math Problems

I was helping my son with his math the other night and we hit a question called The Magic Box. You are given a 3x3 square and the digits 3,4,5,6,7,8,9,10,11, and are expected to find a way of placing them such that each row, each column, and each diagonal adds up to 21.

I'm a programmer, so my first thought was, hey, I'll make a recursive algorithm to do this. The previous question, measuring 4 quarts when you have a 3 quart measure and a 5 quart measure, was solved due to insights remembered from Die Hard With A Vengeance, so clearly, I'm not coming at these questions from the textbook.

With a little more insight, I solved it. 7 is a third of 21, and it the center of an odd-numbered sequence of numbers, so clearly, it is meant to be the center. There is only one way you can use 11 on a side, with 4 and 6, so that a center column or row will be 3 7 11. If you know that column and the 4 11 6 row, you know at least this:

.  3  .
.  7  .
4 11  6

And because you know the diagonals, you know that it'll be

8  3 10 
.  7  .
4 11  6

And you only have 5 and 9 left, and they're easy to just plug in

8  3 10
9  7  5
4 11  6

So, that's the logical way to to solve it. Clearly, order isn't important; it could be reversed on the x and y axis and still be a solution. But, once the thought of solving with a recursive algorithm came into my head, I could not leave well enough alone. So, here's a recursive program that finds all possible solutions for this problem.

	#!/usr/bin/env perl
	use feature qw{ say state signatures } ;
	use strict ;
	use warnings ;
	use utf8 ;
	use Data::Dumper ;
	my $numbers = [ 3 .. 11 ] ;
	my $array ;
	recurse_magic_box( $numbers, $array ) ;
	sub recurse_magic_box ( $numbers , $array ) {
	# numbers is the list of allowable numbers
	for my $n (@$numbers) {
	push @$array, $n ;
	if ( check_magic_box($array) ) {
	recurse_magic_box( $numbers, $array ) ;
	}
	pop @$array ;
	}
	}
	sub check_magic_box ( $array ) {
	for my $n (@$array) {
	my $c = scalar grep {m{$n}} @$array ;
	return 0 if $c > 1 ;
	}
	do {
	my $sum = 21 ;
	my $checks = [
	[ 0, 1, 2 ], # first row
	[ 3, 4, 5 ], # second row
	[ 6, 7, 8 ], # third row
	[ 0, 3, 6 ], # first col
	[ 1, 4, 7 ], # second col
	[ 2, 5, 8 ], # third col
	[ 0, 4, 8 ], # diagonal from top right
	[ 6, 4, 2 ], # diagonal from bottom right
	] ;
	for my $check (@$checks) {
	my $s = 0 ;
	for my $p (@$check) {
	$s += $array->[$p] ;
	}
	return 0 if $s != $sum ;
	}
	say join "\t", @$array[ 0 .. 2 ] ;
	say join "\t", @$array[ 3 .. 5 ] ;
	say join "\t", @$array[ 6 .. 8 ] ;
	say '' ;
	} if scalar @$array == 9 ;
	return 1 ;
	}

view raw magicbox.pl hosted with ❤ by GitHub