# Enigmatic Code

Programming Enigma Puzzles

## Puzzle 70: Football five teams: new method

From New Scientist #1121, 21st September 1978 [link]

The new method of rewarding goals scored in football matches goes from strength to strength. In this method 10 points are given for a win, 5 points for a draw and 1 point for each goal scored. Once can get some idea of the success of the method from the fact that in the latest competition between 5 teams, when some of the matches had been played, each team had scored at least 1 goal in every match. They are eventually going to play each other once.

The points were as follows:

A   11
B    8
C   12
D    5
E   43

Not more than 9 goals were scored in any match.

What was the score in each match?

[puzzle70]

### 8 responses to “Puzzle 70: Football five teams: new method”

1. Jim Randell 12 July 2017 at 12:15 pm

Here I’ve used a simple MiniZinc model to solve this problem. The [[ `mzn-g12fd` ]] solver executes it in 110ms.

```%#! mzn-g12fd -a

% points for team X in match X vs Y given goals scored
% (we use 0-0 to mean a match is not played)
function var int: points(var int: X, var int: Y) =
if X = 0 /\ Y = 0
then 0
else X + 10 * (X > Y) + 5 * (X = Y)
endif;

% goals for each side in each game
var 0..8: AB; var 0..8: BA;
var 0..8: AC; var 0..8: CA;
var 0..8: AD; var 0..8: DA;
var 0..8: AE; var 0..8: EA;
var 0..8: BC; var 0..8: CB;
var 0..8: BD; var 0..8: DB;
var 0..8: BE; var 0..8: EB;
var 0..8: CD; var 0..8: DC;
var 0..8: CE; var 0..8: EC;
var 0..8: DE; var 0..8: ED;

% at least one goal is scored in each played match
constraint AB = 0 <-> BA = 0;
constraint AC = 0 <-> CA = 0;
constraint AD = 0 <-> DA = 0;
constraint AE = 0 <-> EA = 0;
constraint BC = 0 <-> CB = 0;
constraint BD = 0 <-> DB = 0;
constraint BE = 0 <-> EB = 0;
constraint CD = 0 <-> DC = 0;
constraint CE = 0 <-> EC = 0;
constraint DE = 0 <-> ED = 0;

% not more than 9 goals were scored in any match
constraint AB + BA < 10;
constraint AC + CA < 10;
constraint AD + DA < 10;
constraint AE + EA < 10;
constraint BC + CB < 10;
constraint BD + DB < 10;
constraint BE + EB < 10;
constraint CD + DC < 10;
constraint CE + EC < 10;
constraint DE + ED < 10;

% points for each team
constraint points(AB, BA) + points(AC, CA) + points(AD, DA) + points(AE, EA) = 11;
constraint points(BA, AB) + points(BC, CB) + points(BD, DB) + points(BE, EB) = 8;
constraint points(CA, AC) + points(CB, BC) + points(CD, DC) + points(CE, EC) = 12;
constraint points(DA, AD) + points(DB, BD) + points(DC, CD) + points(DE, ED) = 5;
constraint points(EA, AE) + points(EB, BE) + points(EC, CE) + points(ED, DE) = 43;

solve satisfy;

output [
"AvB = " ++ show([AB, BA]) ++ "\n" ++
"AvC = " ++ show([AC, CA]) ++ "\n" ++
"AvD = " ++ show([AD, DA]) ++ "\n" ++
"AvE = " ++ show([AE, EA]) ++ "\n" ++
"BvC = " ++ show([BC, CB]) ++ "\n" ++
"BvD = " ++ show([BD, DB]) ++ "\n" ++
"BvE = " ++ show([BE, EB]) ++ "\n" ++
"CvD = " ++ show([CD, DC]) ++ "\n" ++
"CvE = " ++ show([CE, EC]) ++ "\n" ++
"DvE = " ++ show([DE, ED])
];
```

Solution: The scores in the played matches are: AvB = 2-2; AvE = 4-5; BvE = 1-3; CvD = 2-1; DvE = 4-5. The remaining matches are not yet played.

2. hakank 12 July 2017 at 9:18 pm

Here’s another MiniZinc model, using a matrix for the scores (which seemed more natural for me).

