% 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, [NP, NR, NC]),
        term_variables(SubM, Vars), 
        Vars::[0,1], 

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

        % ensure that no two numbers occupy the same square
        foreach(J in 1..NR, K in 1..NC,
                        sum([SubM[I,J,K]:I in 1..NP])$=1),

        % each end node has one connected neighbor and each interior node has two connected neighbors
        foreach(I in 1..NP, J in 1..NR, K in 1..NC,
                        [Neibs],
                        (Neibs @= [SubM[I,J1,K1] : (J1,K1) in [(J-1,K),(J+1,K),(J,K-1),(J,K+1)],
                                           (J1>=1, K1>=1, J1=<NR, K1=<NC)],
                         (InputM[J,K]=:=I->sum(Neibs) $= 1;(SubM[I,J,K] $=> sum(Neibs) $= 2)))
        ),
%    sat_solve([file('numberlink_b.cnf')],Vars),
        sat_solve(Vars),
        writeout(SubM,NP,NR,NC).
                
%write the matrix in the better format
writeout(M,NP,NR,NC):-
        foreach(I in 1..NP, [Mi],
                        (Mi @= M[I],
                         write_matrix(Mi,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
% # 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).

/*
% size 42 25
%  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  1
%  -  -  -  -  -  -  -  -  -  -  -  -  - 12  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 25  -  -  -  -  -  -  -  -  -
%  -  -  5  -  -  -  -  -  -  -  -  -  - 10  - 17 62  - 56 61 60 18  -  -  -  -  -  - 50  -  -  -  -  -  -  - 49  - 39  -  -  -
%  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 61  -  -  -  - 34  -  -  -  -  -  -  - 59  -  -  -  -  -  -  - 24  -  -
%  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 62 15 60  -  -  -  -  -  - 56  -  -  - 46  - 47  -  -  -  -  -  -  -  - 49  -
%  -  -  -  -  - 14  -  -  -  -  -  -  -  - 16 19 18  -  -  -  -  -  -  -  - 33  -  -  -  -  -  - 59  -  -  -  -  -  -  -  -  -
%  -  -  -  4  - 13  -  -  -  -  -  -  -  - 17  -  -  -  -  - 55 53  - 34  - 35  -  -  -  - 48  -  -  -  -  -  -  -  -  -  -  -
%  -  -  -  -  -  7  -  -  -  -  -  -  -  -  -  - 13  -  -  - 54  -  - 33  - 57  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%  -  -  -  -  - 12  -  -  -  -  -  -  -  -  3 41 42  -  -  - 53  - 52 32  -  -  -  -  - 57  -  -  -  -  -  -  - 47  -  -  -  -
%  -  -  -  -  - 11  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 35  -  -  -  -  - 45  -  -  - 58  -  -  -  -  -
%  -  -  -  -  - 10  -  -  -  -  -  -  -  -  -  -  -  -  - 55  -  -  -  - 21  -  -  - 51  -  -  -  - 26  -  - 46  -  -  -  -  -
%  -  -  -  -  -  - 11  5  -  -  -  -  -  -  -  -  -  -  - 19 54  -  -  -  -  -  -  -  -  -  -  -  -  -  - 58  -  -  -  -  -  -
%  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 52  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 42  -  -  -  -  -  -  - 29 45  -  -  -  -  -  -  -  -  -  -  -
%  -  -  -  -  -  9  8  6  -  -  - 16  -  -  -  -  -  -  -  -  -  -  - 32 51  -  -  -  -  -  -  -  -  -  -  - 28  -  -  -  -  -
%  -  -  -  -  -  8  -  -  -  -  -  -  -  -  -  -  - 36  -  - 38  -  -  - 44 50  - 30  -  -  -  -  -  -  -  - 27  -  -  -  -  -
%  -  -  -  -  -  -  7  -  -  -  -  -  -  -  -  -  -  - 41 22  - 22  -  -  - 43 23 31  -  -  -  -  -  -  -  - 26  -  -  -  -  -
%  -  -  -  -  -  6  -  -  -  -  -  -  -  -  -  -  -  - 36  -  - 21  -  -  - 27  -  -  -  -  -  -  -  -  -  - 25  -  -  -  -  -
%  -  -  -  -  -  -  -  -  9 15  -  - 14  -  -  -  -  - 37  - 20 44  -  -  -  -  - 43  - 31  -  -  -  -  -  - 24  -  -  -  -  -
%  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 38 39 40 28  - 30  -  -  -  -  -  - 23  -  -  -  -  -
%  -  2  -  -  -  -  -  -  -  -  -  -  -  -  -  4  -  -  -  - 20  - 37  - 48  -  -  -  - 29  -  -  -  -  -  -  -  -  -  -  -  -
%  -  -  3  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%  -  -  -  2  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 40  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
%  1  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
inputM(a(a(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1),
              a(0,0,0,0,0,0,0,0,0,0,0,0,0,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,25,0,0,0,0,0,0,0,0,0),
              a(0,0,5,0,0,0,0,0,0,0,0,0,0,10,0,17,62,0,56,61,60,18,0,0,0,0,0,0,50,0,0,0,0,0,0,0,49,0,39,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,61,0,0,0,0,34,0,0,0,0,0,0,0,59,0,0,0,0,0,0,0,24,0,0),
              a(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,62,15,60,0,0,0,0,0,0,56,0,0,0,46,0,47,0,0,0,0,0,0,0,0,49,0),
              a(0,0,0,0,0,14,0,0,0,0,0,0,0,0,16,19,18,0,0,0,0,0,0,0,0,33,0,0,0,0,0,0,59,0,0,0,0,0,0,0,0,0),
              a(0,0,0,4,0,13,0,0,0,0,0,0,0,0,17,0,0,0,0,0,55,53,0,34,0,35,0,0,0,0,48,0,0,0,0,0,0,0,0,0,0,0),
              a(0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,0,13,0,0,0,54,0,0,33,0,57,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
              a(0,0,0,0,0,12,0,0,0,0,0,0,0,0,3,41,42,0,0,0,53,0,52,32,0,0,0,0,0,57,0,0,0,0,0,0,0,47,0,0,0,0),
              a(0,0,0,0,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,35,0,0,0,0,0,45,0,0,0,58,0,0,0,0,0),
              a(0,0,0,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,55,0,0,0,0,21,0,0,0,51,0,0,0,0,26,0,0,46,0,0,0,0,0),
              a(0,0,0,0,0,0,11,5,0,0,0,0,0,0,0,0,0,0,0,19,54,0,0,0,0,0,0,0,0,0,0,0,0,0,0,58,0,0,0,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,52,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,42,0,0,0,0,0,0,0,29,45,0,0,0,0,0,0,0,0,0,0,0),
              a(0,0,0,0,0,9,8,6,0,0,0,16,0,0,0,0,0,0,0,0,0,0,0,32,51,0,0,0,0,0,0,0,0,0,0,0,28,0,0,0,0,0),
              a(0,0,0,0,0,8,0,0,0,0,0,0,0,0,0,0,0,36,0,0,38,0,0,0,44,50,0,30,0,0,0,0,0,0,0,0,27,0,0,0,0,0),
              a(0,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,0,0,41,22,0,22,0,0,0,43,23,31,0,0,0,0,0,0,0,0,26,0,0,0,0,0),
              a(0,0,0,0,0,6,0,0,0,0,0,0,0,0,0,0,0,0,36,0,0,21,0,0,0,27,0,0,0,0,0,0,0,0,0,0,25,0,0,0,0,0),
              a(0,0,0,0,0,0,0,0,9,15,0,0,14,0,0,0,0,0,37,0,20,44,0,0,0,0,0,43,0,31,0,0,0,0,0,0,24,0,0,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,38,39,40,28,0,30,0,0,0,0,0,0,23,0,0,0,0,0),
              a(0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,20,0,37,0,48,0,0,0,0,29,0,0,0,0,0,0,0,0,0,0,0,0),
              a(0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
              a(0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,40,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
              a(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
              a(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0))).

num(62).
*/
/*
% # 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).
*/
