ILP Part 102 — Gamic Square

~ afish

This is the one hundred and second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we’re going to solve Gamic Square. It’s like a magic square with a little modification. In a n by n square we put k numbers from 1 to k, so that each row, column, and diagonal containing at least two numbers has the same sum. We want to find the highest k.

Solution:

Solution works like this: for each field we have an array of n^2 + 1 flags indicating if given number was put in a field. Lines 1-10.

We make sure that given field has only one flag selected. That’s in lines 12-20.

Next, we make sure that we don’t choose numbers greater than k. This is in lines 22-37

Next, we make sure that all numbers less or equal to k are somewhere on the board. Lines 39-49.

Next, we make sure that rows, columns, and diagonals have the same sum. For rows with less than two elements, we use some sum placeholder. For other rows, we calculate the actual sum, and we make sure it’s equal to the placeholder. Since the placeholder can be anything, it’ll make sure that all sums are the same. Lines 51-92.

Next, we add the goal, and print the solution.

Output for square of size 5:

You can see that it took nearly 42 hours to find the final solution. However, we can easily change this to a decision problem asking if there is a solution for a given k.