10 teams, 10 spellen probleem

[sjasogun1]

Stel, je hebt 10 teams. Deze 10 teams spelen 10 spellen tegen elkaar, dus er staan 2 teams per spel. De helft van de spellen blijft dus altijd onbezet. Hoe, indien het überhaupt mogelijk is, is een schema te maken waarin elk team tenminste één keer tegen elk ander team heeft gespeeld EN waarin elk team elk spel minstens één keer heeft gespeeld. Ik heb er mijn hoofd al een tijdje over lopen breken maar ik kom er, zelfs met vereende krachten echt niet uit. Weet iemand de oplossing voor dit probleem?

[Safe]

Deze 10 teams spelen 10 spellen tegen elkaar, dus er staan 2 teams per spel. De helft van de spellen blijft dus altijd onbezet.

Wat bedoel je met spellen?

Worden er totaal 10 spellen gespeeld of speelt elk team (een spel) tegen elk ander team?

Kortom, heb je het over een halve competitie?

[sjasogun1]

Het is de bedoeling dat de teams wisselen over de spellen. Bijvoorbeeld, in de eerste ronde speelt team 1 tegen team 2 spel A, en speelt team 3 tegen team 4 spel B, enzovoorts. De volgende ronde zou je dan normaal gezien zeggen dat team 1 tegen team 2 spel B speelt en team 3 tegen team 4 spel C, of dat team 1 tegen team 3 spel A zou spelen en team 2 tegen team 4 spel B.

De eerste kan niet omdat team 1 en 2 dan twee keer tegen elkaar spelen (technisch gezien kan dit niet anders omdat ze niet tegen zichzelf kunnen spelen en er tien rondes moéten zijn omdat anders nooit alle 10 spellen gespeeld kunnen worden, maar als je dit patroon nog een keer herhaalt loopt het wel stuk)

De tweede kan niet omdat team 1 dan twee keer spel A speelt en team 4 twee keer spel B.

Een combinatie van die twee zou 1 tegen 3 met C en 2 tegen 4 met bijvoorbeeld D opleveren, maar hoe dan verder? Bij gewoon enkele patronen proberen loopt dit al snel vast. Ik ben er verder niet uitgekomen dus heb ik hier maar om hulp gevraagd. Ter verduidelijking hieronder nog enkele excel-tabellen van de situaties.

1 tegen 2 met B, 3 tegen 4 met C

Spoiler: [+]

1 tegen 3 met A, 2 tegen 4 met B

Spoiler: [+]

1 tegen 3 met C, 2 tegen 4 met D

Spoiler: [+]

Tweede poging, met andere beginwaarden. Dit is trouwens ook mijn beste poging tot dusver.

Spoiler: [+]

[kee]

Nog een vraagje: Wordt elk spel maar 1 keer gespeeld op hetzelfde moment, of kunnen meerdere teams hetzelfde spel spelen in een ronde?

[sjasogun1]

Nee, elk spel kan maar één keer gespeeld worden op hetzelfde moment. Er is bijvoorbeeld maar één basketbalveld, één hockeyveld, één voetbalveld enzovoorts.

[Marko]

Je geeft aan dat je wil dat ieder team ieder spel minstens één keer speelt, en iedere tegenstander ook minstens één keer tegenkomt, maar zit daar ook nog een maximum aan?

[sjasogun1]

Het 'toernooi' is afgelopen als elk team elk spel een keer heeft gespeeld. Aangezien er genoeg spellen zijn om elk team elke ronde te laten spelen en er 10 spellen zijn, zal dit 10 rondes duren. Voor het aantal keer dat een team tegen een ander team speelt is geen maximum, maar aangezien er 10 teams zijn en een team niet tegen zichzelf kan spelen, volgt daaruit in combinatie met het bovenstaande gegeven dat elk team precies één keer tegen acht teams zal spelen, en twee keer tegen het negende (en laatste aangezien ze zelf niet meetellen).

Samengevat: Elk team moet precies één keer elk spel spelen, en elk team moet minstens één keer tegen elk team hebben gespeeld.

[Erik Leppen]

Dit zijn leuke hersenkrakers en het is zeer de vraag of het kan. Ik heb een keer een vergelijkbaar vraagstuk onmogelijk bewezen, maar dat was veel kleiner. Met tien teams en tien spellen wordt het een hele klus. Ik denk dat wil je een oplossing vinden, dan heb je een of andere truc nodig.

Nog een vraag trouwens: zijn alle tien spellen alle tien rondes beschikbaar?

De reden dat ik het vraag is dat ik in jouw oplossing bijvoorbeeld de eerste vijf rondes alleen maar A tot en met E zie (aannemende dat dat de spellen zijn), waarbij F tot en met J pas in ronde 6 komen. Ik denk dat je het leegstaan van de helft van de spellen moet zien als een vrijheid die je zo slim mogelijk moet gebruiken. Ik verwacht dat als er een oplossing is, dat er dan elke ronde andere spellen leeg staan.

