Shikaku (四角に切れ, shikaku ni kire) is een logische puzzel die bestaat uit een rechthoekig rooster waarvan sommige cellen genummerd zijn met strikt positieve natuurlijke getallen. Het doel is om het rooster in rechthoekige stukken te verdelen, zodat elk stuk een aantal cellen volledig bedekt. Het aantal cellen dat door een rechthoek bedekt wordt, noemen we de oppervlakte van de rechthoek. Bovendien moet elke rechthoek precies één genummerde cel bedekken waarvan het getal gelijk is aan de oppervlakte van de rechthoek. Een gevolg hiervan is dat de oppervlakte van het rooster gelijk moet zijn aan de som van alle getallen in het rooster. Dit is bijvoorbeeld de opgave (links) van een $$5 \times 6$$ puzzel met bijhorende oplossing (rechts).
Om naar de cellen in het rooster van een Shikaku-puzzel te kunnen verwijzen, worden de rijen van boven naar onder genummerd en de kolommen van links naar rechts, telkens vanaf nul. De positie van een cel in het rooster wordt voorgesteld door een tuple $$(r, k)$$, waarbij $$r \in \mathbb{N}$$ (int) het rijnummer en $$k \in \mathbb{N}$$ (int) het kolomnummer aanduidt.
Definieer een klasse Rechthoek waarmee rechthoekige stukken van Shikaku-puzzels kunnen voorgesteld worden. Bij het aanmaken van een rechthoek (Rechthoek) moeten er drie of vier natuurlijke getallen $$r$$, $$k$$, $$h$$ en optioneel ook $$b$$ doorgegeven worden. Daarbij is $$(r, k)$$ de positie van de cel in het rooster van de puzzel die bedekt wordt door de linkerbovenhoek van de rechthoek, $$h$$ de hoogte van de rechthoek (uitgedrukt als een aantal rijen) en $$b$$ de breedte van de rechthoek (uitgedrukt als een aantal kolommen). We noemen $$(r, k)$$ ook de positie van de rechthoek. Als er geen vierde argument wordt doorgegeven, dan is de rechthoek een vierkant waarvan de breedte ($$b$$) en de hoogte ($$h$$) gelijk zijn.
Als er een rechthoek $$R$$ (Rechthoek) wordt doorgegeven aan de ingebouwde functie repr, dan moet die een expressie (str) teruggeven waarmee een nieuwe rechthoek (Rechthoek) aangemaakt wordt met dezelfde positie, hoogte en breedte als de rechthoek $$R$$. Daarbij moeten er altijd vier argumenten doorgeven worden (ook al zijn de hoogte en breedte gelijk), en moeten de argumenten telkens van elkaar gescheiden worden door een komma (,) en een spatie.
Daarnaast moet een rechthoek $$R$$ (Rechthoek) minstens ook de volgende methoden ondersteunen:
Een methode oppervlakte waaraan geen argumenten moeten doorgegeven worden. De methode moet de oppervlakte van $$R$$ (int) teruggeven.
Een methode cellen waaraan geen argumenten moeten doorgegeven worden. De methode moet een verzameling (set) teruggeven met de posities van alle cellen in het rooster die door $$R$$ bedekt worden.
Zorg er voor dat de ingebouwde operator <= voor twee rechthoeken (Rechthoek) $$R_1$$ en $$R_2$$ (R1 <= R2) een Booleaanse waarde (bool) oplevert die aangeeft of $$R_1$$ volledig ingesloten zit in de $$R_2$$. Anders gezegd, of alle cellen die bedekt worden door $$R_1$$ ook bedekt worden door $$R_2$$.
Zorg er voor dat de ingebouwde operator & voor twee rechthoeken (Rechthoek) $$R_1$$ en $$R_2$$ (R1 & R2) een rechthoek (Rechthoek) oplevert die alle cellen bedekt die zowel door $$R_1$$ als door $$R_2$$ bedekt worden. Als $$R_1$$ en $$R_2$$ geen gemeenschappelijke cellen bedekken, dan moet de operator & de waarde None opleveren.
Definieer ook nog een klasse Shikaku waarmee Shikaku-puzzels kunnen voorgesteld worden, waarin rechthoekige stukken kunnen aangeduid en terug verwijderd worden. Bij het aanmaken van een puzzel (Shikaku) moet de locatie (str) doorgegeven worden van een tekstbestand dat de opgave van de puzzel beschrijft. De eerste regel van het bestand bevat twee natuurlijke getallen $$m$$ en $$n$$ die van elkaar gescheiden worden door een spatie. Ze geven aan dat het rooster van de puzzel bestaat uit $$m$$ rijen en $$n$$ kolommen. Daarna volgt voor elke genummerde cel in het rooster een regel waarop drie natuurlijke getallen staan die van elkaar gescheiden worden door een spatie: i) het rijnummer van de cel, ii) het kolomnummer van de cel en iii) het getal in de cel. De puzzel uit de inleiding wordt bijvoorbeeld beschreven door het volgende bestand:
5 6 0 3 10 1 5 5 2 0 2 3 2 9 4 0 4
Je mag ervan uitgaan dat het bestand altijd een geldige puzzel beschrijft, zonder dat dit expliciet moet gecontroleerd worden: alle cellen liggen in het rooster en de oppervlakte van het rooster is gelijk aan de som van alle getallen in het rooster. Bij aanvang zijn er nog geen rechthoekige stukken aangeduid in het rooster. Een puzzel (Shikaku) moet minstens de volgende methoden ondersteunen:
Een methode cellen waaraan een rechthoek $$R$$ (Rechthoek) moet doorgegeven worden. De methode moet een lijst (list) teruggeven met de posities van alle genummerde cellen van het rooster die door $$R$$ bedekt worden. De posities moeten opgelijst worden in de volgorde waarin je de cellen tegenkomt als je het rooster van links naar rechts en van boven naar onder doorloopt.
Een methode getallen waaraan een rechthoek $$R$$ (Rechthoek) moet doorgegeven worden. De methode moet een lijst (list) teruggeven met de getallen (int) in alle genummerde cellen van het rooster die door $$R$$ bedekt worden. De getallen moeten opgelijst worden in de volgorde waarin je de cellen tegenkomt als je het rooster van links naar rechts en van boven naar onder doorloopt.
Een methode onbedekt waaraan geen argumenten moeten doorgegeven worden. De methode moet een verzameling (set) teruggeven met de posities van alle genummerde cellen van het rooster die nog niet door een rechthoek bedekt zijn.
Een methode bedekken waaraan een rechthoek $$R$$ (Rechthoek) moet doorgegeven worden. De methode moet ervoor zorgen dat wordt bijgehouden dat de cellen van $$R$$ nu bedekt zijn, als aan de volgende voorwaarden voldaan is:
$$R$$ bedekt enkel cellen die in het rooster van de puzzel gelegen zijn
$$R$$ bedekt geen cellen die al door andere rechthoeken bedekt zijn
$$R$$ bedekt slechts één genummerde cel
de oppervlakte van $$R$$ is gelijk aan het getal in de genummerde cel die door $$R$$ bedekt wordt
Als minstens één van deze voorwaarden niet voldaan is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige rechthoek.
Een methode verwijderen waaraan de positie van een genummerde cel moet doorgegeven worden. Als de genummerde cel niet door een rechthoek bedekt wordt, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige positie. Anders moet de methode de rechthoek weghalen die de genummerde cel bedekt, waardoor alle cellen die door deze rechthoek bedekt werden niet langer bedekt zijn.
Een methode isopgelost waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven die aangeeft of alle genummerde cellen door rechthoeken bedekt zijn.
In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand shikaku.txt1 zich in de huidige directory bevindt.
>>> groen = Rechthoek(0, 5, 5, 1)
>>> groen
Rechthoek(0, 5, 5, 1)
>>> groen.oppervlakte()
5
>>> groen.cellen()
{(4, 5), (1, 5), (0, 5), (2, 5), (3, 5)}
>>> blauw = Rechthoek(3, 0, 2)
>>> blauw
Rechthoek(3, 0, 2, 2)
>>> blauw.oppervlakte()
4
>>> blauw.cellen()
{(3, 0), (3, 1), (4, 1), (4, 0)}
>>> groen & blauw
>>> groen & Rechthoek(1, 1, 3, 5)
Rechthoek(1, 5, 3, 1)
>>> blauw & Rechthoek(1, 1, 3, 5)
Rechthoek(3, 1, 1, 1)
>>> Rechthoek(2, 3, 3, 2) <= Rechthoek(2, 2, 3)
True
>>> groen <= blauw
False
>>> shikaku = Shikaku('shikaku.txt2')
>>> shikaku.cellen(blauw)
[(4, 0)]
>>> shikaku.getallen(blauw)
[4]
>>> shikaku.cellen(Rechthoek(1, 1, 3, 5))
[(1, 5), (3, 2)]
>>> shikaku.getallen(Rechthoek(1, 1, 3, 5))
[5, 9]
>>> shikaku.onbedekt()
{(1, 5), (2, 0), (3, 2), (0, 3), (4, 0)}
>>> shikaku.bedekken(blauw)
>>> shikaku.onbedekt()
{(1, 5), (3, 2), (2, 0), (0, 3)}
>>> shikaku.isopgelost()
False
>>> shikaku.bedekken(groen)
>>> shikaku.onbedekt()
{(2, 0), (3, 2), (0, 3)}
>>> shikaku.isopgelost()
False
>>> shikaku.bedekken(Rechthoek(1, 1, 3, 5))
Traceback (most recent call last):
AssertionError: ongeldig rechthoek
>>> shikaku.verwijderen((3, 0))
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> shikaku.verwijderen((4, 0))
>>> shikaku.onbedekt()
{(2, 0), (3, 2), (4, 0), (0, 3)}
>>> shikaku.bedekken(blauw)
>>> shikaku.bedekken(Rechthoek(0, 0, 2, 5)) # paars
>>> shikaku.bedekken(Rechthoek(2, 0, 1, 2)) # bruin
>>> shikaku.bedekken(Rechthoek(2, 2, 3)) # roze
>>> shikaku.onbedekt()
set()
>>> shikaku.isopgelost()
True