%
% This is a little "tomography" problem, taken from an old issue
% of Scientific American.
%
% A matrix which contains zeroes and ones gets "x-rayed" vertically and
% horizontally, giving the total number of ones in each row and column.
% The problem is to reconstruct the contents of the matrix from this
% information. Sample run:
%
%	?- go.
%	    0 0 7 1 6 3 4 5 2 7 0 0
%	 0                         
%	 0                         
%	 8      * * * * * * * *    
%	 2      *             *    
%	 6      *   * * * *   *    
%	 4      *   *     *   *    
%	 5      *   *   * *   *    
%	 3      *   *         *    
%	 7      *   * * * * * *    
%	 0                         
%	 0                         
%	
%	
% Eclipse solution by Joachim Schimpf, IC-Parc
%


:- lib(ic).

go :-
	data1(RowSums, ColSums),
	solve(RowSums, ColSums, Board),
	pretty_print(RowSums, ColSums, Board).



solve(RowSums, ColSums, Board) :-
	dim(RowSums, [M]),		% get row and column dimensions
	dim(ColSums, [N]),

	dim(Board, [M,N]),		% make variables
	Board #:: 0..1,

	( for(I,1,M), param(Board,RowSums) do		% row constraints
	    sum(Board[I,*]) #= RowSums[I]
	),

	( for(J,1,N), param(Board,ColSums) do		% column constraints
	    sum(Board[*,J]) #= ColSums[J]
	).


pretty_print(RowSums, ColSums, Board) :-
	dim(Board, [M,N]),
	write("   "),
	( for(J,1,N), param(ColSums) do
	    ColSum is ColSums[J],
	    printf("%2d", ColSum)
	), nl,
	( for(I,1,M), param(RowSums,Board,N) do
	    RowSum is RowSums[I],
	    printf("%2d ", RowSum),
	    ( for(J,1,N), param(Board,I) do
		X is Board[I,J],
		( X==0 -> write("  ")
		; X==1 -> write(" *")
		;         write(" ?")
		)
	    ), nl
	), nl.


% sample data

data1([](0,0,8,2,6,4,5,3,7,0,0),	% row sums
      [](0,0,7,1,6,3,4,5,2,7,0,0)).	% column sums

data2([](10,4,8,5,6),
      [](5,3,4,0,5,0,5,2,2,0,1,5,1)).

data3([](11,5,4),
      [](3,2,3,1,1,1,1,2,3,2,1)).