% COMP30020 - Declarative Programming 2017 Semester 2
% Written by Jie Jenny Yan - 693839

% Written for the purpose of solving maths puzzles.
% A maths puzzle is a square grid of squares, each to be filled in
% with a single digit from 1 to 9. It must satisfy the following
% constraints:
%  - each row and each column contains no repeated digits
%  - all squares on the diagonal line from upper left to lower right
%    contain the same value
%  - the heading of each row and column (leftmost square in a row and topmost
%    square in a column) holds either the sum or the product of all the digits
%    in that row or column
% This program solves this puzzle and filles in the blanks (finds the values
% that satisfy the above mentioned conditions) and produces a solution ONLY if
% one solution for that puzzle exists.
% (We assume that the row and column headings are not considered to be part of
% the row or column and so do not need to conform to the first 2 conditions.

:- use_module(library(clpfd)).
:- ensure_loaded(library(clpfd)).

% puzzle_solution takes a list of lists (size N x N) and checks whether
% the puzzle satisfies each of the conditions of a maths puzzle.
puzzle_solution(Puzzle) :-
    Puzzle = [_|Tail],
    check_diagonal(_, 1, Tail),
    maplist(check, Tail),
    transpose(Puzzle, [_|Columns]),
    maplist(check, Columns),
    maplist(label, Puzzle).

% checks whether the diagonal digits all have the same value
% base case: each list in the list of lists has been checked
% recurse over the list of lists, checking each diagonal element, starting
% at index 1 of the first row since index 0 refers to the row header
check_diagonal(_, _, []).
check_diagonal(Diag, N, [Head|Tail]) :-
    N0 is N + 1,
    get_diag_elem(Head, N, Diag),
    check_diagonal(Diag, N0, Tail).

% helper function that gets the diagonal element of a particular row at
% index 'N' and checks that this value is equal to our first diagonal element
get_diag_elem( [Head|_], 0, Head).
get_diag_elem( [_|Tail], N, Diag):-
    N0 is N - 1,
    get_diag_elem(Tail, N0, Diag).

% checking if all Tail elements are distinct and whether the sum or prod
% of the tail is equal to their respective head values, where head is the
% first element in the given list and tail is the remaining elements.
check([Head|Tail]) :-
    (sum_list(Tail, Head); prod_list(Tail, Head)),
    all_distinct(Tail).

% checks if the sum of a list matches the given sum value (row/col header)
sum_list(List, Sum) :-
    sum_list(List, 0, Sum).

% recursively adds the elements to sum0 (initial sum), until we have
% cycled through all elements in the list and checks that the final sum matches
% our given sum (row/col header)
sum_list([], Sum, Sum).
sum_list([Head|Tail], Sum0, Sum) :-
    between(1,9,Head),
    Sum1 is Sum0 + Head,
    sum_list(Tail, Sum1, Sum).

% similar to the sum_list function, prod_list checks if the prod of the list
% matches the given prod value (row/col header)
prod_list(List, Sum) :-
    prod_list(List, 1, Sum).

% recursively multiplies the elements to prod0 (initial prod), until we have
% cycled through all elements in the list and checks that the final prod
% matches our given prod (row/col header)
prod_list([], Prod, Prod).
prod_list([Head|Tail], Prod0, Prod) :-
    between(1,9,Head),
    Prod1 is Prod0 * Head,
    prod_list(Tail, Prod1, Prod).