Akari is een Japanse puzzel die gespeeld wordt op een rechthoekig rooster met witte en zwarte cellen.

Het doel is om lampen in de witte cellen te plaatsen zodat twee lampen nooit rechtstreeks op elkaar schijnen en zodat het volledige spelbord verlicht wordt.

Daarbij zendt een lamp horizontaal en verticaal lichtstralen uit, en verlicht de hele rij en kolom waarop de lamp staat, tenzij het licht geblokkeerd wordt door een zwarte cel.

Een zwarte cel kan gemarkeerd zijn met een getal van 0 tot 4. Dat getal geeft aan hoeveel lampen op horizontaal of verticaal aangrenzende witte cellen rondom de zwarte cel moeten geplaatst worden: een zwarte cel met een 4 moet bijvoorbeeld omgeven worden door 4 lampen, en rondom een zwarte cel met een 0 mogen geen lampen geplaatst worden. Rondom een zwarte cel zonder getal kan een willekeurig aantal lampen geplaatst worden. Lampen die schuin naast een genummerde zwarte cel staan, dragen niet bij aan het aantal lampen rondom die cel. De lampen hoeven ook niet per se aan een zwarte cel te grenzen.

Opgave

Om te kunnen verwijzen naar een cel in het rechthoekig rooster van een akaripuzzel worden de rijen van boven naar onder genummerd, en de kolommen van links naar rechts, telkens vanaf nul. Daardoor kan de positie van een cel voorgesteld worden als een Array $$[r, k]$$, waarbij $$r \in \mathbb{N}$$ (Number) het rijnummer en $$k \in \mathbb{N}$$ (Number) het kolomnummer van de cel aanduidt.

Een collectie cellen in het rooster van een akaripuzzel wordt voorgesteld als een Array met de posities van de cellen. Daarbij worden de cellen altijd opgelijst van boven naar onder en van links naar rechts.

Definieer een klasse Akari waarmee het rooster van akaripuzzels kan voorgesteld worden. Bij het aanmaken van een akaripuzzel (Akari) moeten drie argumenten doorgegeven worden: i) het aantal rijen (Number) van het rooster, ii) het aantal kolommen (Number) van het rooster, en iii) een Array met de zwarte cellen in het rooster. Daarbij wordt een ongenummerde zwarte cel voorgesteld door zijn positie ($$[r, k]$$) en wordt een genummerde zwarte cel voorgesteld door een Array $$[r, k, l]$$, waarbij $$r \in \mathbb{N}$$ (Number) het rijnummer, $$k \in \mathbb{N}$$ (Number) het kolomnummer en $$l \in \mathbb{N}$$ (Number, $$0 \leq l \leq 4$$) het nummer van de cel aanduidt. Akaripuzzels (Akari) moeten minstens de volgende methoden ondersteunen:

• Een methode zwarteCellen waaraan geen argumenten moeten doorgegeven worden. De methode moet een collectie met alle zwarte cellen in het rooster teruggeven.

• Een methode lampen waaraan geen argumenten moeten doorgegeven worden. De methode moet een collectie met alle lampen in het rooster teruggeven.

• Een methode toString waaraan geen argumenten moeten doorgegeven worden. De methode moet een stringvoorstelling (String) van het rooster teruggeven. Daarin vormt elke rij een afzonderlijke regel, worden ongenummerde zwarte cellen voorgesteld door een vraagteken (?), genummerde zwarte cellen door hun nummer (0 – 4), witte cellen waarop een lamp staat door de hoofdletter L, witte cellen die door minstens één lamp verlicht worden door een asterisk (*) en alle andere witte cellen door een underscore (_).

• Een methode plaatsLamp waaraan het rijnummer $$r$$ en het kolomnummer $$k$$ van een positie in het rooster moet doorgegeven worden. De methode moet nagaan of op positie $$[r, k]$$ een lamp kan geplaatst worden. Dat is het geval als aan de volgende voorwaarden voldaan is

• positie $$[r, k]$$ valt binnen het rooster

• de cel op positie $$[r, k]$$ is wit

• de cel op positie $$[r, k]$$ is nog niet bezet door een andere lamp

• de cel op positie $$[r, k]$$ wordt niet verlicht door een andere lamp

• alle genummerde zwarte cellen die aan positie $$[r, k]$$ grenzen kunnen nog omgeven worden door minstens één bijkomende lamp

Als minstens één van deze voorwaarden niet voldaan is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige positie. Anders moet het object bijhouden dat er op positie $$[r, k]$$ een lamp geplaatst werd.

• Een methode verwijderLamp waaraan het rijnummer $$r$$ en het kolomnummer $$k$$ van een positie in het rooster moet doorgegeven worden. De methode moet de lamp die op positie $$[r, k]$$ staat terug verwijderen. Als er op positie $$[r, k]$$ geen lamp staat dan moet een AssertionError opgeworpen worden met de boodschap ongeldige positie.

