% % 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)).