Calendar of a football championship - Answer set programming

Question

I wrote an algorithm in answer set programming, run with clingo, to calculate a league of 20 teams and its 38 matches (19 round and 19 return) with certain constraints:

• There may not be more than one match on the same day with two teams at home from the same city;
• A team may not play more than two home games in a row.
• Between a first match and a return match (same teams) must pass at least 10 days.

The problem is that the algorithm, performed in a test with 10 teams, ends in 20 seconds, while with 20 teams does not end in 24 hours..

Is there any way to optimize the algorithm, maybe by using counts or something?

This is the code:

squadra(
    milan;
    napoli;
    inter;
    juventus;
    atalanta;
    roma;
    lazio;
    fiorentina;
    sassuolo;
    verona;
    torino;
    bologna;
    empoli;
    udinese;
    sampdoria;
    spezia;
    cagliari;
    venezia;
    genoa;
    salernitana
).

citta(milan, milano).
citta(napoli, napoli).
citta(inter, milano).
citta(juventus, torino).
citta(atalanta, bergamo).
citta(roma, roma).
citta(lazio, roma).
citta(fiorentina, firenze).
citta(sassuolo, sassuolo).
citta(verona, verona).
citta(torino, torino).
citta(bologna, bologna).
citta(empoli, empoli).
citta(udinese, udine).
citta(sampdoria, genova).
citta(spezia, laspezia).
citta(cagliari, cagliari).
citta(venezia, venezia).
citta(genoa, genova).
citta(salernitana, salerno).

giornataAndata(1..19).
giornataRitorno(20..38).

% 10 partite per ogni giornata
10 {partita(G, SquadraCasa, SquadraTrasferta) : squadra(SquadraCasa), squadra(SquadraTrasferta), SquadraCasa <> SquadraTrasferta} 10 :- giornataAndata(G).
10 {partita(G, SquadraCasa, SquadraTrasferta) : squadra(SquadraCasa), squadra(SquadraTrasferta), SquadraCasa <> SquadraTrasferta} 10 :- giornataRitorno(G).

% Nella stessa giornata, una squadra non può giocare più di una partita.
% In giornate diverse, due squadre che si sono già incontrate, non si posso rincontrare.
:- giornataAndata(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa, SquadraTrasferta2), SquadraTrasferta<>SquadraTrasferta2.
:- giornataAndata(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta), SquadraCasa<>SquadraCasa2.
:- giornataAndata(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta2), SquadraCasa==SquadraTrasferta2.
:- giornataAndata(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta2), SquadraTrasferta==SquadraCasa2.
:- giornataAndata(G), giornataAndata(G2), partita(G, SquadraCasa, SquadraTrasferta), partita(G2, SquadraCasa, SquadraTrasferta), G<>G2.
:- giornataAndata(G), giornataAndata(G2), partita(G, SquadraCasa, SquadraTrasferta), partita(G2, SquadraTrasferta, SquadraCasa), G<>G2.
:- giornataRitorno(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa, SquadraTrasferta2), SquadraTrasferta<>SquadraTrasferta2.
:- giornataRitorno(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta), SquadraCasa<>SquadraCasa2.
:- giornataRitorno(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta2), SquadraCasa==SquadraTrasferta2.
:- giornataRitorno(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta2), SquadraTrasferta==SquadraCasa2.
:- giornataRitorno(G), giornataRitorno(G2), partita(G, SquadraCasa, SquadraTrasferta), partita(G2, SquadraCasa, SquadraTrasferta), G<>G2.
:- giornataRitorno(G), giornataRitorno(G2), partita(G, SquadraCasa, SquadraTrasferta), partita(G2, SquadraTrasferta, SquadraCasa), G<>G2.

:- giornataAndata(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta2), SquadraCasa<>SquadraCasa2, citta(SquadraCasa, C), citta(SquadraCasa2, C).
:- giornataRitorno(G), partita(G, SquadraCasa, SquadraTrasferta), partita(G, SquadraCasa2, SquadraTrasferta2), SquadraCasa<>SquadraCasa2, citta(SquadraCasa, C), citta(SquadraCasa2, C).

:- giornataAndata(GA), giornataRitorno(GR), partita(GA, SquadraCasa, SquadraTrasferta), partita(GR, SquadraCasa, SquadraTrasferta).

:-  giornataAndata(G), 
    partita(G, SquadraCasa, SquadraTrasferta), 
    partita(G+1, SquadraCasa, SquadraTrasferta2),
    partita(G+2, SquadraCasa, SquadraTrasferta3).

:-  giornataRitorno(G), 
    G<=36,
    partita(G, SquadraCasa, SquadraTrasferta), 
    partita(G+1, SquadraCasa, SquadraTrasferta2),
    partita(G+2, SquadraCasa, SquadraTrasferta3).

:-  giornataAndata(GA), 
    giornataRitorno(GR), 
    GR<=29,
    partita(GA, SquadraCasa, SquadraTrasferta),
    partita(GR, SquadraTrasferta, SquadraCasa),
    Risultato = GR-GA,
    Risultato <= 10.

#show partita/3.

SquadraCasa = Home team.

SquadraTrasferta = Away team.

G = number of day.

partita(G, SquadraCasa, SquadraTrasferta) = match(G, HomeTeam, AwayTeam).

giornataAndata(1..19) = first half of the season(1..19).

giornataRitorno(20..38) = second half of the season(20..38).

citta(milan, milano) = the team "Milan" play in the city of Milan.

squadra(milan; napoli; ...) = team(milan; napoli; ...).

Thank you very much in advance!

Answer 1

I have bad news for you: your program seems unsatisfiable.

I rewrote the code since there are redundancies, and I came up with this:

player(milan; napoli; inter; juventus; atalanta; roma; lazio; fiorentina; sassuolo; verona; torino; bologna; empoli; udinese; sampdoria; spezia; cagliari; venezia; genoa; salernitana).
n(N):- {player(X)} = N. % counting players

citta(milan, milano).
citta(napoli, napoli).
citta(inter, milano).
citta(juventus, torino).
citta(atalanta, bergamo).
citta(roma, roma).
citta(lazio, roma).
citta(fiorentina, firenze).
citta(sassuolo, sassuolo).
citta(verona, verona).
citta(torino, torino).
citta(bologna, bologna).
citta(empoli, empoli).
citta(udinese, udine).
citta(sampdoria, genova).
citta(spezia, laspezia).
citta(cagliari, cagliari).
citta(venezia, venezia).
citta(genoa, genova).
citta(salernitana, salerno).

dates(1..2*(N-1)) :- n(N).
date1(1..N-1) :- n(N).
date2(N..2*N-2) :- n(N).

1{game(T,X,Y):dates(T)}1:- player(X),player(Y), X<>Y.
(N/2){ game(T,X,Y): player(X), player(Y), X<>Y }(N/2) :- dates(T), n(N).

:- player(X), player(Y), game(G1,X,Y),  game(G2,Y,X), G1<G2, date2(G1).
:- player(X), player(Y), game(G1,X,Y),  game(G2,Y,X), G1<G2, date1(G2).
:- player(X), game(G,X,_), game(G+1,X,_), game(G+2,X,_).
:- player(X), player(Y), game(G1,X,Y),  game(G2,Y,X), G1<G2, G2-G1<=N, n(N).
:- dates(T), game(T,X,_), game(T,Y,_), citta(X,Z), citta(Y,Z).

which returns unsatisfiable. If you comment the last line out you will get a model. Please note that I took some liberty interpreting your work.