Magic Non-Square

Computer Science Level 5

In how many ways can we fill a 3 × 5 3 \times 5 board with integers from 1 to 15 1 \text{ to } 15 such that the following conditions hold?

  1. Each integer is used exactly once.
  2. In all the rows, the sum of all the numbers in the row are equal.
  3. In all the columns, the sum of all the numbers in the column are equal.

Also:

  • All permutations of rows or columns count as distinct.
  • Transposing the board is not allowed.

Explicit example:

[ 1 3 11 12 13 8 7 9 10 6 15 14 4 2 5 ] \begin{bmatrix} 1 & 3 & 11 & 12 & 13 \\ 8 & 7 & 9 & 10 & 6 \\ 15 & 14 & 4 & 2 & 5 \end{bmatrix}


The answer is 28080.

View wiki
Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

We make the following observations:

  1. Since there are all the numbers from 1 to 15, the sum of all the numbers must be 120.
  2. Because there are 5 rows, the sum of each row must be 24.
  3. Because there are 3 rows, the sum of each row must be 40.

And formulate an idea for symmetry breaking:

  1. Given a magic non-square, we can permute the rows and the columns separately to form 5!3! magic non-squares from it. We could use this idea for what is called symmetry breaking in constraint programming.

We call a non-square primitive if both of the following holds:

  • 1 is at the top left position.
  • The board has the first column and the first row both in ascending order.

Now, we are ready to use the python-constraint library (or any other language, for that matter) to implement a constraint model. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
from constraint import *

problem = Problem()

#Declaring the range of the variables
problem.addVariables(range(0, 15), range(1, 16))

#AllDifferent is a Global Constraint telling the solver that all the variables must take different values
problem.addConstraint(AllDifferentConstraint(), range(0, 15))

#The rows and the columns must sum up to 40 and 24 respectively
for row in range(3):
    problem.addConstraint(ExactSumConstraint(40),
                          [row*5+i for i in range(5)])
for col in range(5):
    problem.addConstraint(ExactSumConstraint(24),
                          [col+5*i for i in range(3)])

#phanthanhtoms method of primitive boards
problem.addConstraint(lambda *x: x[0]==1,[0])
problem.addConstraint(lambda *l: all(l[i] <= l[i+1] for i in xrange(len(l)-1)),[0,1,2,3,4])
problem.addConstraint(lambda *l: all(l[i] <= l[i+1] for i in xrange(len(l)-1)),[0,5,10])

print len([sol for sol in problem.getSolutions()])

That should tell us there are just 39 39 primitive boards and hence a total of 28080 28080 boards

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

This is an interesting approach. Can you say more about what the constraint package does? As written, it might be hard for people not familiar to follow your solution.

Very cool.

Thaddeus Abiy - 5 years, 10 months ago

Log in to reply

Thanks.

The problem is that I am not sure of my solution. I need someone to check if I ran the numbers correct.

Agnishom Chattopadhyay - 5 years, 10 months ago

Log in to reply

Here is a list of all the actual solutions I generated with my approach.

Thaddeus Abiy - 5 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...