De opgave van een bellen en blokken puzzel bestaat uit $$m \times n$$ vierkanten die gerangschikt zijn in een rechthoekig rooster met $$m$$ rijen en $$n$$ kolommen. Het rooster is onderverdeeld in samenhangende gebieden van vierkanten die omsloten worden door dikke blauwe lijnen. Vierkanten die groen gekleurd zijn, behoren tot geen enkel gebied. Dit is een voorbeeld van zo'n puzzel waarvan het $$4 \times 4$$ rooster onderverdeeld is in vier gebieden.

Het doel is om in elk gebied van het rooster juist één luchtbel en juist één rotsblok te plaatsen. Daarbij moeten een aantal regels in acht genomen worden. In elk vierkant kan er maar één luchtbel of rotsblok staan. Als er niets in de weg staat, zakken rotsblokken naar de onderste rij van het rooster en stijgen luchtbellen naar de bovenste rij van het rooster.

Rotsblokken kunnen bovenop groene vierkanten en bovenop andere rotsblokken staan. Ze kunnen echter niet bovenop luchtbellen of lege vierkanten staan.

Luchtbellen kunnen onder groene vierkanten en onder andere luchtbellen hangen. Ze kunnen echter niet onder lege vierkanten hangen.

Dit is de volledig opgeloste puzzel, met één luchtbel en één rotsblok in elk gebied.

Dit soort puzzels is vrij eenvoudig als je het eenmaal onder de knie hebt, maar je kunt bij het oplossen best een potlood gebruiken zodat je je fouten kunt uitwissen. Dit zijn alvast nog enkele puzzels om te oefenen. Klik hier om de oplossingen te bekijkenKlik hier om de oplossingen te verbergen.

Opgave