Verder, gaat het je om het antwoord, of om het zoekproces?

(Merk overigens verder op dat omdat er tien teams zijn en tien rondes, dat elk team in tien rondes negen tegenstanders ziet, en dat jouw voorwaarde dus betekent dat elk team 8 tegenstanders één keer ziet en één tegenstander twee keer.)

[EvilBro]

Ik was er redelijk van overtuigd dat er geen oplossing zou zijn. Met wat programmeerwerk vind ik echter het volgende:

\(\begin{array}{cccccccccc}

1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\

1 & 2 & 5 & 6 & 3 & 4 & 9 & 10 & 7 & 8 \\

2 & 1 & 3 & 6 & 4 & 5 & 10 & 9 & 8 & 7 \\

2 & 1 & 5 & 4 & 10 & 3 & 8 & 7 & 6 & 9 \\

10 & 7 & 1 & 3 & 5 & 4 & 6 & 2 & 8 & 9 \\

10 & 5 & 4 & 9 & 3 & 6 & 8 & 2 & 1 & 7 \\

5 & 8 & 1 & 9 & 4 & 2 & 7 & 10 & 6 & 3 \\

4 & 7 & 6 & 2 & 10 & 5 & 9 & 8 & 1 & 3 \\

4 & 5 & 6 & 3 & 1 & 2 & 10 & 7 & 9 & 8 \\

5 & 8 & 4 & 2 & 1 & 3 & 6 & 9 & 7 & 10

\end{array}\)

Hoe dit te lezen: een rij geeft een speler weer, een kolom een spel en het getal de ronde waarin de speler het spel speelt. Voorbeeld: rij 4, kolom 3 bevat een 5. Dit wil dus zeggen dat de speler 4 spel C in de vijfde ronde speelt. Je kan door in dezelfde kolom op zoek te gaan naar de andere 5 zien dat speler 2 de tegenstander is.

Heeft iemand een reden waarom dit geen oplossing is? (want ik kan natuurlijk een foutje gemaakt hebben.)

[Marko]

Gefeliciteerd!

Ik heb de oplossing gecontroleerd met een ad hoc scriptje

- Gecontroleerd of iedere speler ieder spel inderdaad precies 1 keer heeft gespeeld. Check!

- Gecontroleerd of iedere speler 1 tegenstander precies 2 keer heeft gezien en de andere tegenstanders precies 1 keer. Check!

- Voor de volledigheid: nog gecontroleerd hoe vaak ieder spel is gespeeld. Allemaal 10 5 keer.

Daarmee is aan de voorwaarden voldaan. De oplossing is juist.

Hoe heb je dit uiteindelijk aangepakt? Kan/wil je de code delen?

Ik dacht dat het met een niet al te moeilijk backtracking algoritme moest kunnen (nagaan of het kon en dan dus ook een juiste oplossing vinden), maar was er nog niet aan toegekomen om die te schrijven. Ik heb ooit een Sudoku-solver geschreven die ik dacht voor dit doel te kunnen ombouwen.

Gisteravond viel me ook ineens een benadering binnen waarmee ik de eerste 7 rondes zonder problemen kon invullen; maar toen vielen mijn ogen écht dicht, dus het antwoord op de vraag of het werkt laat nog even op zich wachten.

[EvilBro]

Ik zal alvast mijn Haskell-code posten. Ik zal later nog wel mijn methode uitleggen:

Code: Selecteer alles

import qualified Data.Map as Map

import Data.List



-- size of the grid

size = 10



-- get a solution from the solutionTree. Due to laziness of Haskell this will not construct the entire tree (only the part that is required for a solution).

solution = getSolution solutionTree



-- create a map that represents the start of the solution. This start calls the first game that player 1 plays game 1, the second game 2, etc.

-- The opponent that player 1 plays in round 2 and on is called player n where n is the round number. Player 1 plays against player 2 twice.

startMap :: (Map.Map (Integer, Integer) Integer)

startMap = Map.fromList (((2,1),1) :( [((k,k),k)| k <- [1..size]] ++ [((1,k),k)| k <- [1..size]]))



-- create a tree to hold all possible solutions

data Tree = Node (Map.Map (Integer, Integer) Integer) [Tree]

	deriving (Eq, Show)



solutionTree = Node startMap (createSubNodes startMap)



-- At each node, for the grid generated so far, find the first empty space (start at the top left, search row by row). For that empty space generate

-- all possible branches. An possibility always has two empty spaces: the current empty space and one for the opponent.

