So simple (in C,Java,etc,etc) but yet
so hard (in PROLOG)

Magic Squares. For those that dont know what one
is well here is a definition I grabbed off the
net:

"A magic square is an arrangement of the numbers from
1 to n^2 (n-squared) in an nxn matrix, with each number
occurring exactly once, and such that the sum of the
entries of any row, any column, or any main diagonal is
the same. It is not hard to show that this
sum must be n(n^2+1)/2."

Examples (used code below to create):
order of 3              order of 5
8 1 6                   17 24 1  8  15
3 5 7                   23 5  7  14 16
4 9 2                   4  6  13 20 22
                        10 12 19 21 3
                        11 18 25 2  9

The code below (in C) will create these magic squares
of the odd numbers.

void odd_num(int n) {
   int i,j,num=1;
   int nn=n*3/2;
   for(i=0; i < n; i++)
      for(j=0; j < n; j++)
         m[(j-i+nn)%n][(i*2-j+n)%n]=num++;

From my prolog experience I dont think this is possible
is it?

I can see how I could use recursion to do the for loops
but once i go to pop in the number I'm stuck.

Thanks for any help again

Alex

E.g.: 3x3 array: f(f(_,_,_),f(_,_,_),f(_,_,_)).

A generic access predicate for twodimensional `arrays':
access(X,Y,Term,Arg) :-
   arg(X,Term,Ys),
   arg(Y,Ys,Arg).

It gets more complicated if you need to be able to alter values as
well.

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord/

I'll *try* to figure that stuff out :o)

Thanks

Alex

A = f(1, 2, 3)
B = f(4, 5, 6)
C = f(7, 8, 9)

Yes
?-

Okay, so thats perfect.
But I still have one problem, which is getting values
into the functor.

Going back to my original problem of the magic squares.

I still dont know how to get values INTO the 'array'.

Like, how do I start with a empty 3x3 array and place
values into it, say put 1 into f(1,2) and 5 into
f(3,2) and so on.  Using my formula to calculate where
the values for the magic square go.

Could I have something like this:

magic(N, f(f(_,_,_),f(_,_,_),f(_,_,_))) :- A = 5, B=1,C=2,
                        insert( A , f, B, C).
% insert 5 into f(1,2) like
% f(f(_,5,_),f(_,_,_),f(_,_,_))

insert(A, f, B, C) :- I dont even know where to start

So then my magic sqaures would look something like this:
/*************************************************/
/* C code of what I want to accomplish           */
/*                                               */
/* void odd_num(int n) {                         */
/*   int i,j,num=1;                              */
/*   int nn=n*3/2;                               */
/*   for(i=0; i < n; i++)                     */
/*      for(j=0; j < n; j++)                  */
/*         m[(j-i+nn)%n][(i*2-j+n)%n]=num++;     */
/* }                                             */
/*************************************************/

magic(N , f) :-         NN is (N*3/2),
                        Num is Num+1,
                        I <= N,
                        I is I+1,
                        J <= N,
                        J is J+1,
                        magic(N,f), % to do first loop
                        magic(N,f), % to do second loop
                        S1 is ((j-i+nn) mod n),
                        S2 is ((i*2-j+n) mod n),
                        insert(Num, f, S1, S2).

Thats my basic idea.  I know it dont work :o(
Also what is mod (remainder) in prolog?

Damn, the more I think the more questions

Thanks

Alex

What if you base your array structure as the following..

makelist(0,[]) :- !.

makelist(Dim, [[]|MoreList]) :- !, DimLeft is Dim - 1,
                                makelist(Dim,MoreList).

createarray([],[]).

createarray([Dim],[Array]) :- !, makelist(Dim,Array).

createarray([Dim|MoreDim], [Front|Array]) :- !, makelist(Dim,Front),
                                        createarray(MoreDim,Array).

this would create an `empty' array comprised of `lists-of-lists' that can
represent the data.

for example, to create a 3 x 3 array, one would do.

createarray([3,3],X).

X = [ [ [], [], [] ] , [ [], [], [] ] ]

that could be used to put in numbers in random spots...

suppose F=f(f(_,_,_),f(_,_,_),f(_,_,_)), then

access(1,3,F,27) will bind F to:

F=f(f(_,_,27),f(_,_,_),f(_,_,_))

etc.

but, reading an introductory book on Prolog might be the best way
to proceed. In the old days, there used to be buildings (called
`libraries') where you could read books (almost) for free...

Gj

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord/

Alex asked :
...

Its not obvious, but its easy when you know how.

If you have a magic square three columns wide,
lets use variables "A1, A2, A3, B1, B2, B3, C1, C2, C3"
for the 9 positions.

Like this :-

number( 0 ).
number( 1 ).
number( 2 ).
number( 3 ).
number( 4 ).
number( 5 ).
number( 6 ).
number( 7 ).
... etc. ...
number( 15 ).

find_all_possible_numbers :-
    number( A1 ),
    number( A2 ),
    number( A3 ),
    number( B1 ),
    number( B2 ),
    number( B3 ),
    number( C1 ),
    number( C2 ),
    number( C3 ),
    % Now write the numbers.
    nl,
    write( A1, ' ', A2, ' ', A3 ),
    write( B1, ' ', B2, ' ', B3 ),
    write( C1, ' ', C2, ' ', C3 ),
    % Now go on to find the next set of numbers.
    fail.

% Now write "Finished."
find_all_possible_numbers :-
    n,
    write( 'Finished.' ).

/*
Now you need to write a similar program,
but exclude most combinations of numbers,
so only valid magic squares are printed.
Something like this :
*/

program :-
    number( A1 ),
    number( A2 ),
    number( A3 ),
    number( B1 ),
    number( B2 ),
    number( B3 ),
    number( C1 ),
    number( C2 ),
    number( C3 ),
    % Add up the numbers.
    Row_A_total is A1 + A2 + A3,
    Row_B_total is B1 + B2 + B3,
    Row_C_total is C1 + C2 + C3,

    % Fail if the totals are not equal.
    Row_A_total == Row_B_total,
    Row_A_total == Row_C_total,

    % Now write the numbers.
    nl,
    write( A1, ' ', A2, ' ', A3 ),
    write( B1, ' ', B2, ' ', B3 ),
    write( C1, ' ', C2, ' ', C3 ),
    % Now go on to find the next set of numbers.
    fail.
program :-
    n,
    write( 'Finished.' ).

/* You also need to allow for column totals,
to make sure they are all identical too.
So put this code in the program too :

    Column_1_total is A1 + B1 + C1,
    Column_2_total is A2 + B2 + C2,
    Column_3_total is A3 + B3 + C3,
    Column_1_total == Row_A_total,
    Column_2_total == Row_A_total,
    Column_3_total == Row_A_total,

Then do the diagonals in a similar way.

Diagonal_1 is A1 + B2 + C3,
Diagonal_2 is A3 + B2 + C1,
Diagonal_1 == Row_A_total,
Diagonal_2 == Row_B_total,

*/

/*
This is quite simple.
But I really don't know how to make a version
to find magic squares of any size.

I'd need to write a different program for each size of square.
*/

By the way, you can't learn Prolog from the web!
I strongly recommend this book as your first book on Prolog :
"Prolog Programming for Artificcial Intelligence" by Ivan Bratko,
published by Addison-Wesley, in paperback.

    Martin Sondergaard,
    London.

[snipped]

    odd_num(N):-
        N1 = N - 1,
        NN = N * 3 // 2,
        for(0,N1,I),  % row
            for(0,N1,J),  % column
                I1 is (J - I + NN) mod N,  % row offset
                J1 is (I * 2 -J + N) mod N,  % column offset
                Num is I * N + J + 1,  % offset cell's value
                assert(cell(I1,J1,Num)),
            next(J,N1),
        next(I,N1).
    odd_num(_).

    for(N,_,N).
    for(Start,Stop,NumOut):-
        Start1 is Start + 1,
        Start1 =< Stop,
        for(Start1,Stop,NumOut).

     next(X,X).

1. Single elements: cell(Row,Col,Value)
2. Row elements: row(Row,ColumnValues)
3. Whole array: array(Cells)

and variations of these. Which one of these you choose to use will primarily
depend upon how values are to be accessed. Single elements are interesting when
you often need to access single cells, row elements and the whole array when you
often operate on groups of cells.

BTW, there's nothing "random" about calculating an offset.

[snipped]

To display your array you would implement something like this:

    print_array(N):-
        N1 = N - 1,
        for(0,N1,I),  % row
            nl,
            for(0,N1,J),  % column
                retract(cell(I,J,V)),
                justify(V,Spaces),
                write(Spaces), write(V), write(' '),
            next(J,N1),
        next(I,N1).
    print_array(_):-
        nl, nl.

    justify(N,'   '):- N < 10, !.
    justify(N, '  '):- N < 100, !.
    justify(N,  ' '):- N < 1000, !.
    justify(_,   '').

To tie it all together:

    magic_square(N):-
        (0 is N mod 2
         -> fail
         ;  odd_num(N),
            print_array(N)
        ).

And, finally, to run a query:

    | ?- magic_square(11).

Well, that's a solution for magic squares of odd orders out of the way. It
becomes slightly more interesting with even orders.

Daniel

    (N^3 + N) / 2

where N is the magic square's order and ^ is "to the power of".

[snipped]

Daniel

In the following I will give a translation of the definition above for
magic-squares of size 3. This code can easily be extended to an
arbitrary problem-size.

magicsquare3(Mss) :-
        magicsquare3_(Mss, Zs),
        labeling([ffc], Zs).

magicsquare3_([[M11,M12,M13],[M21,M22,M23],[M31,M32,M33]], Zs) :-
        Zs = [M11,M12,M13,M21,M22,M23,M31,M32,M33],
        domain(Zs, 1, 9),
        all_different(Zs),
        M11+M12+M13 #= Sum,             % rows
        M21+M22+M23 #= Sum,
        M31+M32+M33 #= Sum,
        M11+M21+M31 #= Sum,             % columns
        M12+M22+M32 #= Sum,
        M13+M23+M33 #= Sum,
        M11+M22+M33 #= Sum,             % diagonals
        M31+M22+M13 #= Sum,
        Sum #= 15.                      

Using Prolog (and clpfd) you can not only generate one solution, but also:
        . check if some given square is a magic square.
        . work with partial instatiation (some parts of the square are
                already known, others are still unknown).
        . "create" all solutions to the problem.

If you want to do the same in C, you would have to implement some
algorithm for constraint-satisfaction search (+ backtracking).

Conclusion:
        . Think about the various relations that can be identified.
          Think of WHAT you want to express.
          Do not think of HOW this should be executed by the computer.
          (Remember: Prolog is a declarative language, not an imperative one)

        . Do NOT try to translate a program from C or another imperative
          language. This will almost always be a waste of time.

        . Do NOT use: fail, assert, retract, write, format, !, functor, arg.
          This list is -- of course -- incomplete...
          Some of these "predicates" require profund knowledge of
          prolog-internals. Others indicate a poor programming-style.

ciao,
Stefan

[snipped]

Daniel

ciao,
Stefan

Perhaps it's time to throw your blinkers/blinders away?

Daniel

|> Oh no, not another person with blinkers/blinders? A person with previous
|> programming experience in an imperative programming language will quickly find
|> him/herself "at home" by first reviewing the procedural aspects of the Prolog
|> language.

Let me try to see whether I understand this by putting it in a different context ...

A person with previous programming experience in assembly language programming, when
introduced to Pascal, will quickly find him/herself "at home" by first reviewing the
Pascal "goto" statement.

Yeah, sounds very reasonable to me.

Of course, you'll have to spend a lifetime later to explain that goto is considered harmful ...

And when a Brittish person starts to drive in Belgium, why not let him drive on the left
side for a while, so that he feels "at home" at first. Maybe he should also wear
blinkers/blinders at the beginning - just a matter of ignoring better what's going on in the
rest of the world.

Oh, and while we are at it, the preferred way to teach parachute jumping to a benjee jumper,
is of course to tie the parachute to his feet - this way is much more familiar to him !

Cheers

Bart Demoen

It is thus evident that the "core parts" MUST be taught/learned first.
You certainly agree with me that the imperative parts are not a
part of the "core" of prolog.

ciao,
Stefan