% http://www.cs.kuleuven.be/~dtai/events/ASP-competition/Benchmarks/HamiltonianPath.html
% adapted by Neng-Fa Zhou
:-include(base).

solve(As):-
    (member(start(S),As)->true;true),
    findall(V,member(vtx(V),As),Vs),
    findall(edge(X,Y),member(edge(X,Y),As),Es),
    map(Vs,1,_,MapVs),
    length(Vs,Len),
    functor(Vector,v,Len),
    Vector=..[_|Vars],
    create_domains(Vs,Vector,S,Es,MapVs),
    circuit(Vars),
    labeling([ff],Vars),!,
    output(S,Vars,MapVs,Len).
solve(_):-
    format("UNSATISFIABLE~n").


create_domains([],_,_,_,_).
create_domains([X|Xs],Vector,Start,Es,MapVs):-
    findall(Y,member(edge(X,Y),Es),Ys),
    (X==Start->Ys1=Ys;Ys1=[Start|Ys]),
    map(Ys1,D,MapVs),
    map(X,I,MapVs),
    arg(I,Vector,Var),
    Var :: D,
    create_domains(Xs,Vector,Start,Es,MapVs).

output(_From,_Vars,_MapVs,1):-!.
output(From,Vars,MapVs,Count):-
    map(From,I,MapVs),
    element(K,Vars,I),  % the Kth element of Vars is I
    map(To,K,MapVs),
    format("path(~w,~w). ",[From,To]),
    Count1 is Count-1,
    output(To,Vars,MapVs,Count1).