createSubNodes m | fullMap m = []

				 | otherwise = filter validNode [Node nm cs | a <- options m r c, let nm = insertOptions m a, let cs = (createSubNodes nm)]

	where

		(r,c) = firstEmptySpace m

		insertOptions m (r,c,a,v) = Map.insert (a,c) v (Map.insert (r,c) v m) -- insert the options into the grid

		firstEmptySpace m = fes m 2 3

			where

				fes m r c | c > size = fes m (r+1) 1

						  | r > size = (r, c)

						  | Map.lookup (r,c) m == Nothing = (r,c)

						  | otherwise = fes m r (c+1)

		

-- an option contains the empty space at (r,c) and another empty space (a,c) below it.

-- a possible pair is not an option if:

-- * space (r,c) and (a,c) cannot have the same value.

-- * player r and/or player a already plays against some player twice and this option would also make player r play player a twice.

options m r c = [(r,c,a,v) | a <- ((rowsOfEmpties m c) \\ [r]), v <- (intersect (validValue m r c) (validValue m a c)), ((matchesInRows m r a) == 0) || (((matchesInRows m r a) == 1) && (isAllowed m r a))]

	where

		isAllowed m r a = ((length (filter (>1) (matchesWithOther m r))) == 0) && ((length (filter (>1) (matchesWithOther m a))) == 0) -- check whether player r and/or player a already plays another player twice.						  

			where

				matchesWithOther m r = [matchesInRows m r a | a <- [1..size], r /= a]



-- Return all values that are possible for (r,c) in m. A value is not possible if:

-- * (r,c) already contains a value.

-- * it is equal to any number that is in the row r

-- * it is equal to any number that is in the column c

-- * it is in the rows of all empty spaces in column c

validValue m r c | lu == Nothing = (([1..size] \\ (rowNumbers m r)) \\ (columnNumbers m c)) \\ (foldl1 (intersect) (map (\a -> rowNumbers m a) ((rowsOfEmpties m c) \\ [r])))

				   | otherwise = []

	where

		lu = Map.lookup (r,c) m

		rowNumbers m r = filter (/= 0) $ map (\c -> replaceMaybe (Map.lookup (r,c) m)) [1..size] -- get all (nonzero) numbers already entered in row r.

		columnNumbers m c = filter (/= 0) $ map (\r -> replaceMaybe (Map.lookup (r,c) m)) [1..size] -- get all (nonzero) numbers already entered in column c

		

-- get all rows that have no number entered in column c

rowsOfEmpties m c = filter (\a -> Nothing == Map.lookup (a,c) m) [1..size]



-- Count how often row r1 and r2 match.

matchesInRows m r1 r2 = mir q w

	where

		q = map (\a -> replaceMaybe (Map.lookup (r1,a) m)) [1..size]

		w = map (\a -> replaceMaybe (Map.lookup (r2,a) m)) [1..size]

		mir [] [] = 0

		mir (q:qs) (w:ws) | (q == w) && (q /= 0) = 1 + (mir qs ws)

						  | otherwise = mir qs ws



-- a Node is valid if

--	 it has a full map (which must be valid due to inserting rules)

--	 or it has (valid) Nodes in its Node List.

validNode (Node m ts) = (fullMap m) || ([] /= ts)



fullMap m = (size*size) == (fromIntegral $ Map.size m)

		

-- convert the map with the grid to a list.

extractFromMap m = [map (\a -> replaceMaybe (Map.lookup (r,a) m)) [1..size] | r <- [1..size]]



-- extract the (most left) solution which is under the given Node.

getSolution (Node m ts) | fullMap m = extractFromMap m

						| ts == [] = []

						| otherwise = getSolution' (head ts)

	where

		getSolution' (Node m ts) | ts == [] = extractFromMap m

								 | otherwise = getSolution' (head ts)



						

-- just a function to get rid of the Maybe from Map.lookup

replaceMaybe k | k == Nothing = 0

			   | otherwise	= n

	where

		Just n = k

[sjasogun1]

@Erik Leppen: Ja, elk spel is in elke ronde beschikbaar zolang het niet al gespeeld wordt. En dat ik in de eerste vijf rondes alleen de spellen A-E heb gebruikt is omdat ik het idee had opgevat dat ik het patroon voor de eerste vijf ronden zou kunnen aanpassen voor de laatste vijf, maar uiteindelijk ben ik daar toch niet uitgekomen.

Als antwoord op je andere vraag, het ging me in eerste instantie om de oplossing voor een werkelijk probleem: mijn moeder is docente op een basisschool en zij had de opdracht om een schema uit te denken voor tien spellen die de kinderen in tien teams zouden moeten spelen. Zij kwam hier echter niet uit en na wat gepuzzel dacht ik dat de oplossing niet zo eenvoudig te vinden zou zijn als ik aanvankelijk had gedacht en besloot ik het hier te vragen. Deze gelegenheid is echter al ruim voorbij (er is voor een alternatief schema gekozen waarin ieder team alleen elk spel minstens één keer gespeeld moest hebben), maar ik was nog steeds benieuwd naar de oplossing, als het überhaupt mogelijk zou zijn.

