% by Neng-Fa Zhou & Wen Wei Rong, March 2012

go:-
        inputM(InputM),
        num(NP),                  % number of pairs
        NR is InputM^length,      % number of rows
        NC is InputM[1]^length,   % number of columns
        subMat(NP,NR,NC,InputM).

subMat(NP, NR, NC, InputM):-
        new_array(SubM, [NR, NC]),
        term_variables(SubM, Vars), 
        Vars::1..NP, 

        % initialize preoccupied squares
        foreach(I in 1..NR, J in 1..NC,
                        (InputM[I,J]=\=0 -> SubM[I,J] @= InputM[I,J]; true)),

        % each end node has one connected neighbor and each interior node has two connected neighbors
        foreach(J in 1..NR, K in 1..NC,
                        (InputM[J,K]=\=0->
                             sum([if(SubM[J1,K1]$=SubM[J,K],1,0) :
                                          (J1,K1) in [(J-1,K),(J+1,K),(J,K-1),(J,K+1)],
                                          (J1>=1, K1>=1, J1=<NR, K1=<NC)])$= 1
                         ;
                             sum([if(SubM[J1,K1]$=SubM[J,K],1,0) :
                                          (J1,K1) in [(J-1,K),(J+1,K),(J,K-1),(J,K+1)],
                                          (J1>=1, K1>=1, J1=<NR, K1=<NC)])$= 2
                        )
        ),
%        cp_solve([format(clp),file('test.pl')],Vars),
        sat_solve(Vars),
        write_matrix(SubM,NR,NC).
                
write_matrix(M,NR,NC):-
        foreach(I in 1..NR, J in 1..NC, [Mij],
                        (Mij @= M[I,J], write(Mij), write(' '),
                         (J==NC->nl;true))),
        nl,nl.

% # Numberlink Puzzle
% # Author: Otto Janko
% # Source: http://www.janko.at/Raetsel/
% # URL: http://www.janko.at/Raetsel/Arukone/109.a.htm
% size 10 10
%  -  -  -  6  -  -  -  -  -  -
%  -  -  -  -  -  -  -  -  -  -
%  -  -  5  -  1  4  -  3  -  -
%  -  -  -  -  3  -  -  8  -  -
%  -  2  -  2  -  -  -  -  -  -
%  -  4  -  8  -  7  -  -  -  -
%  -  -  -  -  -  -  -  -  -  -
%  -  -  5  -  6  1  -  7  -  -
%  -  -  -  -  -  -  -  -  -  -
%  -  -  -  -  -  -  -  -  -  -
inputM(a(a(0,0,0,6,0,0,0,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0),
              a(0,0,5,0,1,4,0,3,0,0),
              a(0,0,0,0,3,0,0,8,0,0),
              a(0,2,0,2,0,0,0,0,0,0),
              a(0,4,0,8,0,7,0,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0),
              a(0,0,5,0,6,1,0,7,0,0),
              a(0,0,0,0,0,0,0,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0))).

num(8).
/*
% # Numberlink Puzzle
% # Author: The Afis Project
% # Source: http://www.afis.to/~start/
% # URL: http://www.janko.at/Raetsel/Arukone/001.a.htm
% size 5 5
%  3  -  -  -  2
%  4  1  2  -  -
%  -  -  -  3  -
%  -  -  -  -  -
%  4  -  -  -  1


inputM(a(a(3,0,0,0,2),
          a(4,1,2,0,0),
          a(0,0,0,3,0),
          a(0,0,0,0,0),
          a(4,0,0,0,1))).
num(4).
*/

/*
inputM(a(a(1,0),
         a(2,0),
         a(2,1))).

num(2).
*/