Symmetries

11.6 Symmetries

Consider the following puzzle, where numbers from 1 to 19 have to be arranged in a hexagonal shape such that every diagonal sums up to 38:

puzzle(Pattern) :-
        Pattern = [
                   A,B,C,
                  D,E,F,G,
                 H,I,J,K,L,
                  M,N,O,P,
                   Q,R,S
                  ],
        Pattern :: 1 .. 19,

        % Problem constraints
        alldifferent(Pattern),
          A+B+C #= 38,     A+D+H #= 38,     H+M+Q #= 38,
         D+E+F+G #= 38,   B+E+I+M #= 38,   D+I+N+R #= 38,
        H+I+J+K+L #= 38, C+F+J+N+Q #= 38, A+E+J+O+S #= 38,
         M+N+O+P #= 38,   G+K+O+R #= 38,   B+F+K+P #= 38,
          Q+R+S #= 38,     L+P+S #= 38,     C+G+L #= 38,
        ...

In this formulation, the problem has 12 solutions, but it turns out they are just rotated and mirrored variants of each other. Removal of symmetries is still an area of active research, but a simple method is applicable in situations like this one. One can add constraints which require the solution to have certain additional properties, and so exclude many of the symmetric solutions:

        ...,
        % Optional anti-symmetry constraints
        % Forbid rotated solutions: require A to be the smallest corner
        A #< C, A #< H, A #< L, A #< S, A #< Q,
        % Forbid solutions mirrored on the A-S diagonal
        C #< H.