# Magic Hexagon of order 3

## Task description

The task is to place the integers 1,...,19 in the following grid so that the sum of all numbers in a straight line (there are lines of length 3, 4 and 5) is equal to 38:

An example of a solution is:

This task looks very simple, yet is almost impossibly hard to solve manually.

## Solutions methods

Here are 3 methods to solve this task, in increasing order of abstraction:
1. mhex1.lisp: Macros are used for abbreviation, and pruning is explicit. Reordering the loops is tedious and error-prone due to variable interdependence.
2. mhex2.lisp: Macros are used to let us state the problem in terms of a little language, consisting of lists of variables that ought to sum to 38. At compilation time, macro expansion yields code that is equivalent to the solution above. Pruning code is generated. Experimenting with different variable orderings is easy: All it takes is reordering those lists. A more efficient version was easily found and is available as mhex3.lisp (diff). Sample run:
```   \$ gcl -load mhex3.lisp -batch

(3 17 18 19 7 1 11 16 2 5 6 9 12 4 8 14 10 13 15)
(3 19 16 17 7 2 12 18 1 5 4 10 11 6 8 13 9 14 15)
(9 11 18 14 6 1 17 15 8 5 7 3 13 4 2 19 10 12 16)
(9 14 15 11 6 8 13 18 1 5 4 10 17 7 2 12 3 19 16)
(10 12 16 13 4 2 19 15 8 5 7 3 14 6 1 17 9 11 18)
(10 13 15 12 4 8 14 16 2 5 6 9 19 7 1 11 3 17 18)
(15 13 10 14 8 4 12 9 6 5 2 16 11 1 7 19 18 17 3)
(15 14 9 13 8 6 11 10 4 5 1 18 12 2 7 17 16 19 3)
(16 12 10 19 2 4 13 3 7 5 8 15 17 1 6 14 18 11 9)
(16 19 3 12 2 7 17 10 4 5 1 18 13 8 6 11 15 14 9)
(18 11 9 17 1 6 14 3 7 5 8 15 19 2 4 13 16 12 10)
(18 17 3 11 1 7 19 9 6 5 2 16 14 8 4 12 15 13 10)
```
3. hexagon.pl: A Prolog solution using integer constraints.

Propagating constraints and pruning is left to the constraint solver. If you improve the constraint solver, you improve all programs that use it.

Sample run:
```   ?- magic_hexagon(Vs), label(Vs).
Vs = [3, 17, 18, 19, 7, 1, 11, 16, 2, 5, 6, 9, 12, 4, 8, 14, 10, 13, 15] ;
Vs = [3, 19, 16, 17, 7, 2, 12, 18, 1, 5, 4, 10, 11, 6, 8, 13, 9, 14, 15] .
```
Main page