title: Restrict search in Prolog - Magic Sqare
body: <p>I want to solve the Most Perfect Magic Square with a Prolog program.</p>
  <p>Wiki page: <a href="https://en.wikipedia.org/wiki/Most-perfect_magic_square" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Most-perfect_magic_square</a></p>
  <p>When I input the query &quot;magic_square(4, [[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]]).&quot; (which is a valid Magic Square) my program returns true. So I assume my rule basis is correct.</p>
  <p>Unfortunately, if more than 9 Values are unknown, it takes forever to find a solution.</p>
  <p>I need help to restrict my search, so the Program finds a solution in a reasonable time. Ideally, it should also work with a 12 x 12 grid(and also every other multiple of 4) and no Values given: magic_square(12, Matrix).</p>
  <p>Thanks a lot!</p>
  <p>Here my Code:</p>
  <pre><code>:- use_module(library(clpfd)).
  
  diag2_sum(0, _, _, _).
  diag2_sum(I0, C1, Row1, Row3) :-
      I0 &gt; 0,
      nth1(I0,Row1,A),
      (I0 =:= 2 -&gt; I2 = 4 ; I2 is mod(I0 + 2,4)),
      nth1(I2,Row3,B),
      C1 =:= A + B,
      I1 is I0 - 1,
      diag2_sum(I1, C1, Row1, Row3).
  
  diag_sum([_,_], _, _).
  diag_sum([Row1|Tail], C1, N) :-
      nth1(2,Tail,Row3),
      diag2_sum(N, C1, Row1,Row3),
      diag_sum(Tail, C1, N).
  
  square_sum_x(_, _, _, 0).
  square_sum_x(Row1, Row2, C2, I0) :-
      (I0 =:= 3 -&gt; I2 = 4 ; I2 is mod(I0 + 1,4)),
      nth1(I0,Row1,Elem1),
      nth1(I2,Row1,Elem2),
      nth1(I0,Row2,Elem3),
      nth1(I2,Row2,Elem4),
      C2 =:= Elem1 + Elem2 + Elem3 + Elem4,
      I1 is I0 - 1,
      square_sum_x(Row1, Row2, C2, I1).
  
  
  square_sum_y(_, _, 0, _).
  square_sum_y(Matrix, C2, I0, N) :-
      (I0 =:= 3 -&gt; I2 = 4 ; I2 is mod(I0 + 1,4)),
      nth1(I0,Matrix,Row1),
      nth1(I2,Matrix,Row2),
      
      square_sum_x(Row1,Row2, C2, N),
      I1 is I0 - 1,
      square_sum_y(Matrix, C2, I1, N).
  
  magic_square(N, Matrix) :-
      Nmax is N * N,
      C1 is Nmax + 1,
      C2 is C1 * 2,
      write(C1),nl,write(C2),nl,
      length(Matrix, N),
      maplist(same_length(Matrix), Matrix),
      append(Matrix, Vs),
      Vs ins 1..Nmax, all_different(Vs),
      maplist(label, Matrix),
      %write(Matrix),nl,
      diag_sum(Matrix, C1, N),
      square_sum_y(Matrix, C2, N, N).
  
  % some queries i tryed out:
  % magic_square(4, [[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]]).    
  % magic_square(4, [[7, 12, 1, 14], [2, 13, 8, B4], [C1, C2, C3, C4], [D1, D2, D3, D4]]).
  % magic_square(4, [[7, A2, A3, 14], [2, B2, 8, B4], [C1, C2, 10, C4], [D1, D2, D3, 4]]).
  </code></pre>