home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / EXAMPLES / MAGIC.LF < prev    next >
Text File  |  1996-06-04  |  2KB  |  83 lines
  1. % Copyright 1992 Digital Equipment Corporation
  2. % All Rights Reserved
  3. % Author: Hassan Ait-Kaci
  4.  
  5. % This is a magic square solver. It generates a size x size square of
  6. % numbers forming a permutation of [1,size*size] such that all rows, all
  7. % columns, and both diagonals, sum up to the same total.
  8. % Execute the query 'magic ?' or 'magic(S) ?' where S is an optional size
  9. % parameter.
  10.  
  11. module("magic") ?
  12. public(magic) ?
  13.  
  14.  
  15. n_th(1,[H|T]) -> H.
  16. n_th(N:int,[_|T]) -> n_th(N-1,T).
  17.  
  18. car([H|T]) -> H.
  19. cdr([H|T]) -> T.
  20.  
  21. dynamic(size)?    % size may be specified dynamically.
  22. size -> 3.    % default size is 3.
  23.  
  24. grid -> square(size).
  25.  
  26. vector(0) -> [].
  27. vector(N:int) -> [int|vector(N-1)].
  28.  
  29. square(0) -> [].
  30. square(N:int) -> [vector(size)|square(N-1)].
  31.  
  32. transpose([[]|list]) -> [].
  33. transpose(S) -> [map(car,S)|transpose(map(cdr,S))].
  34.  
  35. entries(S) -> reduce(append,[],S).
  36.  
  37. diag([]) -> [].
  38. diag([Row|Rows],N:int,Next) -> [n_th(N,Row)|diag(Rows,Next(N),Next)].
  39.  
  40. incr(N:int) -> N+1.
  41. decr(N:int) -> N-1.
  42.  
  43. diag_dn(S) -> diag(S,1,incr).
  44. diag_up(S) -> diag(S,size,decr).
  45.  
  46. all_different([]) :- !.
  47. all_different([H|T]) :-
  48.     0<H, H=<size*size,
  49.     out_of(H,T),
  50.     all_different(T).
  51.  
  52. out_of(H,[]) :- !.
  53. out_of(H,[A|T]) :- A =\= H, out_of(H,T).
  54.  
  55. all_equal([]) :- !.
  56. all_equal([H|T],H) :- all_equal(T,H).
  57.  
  58. sum_up(L) -> reduce((+),0,L).
  59.  
  60. number -> number_to(size*size).
  61. number_to(N:int) -> cond(N < 1, {}, {1;1+number_to(N-1)}).
  62.  
  63. assign_numbers([]) :- !.
  64. assign_numbers([number|L]) :- assign_numbers(L).
  65.  
  66. display_square([]) :- !.
  67. display_square([Row|Rows]) :- nl, display_row(Row), display_square(Rows).
  68.  
  69. display_row([]) :- nl,!.
  70. display_row([N|T]) :- write("    ",N),display_row(T).
  71.  
  72. magic(S:{size;int}) :-
  73.     !,
  74.     setq(size,S),
  75.     all_different(Entries:entries(Square:grid)),
  76.     Total = S*(S*S+1)/2,
  77.     Total:sum_up(diag_dn(Square)) = sum_up(diag_up(Square)),
  78.     all_equal(map(sum_up,Square),Total),
  79.     all_equal(map(sum_up,transpose(Square)),Total),
  80.     assign_numbers(Entries),
  81.     display_square(Square),
  82.     nl, write("Magic Total = ",Total), nl.
  83.