• Een methode stralen waaraan het rijnummer $$r$$ en het kolomnummer $$k$$ van een positie in het rooster moet doorgegeven worden. De methode moet een collectie teruggeven met alle posities die zouden verlicht worden als er een lamp op positie $$[r, k]$$ zou geplaatst worden. Daarbij maakt het niet uit of de cel op positie $$[r, k]$$ wit of zwart is (doe alsof het een witte cel met een lamp is). De positie $$[r, k]$$ mag zelf niet in de collectie opgenomen worden (de lamp staat op de cel en daardoor wordt de cel zelf niet door de lamp verlicht).

• Een methode verlicht waaraan geen argumenten moeten doorgegeven worden. De methode moet een collectie teruggeven met de posities van alle vrije witte cellen in het rooster die door een lamp verlicht worden.

• Een methode isOpgelost waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of de akaripuzzel correct opgelost werd. Dat is het geval als alle vrije witte cellen door een lamp verlicht worden én als alle genummerde zwarte cellen omgeven worden door het gegeven aantal lampen.

Voorbeeld

> const puzzel = new Akari(6, 6, [[1, 1, 4], [2, 3, 2], [2, 5], [3, 0, 1], [3, 2], [4, 4, 0]]);
> puzzel.zwarteCellen()
[[1, 1], [2, 3], [2, 5], [3, 0], [3, 2], [4, 4]]
> puzzel.lampen()
[]
> puzzel.verlicht()
[]
> console.log(puzzel.toString())
______
_4____
___2_?
1_?___
____0_
______
> puzzel.isOpgelost()
false
> puzzel.stralen(1, 1)
[[0, 1], [1, 0], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [3, 1], [4, 1], [5, 1]]
> puzzel.stralen(2, 1)
[[2, 0], [2, 2], [3, 1], [4, 1], [5, 1]]
> puzzel.plaatsLamp(2, 1)
> puzzel.lampen()
[[2, 1]]
> puzzel.verlicht()
[[2, 0], [2, 2], [3, 1], [4, 1], [5, 1]]
> console.log(puzzel.toString())
______
_4____
*L*2_?
1*?___
_*__0_
_*____
> puzzel.isOpgelost()
false
> puzzel.plaatsLamp(3, 6)          // buiten rooster
AssertionError: ongeldige positie
> puzzel.plaatsLamp(1, 1)          // niet op witte cel
AssertionError: ongeldige positie
> puzzel.plaatsLamp(2, 1)          // cel bevat al een lamp
AssertionError: ongeldige positie
> puzzel.plaatsLamp(5, 1)          // cel wordt verlicht door andere lamp
AssertionError: ongeldige positie
> puzzel.plaatsLamp(4, 5)          // te veel lampen naast zwarte cel
AssertionError: ongeldige positie
> puzzel.plaatsLamp(0, 1)
> puzzel.plaatsLamp(1, 0)
> puzzel.plaatsLamp(1, 2)
> puzzel.lampen()
[[0, 1], [1, 0], [1, 2], [2, 1]]
> puzzel.verlicht()
[[0, 0], [0, 2], [0, 3], [0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 0], [2, 2], [3, 1], [4, 1], [5, 1]]
> console.log(puzzel.toString())
*L****
L4L***
*L*2_?
1*?___
_*__0_
_*____
> puzzel.isOpgelost()
false
> puzzel.verwijderLamp(1, 2)
> puzzel.lampen()
[[0, 1], [1, 0], [2, 1]]
> console.log(puzzel.toString())
*L****
L4____
*L*2_?
1*?___
_*__0_
_*____
> puzzel.plaatsLamp(1, 2)
> console.log(puzzel.toString())
*L****
L4L***
*L*2_?
1*?___
_*__0_
_*____
> puzzel.verwijderLamp(2, 2)
AssertionError: ongeldige positie
> puzzel.plaatsLamp(2, 4)
> puzzel.plaatsLamp(3, 3)
> puzzel.plaatsLamp(4, 0)
> puzzel.plaatsLamp(5, 5)
> puzzel.lampen()
[[0, 1], [1, 0], [1, 2], [2, 1], [2, 4], [3, 3], [4, 0], [5, 5]]
> puzzel.verlicht()
[[0, 0], [0, 2], [0, 3], [0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 0], [2, 2], [3, 1], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 5], [5, 0], [5, 1], [5, 2], [5, 3], [5, 4]]
> console.log(puzzel.toString())
*L****
L4L***
*L*2L?
1*?L**
L***0*
*****L
> puzzel.isOpgelost()
true

Epiloog

Dit is een vrij moeilijke puzzel. Kan je die ook oplossen?

 Antwoord weergeven¹