/* Projet PROLOG IIE, 2A par Yoann GUILLOT */
/* K est le reste de la division de D par R */
reste(D, D, R) :- D<R, !.
reste(K, D, R) :- D>=R, DD is D-R, reste(K, DD, R).

quot(0, D, R) :- D<R, !.
quot(K, D, R) :- DD is D-R, quot(Q, DD, R), K is Q+1.

/* cree une liste de 0 */
init(0, []) :- !.
init(I, [0|C]) :- J is I-1, init(J, C).

/* rang(valeur, pos, liste): verifie que le POSe element de la liste est VALEUR */
rang(E, 1, [E|_]) :- !.
rang(E, P, [_|C]) :- PP is P-1, rang(E, PP, C).

/* remplace un element d'une liste */
placer(X, 1, [_|C], [X|C]) :- !.
placer(X, P, [E|C1], [E|C2]) :- PP is P-1, placer(X, PP, C1, C2).

/* suiv(depart, cote, suivant): donne le rang du suivant toroidalement */
suiv(RD, N, RS) :- reste(0, RD, N), N*N<RD+1, !, RS is RD+1-N*N.
suiv(RD, N, RS) :- reste(0, RD, N), !, RS is RD+1.
suiv(RD, N, RS) :- N*N<RD+N+1, !, RS is RD+N+1-N*N.
suiv(RD, N, RS) :- RS is RD+N+1.

/* donne la position suivante (suiv si la case est vide, +2col sinon) */
possuiv(RD, N, C, RS) :- suiv(RD, N, RS), rang(0, RS, C), !.
possuiv(RD, N, _, RS) :- RD<N*N-2*N, !, RS is RD+2*N.
possuiv(RD, N, _, RS) :- RS is RD+2*N-N*N.

/* construc(num, pos, cote, liste, resultat): construit le carre magique */
construc(I, _, N, C, C) :- I>N*N, !.
construc(I, RD, N, CI, CM) :- possuiv(RD, N, CI, RS), placer(I, RS, CI, CT), J is I+1, construc(J, RS, N, CT, CM).

/* affichage du carre */
vue(_, [], _) :- !.
vue(I, [E|C], N) :- reste(0, I, N), !, write(E), nl, J is I+1, vue(J, C, N).
vue(I, [E|C], N) :- write(E), write(' '), J is I+1, vue(J, C, N).

/* predicat principal */
magik(P) :- N is P*2+1, M is N*N, quot(RD, (N+1)*(N-1), 2), init(M, CI), construc(1, RD, N, CI, CM), vue(1, CM, N).

/* exemple: | ?- magik(4).
37 78 29 70 21 62 13 54 5
6 38 79 30 71 22 63 14 46
47 7 39 80 31 72 23 55 15
16 48 8 40 81 32 64 24 56
57 17 49 9 41 73 33 65 25
26 58 18 50 1 42 74 34 66
67 27 59 10 51 2 43 75 35
36 68 19 60 11 52 3 44 76
77 28 69 20 61 12 53 4 45
*/