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).

opgave
Opgave van een Shikaku-puzzel.
oplossing
Oplossing van de Shikaku-puzzel.

Opgave

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.

Rechthoek

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:

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.

Shikaku

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:

Voorbeeld

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