Stardoku is een puzzel waarbij een getal $$s$$ gegeven wordt en een vierkant $$n \times n$$ rooster met $$n$$ rijen en $$n$$ kolommen. Het rooster is onderverdeeld in $$n$$ gebieden. De opdracht bestaat erin om $$s \times n$$ sterren op het rooster te plaatsen — maximaal één in elke cel van het rooster — zodat

• elke rij exact $$s$$ sterren bevat

• elke kolom exact $$s$$ sterren bevat

• twee cellen met sterren elkaar nooit horizontaal, vertikaal of diagonaal raken

• elk gebied exact $$s$$ sterren bevat

Hieronder zie je links een voorbeeld van een Stardoku waarbij 2 sterren moeten geplaatst worden in elke rij, elke kolom en elk gebied van een $$10 \times 10$$ rooster, met rechts een correcte oplossing. In dit geval zijn de gebieden van het rooster omgeven door dikke zwarte lijnen, en zijn ze ook samenhangend (maar dit laatste leggen we niet op als voorwaarde van een puzzel). Merk op dat een Stardoku niet noodzakelijk een unieke oplossing moet hebben.

Opgave: klasse Puzzel

Een tekstbestand met de omschrijving van een Stardoku bestaat uit een regel met een getal $$s \in \mathbb{N}_0$$. Daarna volgen $$n \in \mathbb{N}_0$$ rijen met elk $$n$$ karakters, waarbij de gebieden gevormd worden door de cellen van het $$n \times n$$ rooster met hetzelfde karakter. Hieronder zie je bijvoorbeeld de inhoud van een tekstbestand met de omschrijving van een Stardoku met een $$6 \times 6$$ rooster en waarbij in elke rij, elke kolom en elk gebied één ster moet geplaatst worden.

1
AABBCC
AABCCC
AABCCC
DDBBEE
DDBBEF
DDBBFF

De rijen van het rooster worden van boven naar onder genummerd, en de kolommen van links naar rechts, telkens vanaf nul. Een positie in het rooster wordt voorgesteld door een tuple $$(r, k)$$, waarbij $$r$$ en $$k$$ respectievelijk het rij- en kolomnummer van de cel in het rooster aangeven.

Definieer een klasse Puzzel waarmee Stardoku's kunnen voorgesteld worden. Bij initialisatie van objecten van de klasse Puzzel moet de locatie van een tekstbestand met de omschrijving van een Stardoku doorgegeven worden. Indien de inhoud van het tekstbestand niet overeenkomt met bovenstaande omschrijving, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige puzzel. Elk object van de klasse Puzzel moet de volgende twee onveranderlijke eigenschappen hebben:

• sterren (int): aantal sterren dat in elke rij, elke kolom en elk gebied van de Stardoku moet geplaatst worden

• dimensie (int): aantal rijen en kolommen van het vierkant rooster van de Stardoku

Indien een poging wordt ondernomen om deze eigenschappen te wijzigen, dan moet een AttributeError opgeworpen worden met de boodschap can't set attribute. Voorts moet de klasse Puzzel minstens de volgende methoden ondersteunen:

• Een methode gebied waaraan twee integers $$r$$ en $$k$$ moeten doorgegeven worden. Indien $$(r, k)$$ geen geldige positie in het rooster aanduidt, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige positie. Anders moet het karakter op positie $$(r, k)$$ in het rooster teruggegeven worden.

• Een methode posities waaraan een string met één karakter moet doorgegeven worden. De methode moet een verzameling teruggeven met alle posities in het rooster waar het gegeven karakter voorkomt. Indien het gegeven karakter niet in het rooster voorkomt, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig gebied.

Zorg er voor dat de ingebouwde functie print kan gebruikt worden om een stringvoorstelling van de objecten van de klasse Puzzel uit te schrijven. Deze voorstelling komt overeen met de inhoud van het tekstbestand dat gebruikt werd om een object van de klasse Puzzel te initialiseren, zonder de eerste regel die het aantal sterren aangeeft.