```% include "globals.mzn";

int: n = 5;
array[1..n] of int: points = [11,8,12,5,43];

% decision variables
% a match between a and b: a got scores[a,b] points and b got scores[b,a] points
array[1..n,1..n] of var 0..9: scores; % max 9 scores. 0's for not played matches

% var 0..(n+(n+1)) div 2: num_matches = sum([scores[i,j] > 0 | i,j in 1..n ]) div 2;

% solve satisfy;
solve :: int_search(array1d(scores), first_fail, indomain_split, complete) satisfy;

constraint
forall(i in 1..n) (
scores[i,i] = 0 % a team don't play against itself
/\
% the possible matches
forall(j in 1..n where i < j) (
% a match not yet played: scores 0
if scores[i,j] = 0 then scores[j,i] = 0 else true endif
/\
% each teams scored at least 1 goal in every match: scores > 0
if scores[i,j] > 0 then scores[j,i] > 0 else true endif
/\ % no more than 9 goals was scored in each match
scores[i,j] + scores[j,i] <= 9
)
)
/\ % the points
forall(i in 1..n) (
points[i] = sum([ 10*(scores[i,j] > scores[j,i]) + 5*(scores[i,j] = scores[j,i] /\ scores[i,j] > 0)
+ scores[i,j]
| j in 1..n where i != j])

)
;

output
% ["num_matches: \(num_matches)\n"] ++
[
if j = 1 then "\n" else "" endif ++
show(scores[i,j]) ++ " "
| i,j in 1..n
]
++ ["\n\n"] ++
[
if fix(scores[i,j]) > 0 then
"\(i) vs \(j): \(scores[i,j]) - \(scores[j,i])\n"
else
""
endif
| i,j in 1..n where i < j
]
;
```
• Jim Randell 13 July 2017 at 9:35 am

@hakank: Thanks for your post. Sorry you had problems (at one time I hoped that WordPress.com would allow the ability to edit (or even preview) comments, but it never happened).

I took the code from the link you posted and incorporated it into the original comment, using:

`[code language="text"]...[/code]`

tags to preserve the code. (See [ https://en.support.wordpress.com/code/posting-source-code/ ] for a list of supported languages). I deleted the followup comments where you were trying to sort it out. Hope that’s OK.

• hakank 13 July 2017 at 11:24 am

@jim Thanks for this. And sorry for messing things up. I’ll try to remember that it should be “code” and not “pre” that I should use. And I’ll test it right away with a new comment on the Picat code. 🙂

3. hakank 12 July 2017 at 10:52 pm

And here’s the same approach in Picat: http://hakank.org/picat/football_five_teams_new_method.pi

4. hakank 13 July 2017 at 11:26 am

Here’s the Picat code mentioned above:

```import cp.

main => go.

go =>
N = 5,
Points = [11,8,12,5,43],

% decision variables
% a match between a and b: a got scores[a,b] points and b got scores[b,a] points
Scores = new_array(N,N),
Scores :: 0..8, % max 8 goal per match (1+8). 0's for not played matches

foreach(I in 1..N)
Scores[I,I] #= 0, % a team don't play against itself
foreach(J in 1..N, I < J)
% a match not yet played: scores 0,
% also: each teams scored at least 1 goal in every match: scores > 0
Scores[I,J] #= 0 #<=> Scores[J,I] #= 0,

% no more than 9 goals was scored in each match
Scores[I,J] + Scores[J,I] #<= 9
end
end,
% the points
foreach(I in 1..N)
Points[I] #= sum([
10*(Scores[I,J] #> Scores[J,I]) +
5*((Scores[I,J] #= Scores[J,I]) #/\ Scores[I,J] #> 0) +
Scores[I,J]
: J in 1..N, I != J])
end,

solve(\$[ff,split],Scores),

foreach(I in 1..N, J in 1..N, I < J)
if Scores[I,J] > 0 then
printf("%d vs %d: %d - %d\n", I,J, Scores[I,J],Scores[J,I])
end
end,
nl.
```
5. hakank 21 July 2017 at 6:32 pm

@jim: Yes, Picat is an interesting language. I’m kind of involved with Picat and co-authored the book “Constraint Solving and Planning with Picat” together with Neng-Fa Zhou (creator of Picat) and Jonathan Frumann in 2015. The book is now free to download: PDF via http://picat-lang.org/picatbook2015.html (I was the main author of the two Constraint Programming chapters). Here’s my Picat page with some programs in different areas of interest: http://hakank.org/picat/ .

MiniZinc has better support for some type of constraints (e.g. element: z = x[y] where x, y, and z are all decision variables) and also has support for many different FlatZinc solvers, among them Picat. Picat, on the other hand, is a complete programming language where one can write traditional “imperative” loops (which MiniZinc don’t allow). So MiniZinc and Picat are both favourite languages, and nowadays I tend to implement models in both languages.

This site uses Akismet to reduce spam. Learn how your comment data is processed.