@EvilBro: Wauw, hartstikke bedankt voor de oplossing! Ik begon al te twijfelen of het überhaupt mogelijk was. Voor zover ik kan zien klopt de oplossing inderdaad en ik zal Marko op zijn woord geloven als hij het met een scriptje gecontroleerd heeft. Je Haskell-code ziet er interessant uit om te bestuderen, maar helaas ben ik niet voldoende bedreven in Functioneel programmeren om je code te begrijpen (ik ben namelijk meer van het imperatief programmeren). Het was eigenlijk nog helemaal niet in me op gekomen om een programmaatje te schrijven om een oplossing te vinden, vooral doordat er

\((10\cdot10)^{10}=100^{10}=10^{20}\)

mogelijkheden zijn om de cijfers te ordenen. Ik ben erg benieuwd naar je uitleg van hoe je het gedaan hebt!

@Marko: Zou je kunnen kijken of je nog tot die oplossing zou kunnen komen? De oplossing met het computerprogramma is natuurlijk prima (het ging me om de oplossing, niet om de methode), maar een algoritme is natuurlijk altijd leuker. Tenzij ik me vergist heb en het programmaatje van EvilBro ook met een algoritme werkt i.p.v. uitproberen en uitsluiten, waarvoor excuses.

[EvilBro]

Wat mijn code doet: ik genereer eerst een startpunt. Dit doe ik door te zeggen dat in ronde N speler 1 tegen speler N speelt bij spel N. In de eerste twee rondes spelen spelers 1 en 2 tegen elkaar. Dit geeft de initiele vulling voor mijn grid.

Vervolgens definieer ik een boom met daarin alle oplossingen. Elke node in de boom bevat het grid tot dan toe en een lijst met alle valide nodes die daarop volgen. Om de vervolgnodes te genereren ga ik opzoek naar het eerste lege vakje in het grid. Bij dit vakje zoek ik alle paren van lege vakjes en alle mogelijke waarden die daarin kunnen. Voor elk van deze opties maak ik een node aan in de lijst.

Een paar vakjes is een mogelijkheid als de vakjes leeg zijn, het getal wat je in de vakjes wil zetten nog niet voorkomt op een van de rijen van de lege vakjes, nog niet in die kolom voorkomt en het toevoegen van het getal niet veroorzaakt dat een speler meer dan twee keer tegen een andere speler speelt of twee keer twee keer tegen een speler speelt.

In elke tak van de boom komt een moment dat het niet meer mogelijk is om getallen toe te voegen aan het grid. Als het grid op dat moment vol is dan heb je een oplossing gevonden. Als je grid niet vol is dan is dit deel van de boom een doodlopende tak. Als een tak doodlopend is dan wordt deze uit de boom gehouden.

Ik vind nu een oplossing door te kijken wat de meest linker tak is. Is de boom leeg dan is er geen oplossing. Over het vinden van een oplossing doet mijn computer bij N=10 ongeveer een minuut.

De reden dat deze methode uberhaupt werkt is omdat Haskell lazy is. Alleen die delen van de boom die nodig zijn worden daadwerkelijk berekend. De berekening stopt dus zodra er een oplossing gevonden is. Op het moment dat er geen oplossing wordt gevonden duurt het dan ook lang (je moet immers de hele boom af).

Dit alles zou ook prima te doen moeten zijn in een imperatieve taal. Je zal dan door de boom moeten lopen ipv hem gewoon definieren.

[sjasogun1]

Ik snap je bedoeling met het programmaatje, het komt eigenlijk op hetzelfde neer als het backtracking-algoritme dat Marko al genoemd had, maar dan op een manier waarop elke 'tak' tegelijk een wordt uitgebreid indien mogelijk, terwijl een backtracking-algoritme eerst een hele tak af zou maken en dan terug zou gaan naar de eerstvorige positie waar een splitsing nog mogelijk was. In ieder geval bedankt voor je uitleg en het antwoord!

P.S.: Ik zie trouwens dat ik in mijn vorige post een foutje heb gemaakt, het aantal mogelijkheden is

\(10^{100}=1 googol\)

en niet

\(100^{10}=10^{20}\)

[Marko]

Ik ben inmiddels bezig met een recursief dingetje, dat in feite (mind of meer) hetzelfde doet als EvilBro's programma.

Als ik die klaar heb zal ik het resultaat hier neerzetten.

De benadering die ik volgde werkte uiteindelijk niet; was ik eigenlijk al bang voor. De eerste 6 rondes gaat prima, maar daarna was het niet meer mogelijk om alles netjes te vullen.