Een bellen en blokken puzzel wordt beschreven in een tekstbestand dat bestaat uit $$m$$ regels die elk één rij van het $$m \times n$$ rooster beschrijven (van boven naar onder). Elke regel bevat $$n$$ karakters die de vierkanten op de corresponderende rij van het rooster beschrijven (van links naar rechts). Alle vierkanten die tot hetzelfde gebied behoren, worden aangeduid met dezelfde hoofdletter. Groene vierkanten die tot geen enkel gebied behoren, worden aangeduid met hekjes (#). Dit is bijvoorbeeld de inhoud van het bestand dat de puzzel uit de inleiding beschrijft (puzzel.txt¹):

#AAB
CDDB
CDBB
CD#B

De rijen van het rooster worden van boven naar onder genummerd, en de kolommen van links naar rechts, telkens vanaf nul. Op die manier kunnen we de positie van een vierkant in het rooster voorstellen als een tuple $$(r, k)$$, waarbij $$r$$ (int) het nummer is van de rij en $$k$$ (int) het nummer van de kolom waarop het vierkant voorkomt in het rooster.

Definieer een klasse Puzzel waarmee bellen en blokken puzzels kunnen voorgesteld en opgelost worden. Bij het aanmaken van een nieuwe puzzel (Puzzel) moet de locatie (str) doorgegeven worden van een tekstbestand met de beschrijving van de puzzel. Een puzzel $$p$$ (Puzzel) moet minstens de volgende eigenschappen hebben:

• rijen: het aantal rijen (int) in het rooster van puzzel $$p$$

• kolommen: het aantal kolommen (int) in het rooster van puzzel $$p$$

• gebieden: een verzameling (set) met de hoofdletters (str) waarmee de gebieden in het rooster van puzzel $$p$$ aangeduid worden

Als er een puzzel $$p$$ (Puzzel) wordt doorgegeven aan de ingebouwde functie str, dan moet die een stringvoorstelling van het rooster teruggeven die aangeeft waar er reeds luchtbellen en rotsblokken geplaatst werden in puzzel $$p$$. Die voorstelling heeft dezelfde vorm als de inhoud van het tekstbestand dat puzzel $$p$$ beschrijft, maar waarbij de volgende symbolen gebruikt worden om de toestand van de vierkanten voor te stellen:

• een hekje (#): een groen vierkant

• een hoofdletter O: een vierkant waarin een luchtbel geplaatst werd

• een asterisk (*): een vierkant waarin een rotsblok geplaatst werd

• een punt (.): een leeg vierkant (geen van bovenstaande gevallen)

Voorts moet je op elke puzzel $$p$$ (Puzzel) minstens de volgende methoden kunnen aanroepen:

• Een methode vierkanten waaraan een hoofdletter (str) moet doorgegeven worden. Als de hoofdletter geen gebied in het rooster van puzzel $$p$$ aanduidt, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig gebied. Anders moet de methode een verzameling (set) teruggeven met de posities (tuple) van alle vierkanten in het rooster van puzzel $$p$$ die tot het corresponderende gebied behoren.

• Een methode luchtbel waaraan een hoofdletter (str) moet doorgegeven worden. Als de hoofdletter geen gebied in het rooster van puzzel $$p$$ aanduidt, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig gebied. Anders moet de methode de positie (tuple) teruggeven van het vierkant in het corresponderende gebied waarin een luchtbel geplaatst werd, of de waarde None als het gebied nog geen luchtbel bevat.

• Een methode rotsblok waaraan een hoofdletter (str) moet doorgegeven worden. Als de hoofdletter geen gebied in het rooster van puzzel $$p$$ aanduidt, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig gebied. Anders moet de methode de positie (tuple) teruggeven van het vierkant in het corresponderende gebied waarin een rotsblok geplaatst werd, of de waarde None als het gebied nog geen rotsblok bevat.

• Een methode isleeg waaraan twee getallen $$r$$ en $$k$$ (int) moeten doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven die aangeeft of $$(r, k)$$ de positie is van een leeg vierkant binnen het rooster van puzzel $$p$$: een vierkant binnen het rooster dat niet groen gekleurd is en waar geen luchtbel of rotsblok geplaatst werd.

• Een methode plaats_luchtbel waaraan twee getallen $$r$$ en $$k$$ (int) moeten doorgegeven worden. Als er op positie $$(r, k)$$ geen luchtbel kan geplaatst worden in het rooster van puzzel $$p$$ dan moet een AssertionError opgeworpen worden met de boodschap ongeldige positie. Dat is het geval als $$(r, k)$$ geen positie is van een leeg vierkant binnen het rooster van puzzel $$p$$, als een luchtbel op die positie niet op de bovenste rij of onder een groen vierkant of een andere luchtbel zou hangen, of als er op een andere positie in hetzelfde gebied al een luchtbel geplaatst werd. Anders moet de methode een luchtbel plaatsen op positie $$(r, k)$$ in het rooster van puzzel $$p$$ en een verwijzing naar puzzel $$p$$ teruggeven.

• Een methode plaats_rotsblok waaraan twee getallen $$r$$ en $$k$$ (int) moeten doorgegeven worden. Als er op positie $$(r, k)$$ geen rotsblok kan geplaatst worden in het rooster van puzzel $$p$$ dan moet een AssertionError opgeworpen worden met de boodschap ongeldige positie. Dat is het geval als $$(r, k)$$ geen positie is van een leeg vierkant binnen het rooster van puzzel $$p$$, als een rotsblok op die positie niet op de onderste rij of op een groen vierkant of een ander rotsblok zou staan, of als er op een andere positie in hetzelfde gebied al een rotsblok geplaatst werd. Anders moet de methode een rotsblok plaatsen op positie $$(r, k)$$ in het rooster van puzzel $$p$$ en een verwijzing naar puzzel $$p$$ teruggeven.

• Een methode isopgelost waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven die aangeeft of puzzel $$p$$ werd opgelost. Aangezien de twee voorgaande methoden ervoor zorgen dat luchtbellen en rotsblokken enkel op geldige posities kunnen neergezet worden, moet deze methode dus enkel nog controleren of er in elk gebied van het rooster van puzzel $$p$$ een luchtbel en een rotsblok geplaatst werd.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat het tekstbestand puzzel.txt² zich in de huidige directory bevindt.

>>> puzzel = Puzzel('puzzel.txt3')
>>> puzzel.rijen
4
>>> puzzel.kolommen
4
>>> puzzel.gebieden
{'A', 'B', 'C', 'D'}
>>> puzzel.vierkanten('A')
{(0, 1), (0, 2)}
>>> puzzel.vierkanten('B')
{(0, 3), (1, 3), (2, 2), (2, 3), (3, 3)}
>>> puzzel.vierkanten('C')
{(1, 0), (2, 0), (3, 0)}
>>> puzzel.vierkanten('D')
{(1, 1), (1, 2), (2, 1), (3, 1)}
>>> puzzel.vierkanten('E')
Traceback (most recent call last):
AssertionError: ongeldig gebied
>>> puzzel.luchtbel('A')
>>> puzzel.rotsblok('B')
>>> puzzel.luchtbel('E')
Traceback (most recent call last):
AssertionError: ongeldig gebied
>>> print(puzzel)
#...
....
....
..#.
>>> puzzel.isopgelost()
False
>>> puzzel.isleeg(0, 1)
True
>>> print(puzzel.plaats_luchtbel(0, 1))
#O..
....
....
..#.
>>> puzzel.luchtbel('A')
(0, 1)
>>> puzzel.rotsblok('A')
>>> puzzel.isleeg(0, 1)
False
>>> puzzel.isleeg(0, 2)
True
>>> puzzel.plaats_luchtbel(0, 2)    # tweede luchtbel in gebied A
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> puzzel.isleeg(2, 0)
True
>>> puzzel.plaats_rotsblok(2, 0)    # rotsblok zweeft boven leeg vierkant
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> puzzel.isleeg(3, 0)
True
>>> print(puzzel.plaats_rotsblok(3, 0))
#O..
....
....
*.#.
>>> puzzel.luchtbel('C')
>>> puzzel.rotsblok('C')
(3, 0)
>>> puzzel.isopgelost()
False
>>> puzzel.plaats_rotsblok(2, 0)    # tweede rotsblok in gebied C
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> puzzel.plaats_luchtbel(3, 2)    # luchtbel in groen vierkant
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> puzzel.plaats_luchtbel(2, 2)    # luchtbel hangt onder leeg vierkant
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> puzzel.plaats_rotsblok(1, 2)    # rotsblok zweeft boven leeg vierkant
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> print(puzzel.plaats_luchtbel(1, 1).plaats_rotsblok(2, 2).plaats_rotsblok(1, 2))
#O..
.O*.
..*.
*.#.
>>> puzzel.isopgelost()
False
>>> puzzel.plaats_luchtbel(3, 3)    # luchtbel hangt onder leeg vierkant
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> print(puzzel.plaats_luchtbel(1, 0).plaats_rotsblok(0, 2).plaats_luchtbel(0, 3))
#O*O
OO*.
..*.
*.#.
>>> puzzel.isopgelost()
True

Epiloog

Tot nu toe gaven we enkel voorbeelden van kleinere puzzels met een vierkant $$4 \times 4$$ rooster. Hieronder vind je een ietwat grotere puzzel met een rechthoekig $$5 \times 7$$ rooster die ook gebruikt wordt om de oplossingen te testen die je voor deze opgave indient. Klik hier om de unieke oplossing van deze puzzel te bekijkenKlik hier om de unieke oplossing van deze puzzel te verbergen.