Voorbeeld: klasse Puzzel

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het bestand puzzel.txt¹ zich in de huidige directory bevindt.

>>> puzzel = Puzzel('puzzel.txt')
>>> print(puzzel)
AABBCC
AABCCC
AABCCC
DDBBEE
DDBBEF
DDBBFF
>>> puzzel.sterren
1
>>> puzzel.dimensie
6
>>> puzzel.sterren = 4
Traceback (most recent call last):
AttributeError: can't set attribute
>>> puzzel.dimensie = 3
Traceback (most recent call last):
AttributeError: can't set attribute
>>> puzzel.gebied(0, 0)
'A'
>>> puzzel.gebied(3, 4)
'E'
>>> puzzel.gebied(100, 100)
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> puzzel.posities('A')
{(0, 1), (0, 0), (2, 1), (2, 0), (1, 0), (1, 1)}
>>> puzzel.posities('E')
{(4, 4), (3, 4), (3, 5)}
>>> puzzel.posities('X')
Traceback (most recent call last):
AssertionError: ongeldig gebied

Hieronder zie je een grafische voorstelling van de puzzel die in bovenstaand voorbeeld gebruikt wordt. Hierbij worden de gebieden die corresponderen met de verschillende letters elk met een eigen kleur ingekleurd.

Opgave: klasse Oplossing

Een tekstbestand met de mogelijke oplossing van een Stardoku bestaat uit $$n \in \mathbb{N}_0$$ rijen met elk $$n$$ karakters: een punt (.) of een asterisk (*). Lege cellen worden aangeduid met een punt. Cellen die een sterretje bevatten, worden aangeduid met een asterisk. Hieronder zie je bijvoorbeeld de inhoud van een tekstbestand met een mogelijke oplossing van een Stardoku met een $$6 \times 6$$ rooster.

..*...
*.....
...*..
.....*
.*....
....*.

De rijen en kolommen van het rooster worden op dezelfde manier genummerd als bij het rooster van de puzzel zelf. Een positie in het rooster wordt op dezelfde manier voorgesteld door een tuple.

Definieer een klasse Oplossing waarmee mogelijke oplossingen van Stardoku's kunnen voorgesteld worden. Bij initialisatie van objecten van de klasse Oplossing moet de locatie van een tekstbestand met de mogelijke oplossing van een Stardoku doorgegeven worden. Indien de inhoud van het tekstbestand niet overeenkomt met bovenstaande omschrijving, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige puzzel. Elk object van de klasse Oplossing moet de volgende twee onveranderlijke eigenschappen hebben:

• dimensie (int): aantal rijen en kolommen van het vierkant rooster van de mogelijke oplossing

• posities_sterren (set): verzameling met alle posities in het rooster van de mogelijk oplossing waar er sterren staan

Indien een poging wordt ondernomen om deze eigenschappen te wijzigen, dan moet een AttributeError opgeworpen worden met de boodschap can't set attribute. Voorts moet de klasse Oplossing minstens de volgende methoden ondersteunen:

• Een methode sterren_rijen waaraan geen argumenten moeten doorgegeven worden. De methode moet een lijst teruggeven met het aantal sterren op elke rij van het rooster, waarbij de rijen van boven naar onder overlopen worden.

• Een methode sterren_kolommen waaraan geen argumenten moeten doorgegeven worden. De methode moet een lijst teruggeven met het aantal sterren op elke kolom van het rooster, waarbij de kolommen van links naar rechts overlopen worden.

• Een methode sterren_met_buren waaraan geen argumenten moeten doorgegeven worden. De methode moet een verzameling teruggeven met alle posities van sterren die een naburige ster hebben in een horizontaal, vertikaal of diagonaal aangrenzende cel.