test:-
    solve([vtx(v1),vtx(v2),vtx(v3),vtx(v4),vtx(v5),vtx(v6),vtx(v7),vtx(v8),vtx(v9),vtx(v10),vtx(v11),vtx(v12),vtx(v13),vtx(v14),vtx(v15),vtx(v16),vtx(v17),vtx(v18),vtx(v19),vtx(v20),vtx(v21),vtx(v22),vtx(v23),vtx(v24),vtx(v25),vtx(v26),vtx(v27),vtx(v28),vtx(v29),vtx(v30),vtx(v31),vtx(v32),vtx(v33),vtx(v34),vtx(v35),vtx(v36),vtx(v37),vtx(v38),vtx(v39),vtx(v40),vtx(v41),vtx(v42),vtx(v43),vtx(v44),vtx(v45),vtx(v46),vtx(v47),vtx(v48),vtx(v49),vtx(v50),vtx(v51),vtx(v52),vtx(v53),vtx(v54),vtx(v55),vtx(v56),vtx(v57),vtx(v58),vtx(v59),vtx(v60),edge(v1,v5),edge(v1,v11),edge(v1,v12),edge(v1,v17),edge(v1,v22),edge(v1,v24),edge(v1,v30),edge(v2,v3),edge(v2,v7),edge(v2,v13),edge(v2,v15),edge(v3,v2),edge(v3,v6),edge(v3,v7),edge(v3,v8),edge(v3,v15),edge(v3,v26),edge(v4,v13),edge(v4,v14),edge(v4,v18),edge(v4,v22),edge(v4,v24),edge(v4,v27),edge(v5,v1),edge(v5,v18),edge(v5,v19),edge(v5,v22),edge(v5,v23),edge(v6,v3),edge(v6,v9),edge(v6,v10),edge(v6,v15),edge(v6,v18),edge(v6,v21),edge(v6,v26),edge(v7,v2),edge(v7,v3),edge(v7,v8),edge(v7,v13),edge(v7,v25),edge(v7,v29),edge(v7,v51),edge(v8,v3),edge(v8,v7),edge(v8,v10),edge(v8,v26),edge(v8,v29),edge(v9,v6),edge(v9,v18),edge(v9,v20),edge(v9,v21),edge(v9,v23),edge(v10,v6),edge(v10,v8),edge(v10,v20),edge(v10,v21),edge(v10,v26),edge(v10,v28),edge(v10,v29),edge(v11,v1),edge(v11,v12),edge(v11,v13),edge(v11,v25),edge(v11,v28),edge(v12,v1),edge(v12,v11),edge(v12,v13),edge(v12,v14),edge(v12,v17),edge(v13,v2),edge(v13,v4),edge(v13,v7),edge(v13,v11),edge(v13,v12),edge(v13,v14),edge(v13,v15),edge(v13,v18),edge(v13,v25),edge(v14,v4),edge(v14,v12),edge(v14,v13),edge(v14,v17),edge(v14,v27),edge(v14,v30),edge(v15,v2),edge(v15,v3),edge(v15,v6),edge(v15,v13),edge(v15,v18),edge(v16,v19),edge(v16,v20),edge(v16,v23),edge(v17,v1),edge(v17,v12),edge(v17,v14),edge(v17,v30),edge(v18,v4),edge(v18,v5),edge(v18,v6),edge(v18,v9),edge(v18,v13),edge(v18,v15),edge(v18,v22),edge(v18,v23),edge(v19,v5),edge(v19,v16),edge(v19,v23),edge(v20,v9),edge(v20,v10),edge(v20,v16),edge(v20,v21),edge(v20,v23),edge(v21,v6),edge(v21,v9),edge(v21,v10),edge(v21,v20),edge(v22,v1),edge(v22,v4),edge(v22,v5),edge(v22,v18),edge(v22,v24),edge(v23,v5),edge(v23,v9),edge(v23,v16),edge(v23,v18),edge(v23,v19),edge(v23,v20),edge(v24,v1),edge(v24,v4),edge(v24,v22),edge(v24,v27),edge(v24,v30),edge(v25,v7),edge(v25,v11),edge(v25,v13),edge(v25,v28),edge(v25,v29),edge(v26,v3),edge(v26,v6),edge(v26,v8),edge(v26,v10),edge(v27,v4),edge(v27,v14),edge(v27,v24),edge(v27,v30),edge(v28,v10),edge(v28,v11),edge(v28,v25),edge(v28,v29),edge(v29,v7),edge(v29,v8),edge(v29,v10),edge(v29,v25),edge(v29,v28),edge(v30,v1),edge(v30,v14),edge(v30,v17),edge(v30,v24),edge(v30,v27),edge(v31,v35),edge(v31,v41),edge(v31,v42),edge(v31,v47),edge(v31,v52),edge(v31,v54),edge(v31,v60),edge(v32,v33),edge(v32,v37),edge(v32,v43),edge(v32,v45),edge(v33,v32),edge(v33,v36),edge(v33,v37),edge(v33,v38),edge(v33,v45),edge(v33,v56),edge(v34,v43),edge(v34,v44),edge(v34,v48),edge(v34,v52),edge(v34,v54),edge(v34,v57),edge(v35,v31),edge(v35,v48),edge(v35,v49),edge(v35,v52),edge(v35,v53),edge(v36,v33),edge(v36,v39),edge(v36,v40),edge(v36,v45),edge(v36,v48),edge(v36,v51),edge(v36,v56),edge(v37,v32),edge(v37,v33),edge(v37,v38),edge(v37,v43),edge(v37,v55),edge(v37,v59),edge(v38,v33),edge(v38,v37),edge(v38,v40),edge(v38,v56),edge(v38,v59),edge(v39,v36),edge(v39,v48),edge(v39,v50),edge(v39,v51),edge(v39,v53),edge(v40,v36),edge(v40,v38),edge(v40,v50),edge(v40,v51),edge(v40,v56),edge(v40,v58),edge(v40,v59),edge(v41,v31),edge(v41,v42),edge(v41,v43),edge(v41,v55),edge(v41,v58),edge(v42,v31),edge(v42,v41),edge(v42,v43),edge(v42,v44),edge(v42,v47),edge(v43,v32),edge(v43,v34),edge(v43,v37),edge(v43,v41),edge(v43,v42),edge(v43,v44),edge(v43,v45),edge(v43,v48),edge(v43,v55),edge(v44,v34),edge(v44,v42),edge(v44,v43),edge(v44,v47),edge(v44,v57),edge(v44,v60),edge(v45,v32),edge(v45,v33),edge(v45,v36),edge(v45,v43),edge(v45,v48),edge(v46,v6),edge(v46,v49),edge(v46,v50),edge(v46,v53),edge(v47,v31),edge(v47,v42),edge(v47,v44),edge(v47,v60),edge(v48,v34),edge(v48,v35),edge(v48,v36),edge(v48,v39),edge(v48,v43),edge(v48,v45),edge(v48,v52),edge(v48,v53),edge(v49,v35),edge(v49,v46),edge(v49,v53),edge(v50,v39),edge(v50,v40),edge(v50,v46),edge(v50,v51),edge(v50,v53),edge(v51,v36),edge(v51,v39),edge(v51,v40),edge(v51,v50),edge(v52,v31),edge(v52,v34),edge(v52,v35),edge(v52,v48),edge(v52,v54),edge(v53,v35),edge(v53,v39),edge(v53,v46),edge(v53,v48),edge(v53,v49),edge(v53,v50),edge(v54,v31),edge(v54,v34),edge(v54,v52),edge(v54,v57),edge(v54,v60),edge(v55,v37),edge(v55,v41),edge(v55,v43),edge(v55,v58),edge(v55,v59),edge(v56,v33),edge(v56,v36),edge(v56,v38),edge(v56,v40),edge(v57,v34),edge(v57,v44),edge(v57,v54),edge(v57,v60),edge(v58,v40),edge(v58,v41),edge(v58,v55),edge(v58,v59),edge(v59,v37),edge(v59,v38),edge(v59,v40),edge(v59,v55),edge(v59,v58),edge(v60,v31),edge(v60,v44),edge(v60,v47),edge(v60,v54),edge(v60,v57),start(v1)]).