1. CSPlib
  2. Problems
  3. prob019
  4. Models
  5. magic_square_bp.pl

019: Magic Squares and Sequences

Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
 
  Magic squares in B-Prolog.
 
 
 
  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my B-Prolog page: http://www.hakank.org/bprolog/
 
*/
 
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
%
% Reporting both time and backtracks
%
time2(Goal):-
        cputime(Start),
        statistics(backtracks, Backtracks1),
        call(Goal),
        statistics(backtracks, Backtracks2),
        cputime(End),
        T is (End-Start)/1000,
        Backtracks is Backtracks2 - Backtracks1,
        format('CPU time ~w seconds. Backtracks: ~d\n', [T, Backtracks]).
 
%
% Simple run
%
go :-
        time2(magic(5,_Square)).
 
%
% Run for different sizes
%
% ff/updown solves N=6 in 0.06s and 6856 backtracks
%                   10 in 2.99s and 289939 backtracks
% ffd/updown solves N=10 in 2.37s and 306336 backtracks
go2 :-
        foreach(N in 3..11, [Square], time2(magic(N,Square))).
 
 
%
% All solutions.
%
go3 :-
        N = 4,
        findall(Square,magic(N,Square),L),
        length(L,Len),
        writeln('Len':Len).
 
 
 
 
magic(N,Square) :-
        format('\n\nN: ~d\n', [N]),
        NN is N*N,
        Sum is N*(NN+1)//2,% magical sum
        format('Sum = ~d\n', [Sum]),
 
        new_array(Square,[N,N]),
        array_to_list(Square, Vars),
        Vars :: 1..NN,
 
        alldifferent(Vars),
        foreach(I in 1..N,
                (
                    Sum #= sum([ T : J in 1..N, [T], T @= Square[I,J]]),% rows
                    Sum #= sum([ T : J in 1..N, [T], T @= Square[J,I]]) % column
                )
        ),
 
        Sum #= sum(Square^diagonal1),% diagonal sums
        Sum #= sum(Square^diagonal2),% diagonal sums
 
        % Symmetry breaking
        Square[1,1] #< Square[1,N],
        Square[1,1] #< Square[N,N],
        Square[1,1] #< Square[N,1],
        Square[1,N] #< Square[N,1],
 
        labeling([ffd,updown],Vars),
        print_square(Square).
 
 
 
print_square(Square) :-
        N is Square^length,
        foreach(I in 1..N,
                (
                foreach(J in 1..N,
                        [S],
                        (
                            S @= Square[I,J],
                            format('~3d', [S])
                        )
                       ),
                nl
                )
               ),
        nl.