• Een methode sterren_gebieden waaraan een Stardoku (een object van de klasse Puzzel) moet doorgegeven worden. Indien het aantal rijen (en kolommen) van de mogelijke oplossing afwijkt van het aantal rijen (en kolommen) van de gegeven Stardoku, dan moet een AssertionError opgeworpen worden met de boodschap puzzel en oplossing hebben verschillende dimensies. Anders moet de methode een dictionary teruggeven die elk karakter uit het rooster van de gegeven Stardoku afbeeldt op het aantal sterren in de mogelijke oplossing die in het overeenkomstige gebied staan.

• Een methode is_geldig waaraan een Stardoku (een object van de klasse Puzzel) moet doorgegeven worden. De methode moet een Booleaanse waarde teruggeven die aangeeft of de mogelijke oplossing een geldige oplossing is voor de gegeven Stardoku.

Zorg er voor dat de ingebouwde functie print kan gebruikt worden om een stringvoorstelling van de objecten van de klasse Oplossing uit te schrijven. Deze voorstelling komt overeen met de inhoud van het tekstbestand dat gebruikt werd om een object van de klasse Oplossing te initialiseren.

Voorbeeld: klasse Oplossing

Bij onderstaande voorbeeldsessie gaan we ervan uit dat de bestanden puzzel.txt², oplossing_01.txt³, oplossing_02.txt⁴, oplossing_03.txt⁵, oplossing_04.txt⁶ en oplossing_05.txt⁷ zich in de huidige directory bevinden.

>>> puzzel = Puzzel('puzzel.txt')

>>> oplossing = Oplossing('oplossing_01.txt')
>>> print(oplossing)
..*...
*.....
...*..
.....*
.*....
....*.
>>> oplossing.dimensie
6
>>> oplossing.posities_sterren
{(5, 4), (2, 3), (1, 0), (4, 1), (0, 2), (3, 5)}
>>> oplossing.dimensie = 3
Traceback (most recent call last):
AttributeError: can't set attribute
>>> oplossing.sterren_rijen()
[1, 1, 1, 1, 1, 1]
>>> oplossing.sterren_kolommen()
[1, 1, 1, 1, 1, 1]
>>> oplossing.sterren_met_buren()
set()
>>> oplossing.sterren_gebieden(puzzel)
{'A': 1, 'B': 1, 'C': 1, 'D': 1, 'E': 1, 'F': 1}
>>> oplossing.is_geldig(puzzel)
True

>>> oplossing = Oplossing('oplossing_02.txt')
>>> print(oplossing)
..*..*
*.....
......
.....*
.*....
....*.
>>> oplossing.sterren_rijen()
[2, 1, 0, 1, 1, 1]
>>> oplossing.sterren_kolommen()
[1, 1, 1, 0, 1, 2]
>>> oplossing.is_geldig(puzzel)
False

>>> oplossing = Oplossing('oplossing_03.txt')
>>> print(oplossing)
..*...
...*..
.....*
*.....
.*....
....*.
>>> oplossing.sterren_met_buren()
{(3, 0), (1, 3), (4, 1), (0, 2)}
>>> oplossing.sterren_gebieden(puzzel)
{'A': 0, 'B': 1, 'C': 2, 'D': 2, 'E': 0, 'F': 1}
>>> oplossing.is_geldig(puzzel)
False

>>> oplossing = Oplossing('oplossing_04.txt')
>>> print(oplossing)
..*..
*....
...*.
.*...
....*
>>> oplossing.dimensie
5
>>> puzzel.dimensie
6
>>> oplossing.sterren_met_buren()
set()
>>> oplossing.sterren_gebieden(puzzel)
Traceback (most recent call last):
AssertionError: puzzel en oplossing hebben verschillende dimensies
>>> oplossing.is_geldig(puzzel)
False

>>> oplossing = Oplossing('oplossing_05.txt')
Traceback (most recent call last):
AssertionError: ongeldige oplossing

Hieronder zie je een grafische voorstelling van de eerste drie mogelijke oplossingen die in bovenstaand voorbeeld gebruikt wordt. Enkel de eerste daarvan is ook een geldige oplossing.