/*
Example 2: 2D array implemention.

B. Ross, Brock University, 2002

The table is a set of structures - rows, cols, diags.
Elements in these structures are logic variables, which are shared
amongst them. This permits instantaneous setting of table values.

This approach is most useful when table entries are unified during Prolog
search. 
*/

% magic_square: returns a 3x3 magic square of unique integers between 1 and 9
% such that all rows, columns, and diagonals add up to the same value.
% The result is printed to the screen as well.

magic_square(Rows) :-
	table(Rows, Cols, Diags),
	set3sets(Rows, [1,2,3,4,5,6,7,8,9], Nums2, Sum),
	set3sets(Cols, Nums2, Nums3, Sum),
	set2sets(Diags, Nums3, _, Sum),
	print_square(Rows).

% table(Rows, Cols, Diags) is the template for the table.
% Note that the internal structures, eg. row 1 [A1, B1, C1], do not really
% use the list notation within the rest of this application, since list
% processing is never performed on them. A structure such as (A1, B1, C1) 
% would be just as useful, if not somewhat more efficient.

table([ [A1, B1, C1],  % rows
	[A2, B2, C2],
	[A3, B3, C3]],
      [ [A1, A2, A3],  % cols
	[B1, B2, B3],
	[C1, C2, C3]],
      [ [A1, B2, C3], % diags
	[A3, B2, C1]]
	).


% set3sets will unify values into 3 rows or diagonals, such that
% they all add up to Sum.
% set2sets is similar, but it works for the 2 diagonals.

set3sets([R1, R2, R3], Nums, Nums4, Sum) :-
	set(R1, Nums, Nums2, Sum),
	set(R2, Nums2, Nums3, Sum),
	set(R3, Nums3, Nums4, Sum).
set2sets([R1, R2], Nums, Nums3, Sum) :-
	set(R1, Nums, Nums2, Sum),
	set(R2, Nums2, Nums3, Sum).

% set takes a row, col, or diag, and places unique integers into spare
% places (it leaves alone values already there). It then adds up the
% values and unifies with Sum (which may or may not succeed).

set([A, B, C], Nums, Nums4, Sum) :-
	test_and_set(A, Nums, Nums2),
	test_and_set(B, Nums2, Nums3),
	test_and_set(C, Nums3, Nums4),
	Sum is A+B+C.

% test_and_set(V, Nums, Nums2): if V is an uninstantiated variable, then 
% it is unified with a value from Nums. Nums2 is Nums with that value removed.
% Backtracking will unify with other values from Nums.
% However, if V has a value already, it is left alone, and Nums is unchanged.

test_and_set(V, Nums, Nums2) :-
	var(V),
	!,
	remove(V, Nums, Nums2).
test_and_set(_, Nums, Nums).

% remove(A, L, L2): remove a value A from list L, resulting in L2.

remove(A, [A|L], L).
remove(A, [B|L], [B|L2]) :- remove(A, L, L2).

% write the table to screen, row by row...

print_square([]) :- nl.
print_square([R|L]) :-
	write(R),
	nl,
	print_square(L).