What to do?
To fill in the numbers, click or touch a circle and edit the value. You can press the Solve! button at any time to solve the game. You can change the polygon from a square to a hexagon by pressing the corresponding buttons. To reset the game, just press the button corresponding to the current n-Gon.
What is this?
A while ago, I got intrigued by one of the mathematical puzzles proposed by the Plus Magazine — an online magazine about math — it was called Magic 19. The puzzle consisted of allocating numbers from 1 to 19 to each of the 19 vertices of a graph with a hexagonal shape, such that each triad of vertices on the same edge had to add up to 22. To be honest, I was not intrigued by the puzzle itself, but by a reader's comment which said that this problem made an excellent case to be solved by linear programming.
Here, I transform Magic 19 into an Integer Linear Program (ILP) — similarly to what I did to build a Sudoku solver. An ILP optimizes a linear objective function over a feasible domain, which is defined by a set of linear constraints, plus the addition that all variables must have integer values. Then, solving the puzzle is a matter of finding a feasible solution to the ILP.
Each node $i \in \{1, \dots, 3n + 1\}$ in the graph above has $3n + 1$ binary variables assigned: $x_{ij} \;\,\forall j \in {1,\dots,3n + 1}$, where $n$ is the number of vertices of the chosen polygon (i.e. $n=6$ in Magic-19). These variables represent all possible values that a node can have, i.e., all the numbers from 1 to $3n+1$. For instance, if node $i$ has a value of 1, then $x_{11} = 1$. After defining the binary variables, it isn't hard to define an ILP whose solution will be a solution to our puzzle:
$\max\limits_{x \in \{0, 1\}} \; 0$
s.t.
$\sum\limits_{i=1}^{3n+1} x_{ij} = 1 \;\; \,\forall j \in \{1, \dots, 3n + 1\} \;\; (1)$
$\sum\limits_{j=1}^{3n+1} x_{ij} = 1 \;\; \,\forall i \in \{1, \dots, 3n + 1\} \ \;\; (2)$
$\sum\limits_{i \in E} \sum\limits_{j=1}^{3n+1} j x_{ij} = 3n+4 \;\; \,\forall E \;\; (3)$
The constraints in this ILP define the feasible puzzle solution space. Specifically, the constraints in (1) make sure that a unique number is assigned to each node in the graph. The constraints in (2) assign a number from 1 to $3n+1$ to each node. While the constraints in (3) guarantee that the sum of values along each edge $E$ in the graph adds up to $3n + 4$.
As a side note, in this case, we do not care about the objective function of the ILP, here set to maximize a constant! This is because we only care to find a feasible solution to the problem. Note that introducing a set of initial values does not guarantee that a feasible solution will be found. Only a correct set of initial values will render a feasible solution. Also, note that more than one feasible solution exists. Try to find them all, that is, if you dare!