Generierung eines Dobble-Kartensets

This is an old revision of the document!

Dobble ist ein Kartenspiel, wo auf jeder Karte genau $n=8$ unterschiedliche Symbole abgebildet sind. Die Symbole auf der Karte sind so gewählt, dass bei jedem beliebigen Paar von Karten es immer genau ein Symbol gibt, in dem die Karten übereinstimmen. Im Spiel geht es darum, das gemeinsame Symbol vor den Mitspielern zu finden.

Schreiben Sie ein Programm, das ein Dobble-Kartenset erzeugt. Anstatt $m$ verschiedene Symbole werden einfach Zahlen $0, \ldots, m-1$ verwendet, eine Karte wird als Array mit 8 Einträgen betrachtet. Z.B. [0,1,2,3,4,5,6,7].

Das Programm sollte das grösst-mögliche Kartenset erzeugen und wenn möglich auch für andere $n$ (Anzahl Symbole auf einer Karte) funktionieren.

Dokumentieren Sie bitte Ihre Überlegungen und Codes.

Hilfestellungen

Erzeugen Sie Kartensets mit $n=2$ und $n=3$ Symbolen von Hand.

Überlegen Sie sich folgendes:

Gegeben ist ein (evtl. unvollständiges) Kartenset, das die Bedingung erfüllt, dass jedes Paar von Karte genau ein gemeinsames Symbol.
Weiter ist eine (i.d.R. unvollständige) Karte gegeben, die mit jeder Karte aus dem Kartenset 0 oder 1 gemeinsames Symbol hat.
Überlegen Sie sich, wie die Karte um ein ergänzt werden könnte.

Programmieren Sie eine rekursive Funktion, die im Setting von oben eine Karte vervollständigt, oder meldet, dass die Karte nicht vervollständigt werden kann.

Diese Methode liefert zwar valide Kartensets, die zwar nicht vergrössert werden können, die aber auch nicht optimal sind, im Sinne dass es grössere Sets gibt.

Man findet auf dem Internet auch einiges zu diesem Problem. Es gibt dazu auch noch offene mathematische Fragen (ab $n=12$ Symbolen). Eine wirklich schöne Seite ist diese hier: https://puzzlewocky.com/games/the-math-of-spot-it/