Bij Star Battle¹ krijg je een getal $$n \in \mathbb{N}_0$$ en een vierkant $$s \times s$$ rooster dat onderverdeeld is in $$s \in \mathbb{N}_0$$ samenhangende gebieden. De unieke oplossing van de puzzel vind je door $$n \times s$$ sterren in het rooster te plaatsen zodat

elke rij $$n$$ sterren bevat
elke kolom $$n$$ sterren bevat
elk gebied $$n$$ sterren bevat
twee sterren elkaar nooit horizontaal, verticaal of diagonaal raken

Hieronder zie je aan de linkerkant de opgave van een puzzel met een $$12 \times 12$$ rooster. De 12 gebieden worden aangeduid door een dikkere rand. In de rechterbovenhoek wordt aangegeven dat $$n = 2$$. Aan de rechterkant zie je de unieke oplossing met $$2 \times 12 = 24$$ sterren. Speciaal aan deze opgave is dat je het aantal sterren ook tweemaal terugziet in de vorm van de gebieden.

De opgave (links) en de oplossing (rechts) van een Star Battle puzzel ontworpen door Thomas Snyder.

Opgave

In een rooster nummeren we de rijen van boven naar onder en de kolommen van links naar rechts, telkens oplopend vanaf nul. De positie van een cel in het rooster kan daardoor aangeduid worden met een array $$[r, k]$$ (Array), waarbij $$r$$ (Number) en $$k$$ (Number) het nummer aangeven van respectievelijk de rij en de kolom waarin de cel gelegen is.

Gebied

Definieer een klasse Gebied waarmee een selectie van cellen in een rooster kan voorgesteld worden. Bij het aanmaken van een gebied (Gebied) moet een reeks (Array) met de posities van de geselecteerde cellen doorgegeven worden. Hierbij mag je ervan uitgaan dat dezelfde positie nooit meerdere keren voorkomt in de gegeven reeks, zonder dat dit expliciet moet gecontroleerd worden. Een gebied $$g$$ (Gebied) gedraagt zich als een onveranderlijk (immutable) object en moet minstens de volgende methoden hebben:

Een methode toString waaraan geen argumenten moeten doorgegeven worden. De methode moet een string (String) teruggeven die leest als een JavaScript expressie waarmee een nieuw gebied aangemaakt wordt met dezelfde selectie cellen als $$g$$. Daarbij moet de selectie cellen voorgesteld worden als een reeks (Array) waarin de cellen van links naar rechts, en van boven naar onder opgelijst worden.
Een methode grootte waaraan geen argumenten moeten doorgegeven worden. De methode moet het aantal geselecteerde cellen (Number) in het gebied teruggeven.
Een methode bevat waaraan de positie $$c$$ van een cel in een rooster moet doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of $$c$$ geselecteerd is in $$g$$.
Een methode doorsnede waaraan een gebied $$h$$ (Gebied) moet doorgegeven worden. De methode moet een gebied (Gebied) teruggeven met alle cellen die geselecteerd zijn in $$g$$ en in $$h$$.
Een methode unie waaraan een gebied $$h$$ (Gebied) moet doorgegeven worden. De methode moet een gebied (Gebied) teruggeven met alle cellen die geselecteerd zijn in $$g$$ of in $$h$$.
Een methode isGelijkAan waaraan een gebied $$h$$ (Gebied) moet doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of $$g$$ en $$h$$ dezelfde selectie van cellen voorstellen.
Een methode isIngeslotenIn waaraan een gebied $$h$$ (Gebied) moet doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of alle cellen die geselecteerd zijn in $$g$$ ook geselecteerd zijn in $$h$$.
Een methode overlaptMet waaraan een gebied $$h$$ (Gebied) moet doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of $$g$$ en $$h$$ minstens één geselecteerde cel gemeenschappelijk hebben.
Een methode isVerspreid waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven, die aangeeft of twee geselecteerde cellen elkaar nooit horizontaal, verticaal of diagonaal raken.
Een methode isSamenhangend waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven, die aangeeft of de geselecteerde cellen één samenhangend gebied vormen van cellen die elkaar horizontaal of verticaal raken.

Rooster

Definieer een klasse Rooster waarmee de oplossing van een Star Battle puzzel kan voorgesteld worden. Bij het aanmaken van een rooster (Rooster) moeten twee argumenten doorgegeven worden: i) de dimensie $$s$$ (Number) van het rooster (het aantal rijen en kolommen) en ii) een reeks (Array) met de posities van de sterren in het rooster. Daarbij moet gelden dat

alle sterren binnen het rooster liggen
het aantal sterren een veelvoud is van de dimensie van het rooster
twee sterren elkaar nooit horizontaal, verticaal of diagonaal raken

Als dat niet het geval is dan moet een AssertionError opgeworpen worden met de boodschap ongeldig rooster.

Een rooster $$r$$ (Rooster) moet minstens de volgende methoden ondersteunen:

Een methode toString waaraan geen argumenten moeten doorgegeven worden. De methode moet een string (String) teruggeven waarin elke rij van $$r$$ wordt weergegeven op een afzonderlijke regel. Cellen met een ster worden voorgesteld door een asterisk (*) en cellen zonder ster door een punt (.).
Een methode aantalSterren waaraan een gebied $$g$$ (Gebied) moet doorgegeven worden. De methode moet teruggeven hoeveel sterren (int) in $$r$$ ook in $$g$$ gelegen zijn.
Een methode voegGebiedToe waaraan een gebied $$g$$ (Gebied) moet doorgegeven worden waarvoor geldt dat
- $$g$$ volledig binnen $$r$$ ligt
- $$g$$ samenhangend is
- $$g$$ het verwachte aantal sterren bevat
- $$g$$ niet overlapt met één van de andere gebieden van $$r$$
Als dat niet het geval is dan moet een AssertionError opgeworpen worden met de boodschap ongeldig gebied. Anders moet $$g$$ bijgehouden worden als één van de gebieden van $$r$$.
Een methode isBedekt waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (Boolean) teruggeven die aangeeft of $$r$$ volledig bedekt is door gebieden. Dat is het geval als elke cel van $$r$$ in één van de gebieden van $$r$$ ligt.

Voorbeeld

        > const gebied1 = new Gebied([[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]]);
> console.log(gebied1.toString())
Gebied([[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]])
> gebied1.grootte()
6
> gebied1.isVerspreid()
false
> gebied1.isSamenhangend()
true
> const gebied2 = new Gebied([[0, 2], [0, 3], [1, 2], [2, 2], [3, 2], [3, 3], [4, 2], [4, 3], [5, 2], [5, 3]]);
> console.log(gebied2.toString())
Gebied([[0, 2], [0, 3], [1, 2], [2, 2], [3, 2], [3, 3], [4, 2], [4, 3], [5, 2], [5, 3]])
> gebied2.grootte()
10
> gebied2.isVerspreid()
false
> gebied2.isSamenhangend()
true
> const onsamenhangend = new Gebied([[0, 0], [0, 1], [1, 0], [4, 5], [5, 4], [5, 5]]);
> console.log(onsamenhangend.toString())
Gebied([[0, 0], [0, 1], [1, 0], [4, 5], [5, 4], [5, 5]])
> onsamenhangend.grootte()
6
> onsamenhangend.isVerspreid()
false
> onsamenhangend.isSamenhangend()
false
> const verspreid = new Gebied([[0, 2], [1, 0], [2, 3], [3, 5], [4, 1], [5, 4]]);
> console.log(verspreid.toString())
Gebied([[0, 2], [1, 0], [2, 3], [3, 5], [4, 1], [5, 4]])
> verspreid.grootte()
6
> verspreid.isVerspreid()
true
> verspreid.isSamenhangend()
false
> gebied1.unie(gebied2).grootte()
16
> gebied1.unie(onsamenhangend).grootte()
9
> new Gebied([[0, 1], [1, 0], [0, 0]]).isIngeslotenIn(gebied1)
true
> gebied1.overlaptMet(gebied2)
false
> gebied1.doorsnede(gebied2).grootte()
0
> gebied1.overlaptMet(onsamenhangend)
true
> const doorsnede = gebied1.doorsnede(onsamenhangend);
> doorsnede.grootte()
3
> doorsnede.bevat([0, 0])
true
> doorsnede.bevat([1, 0])
true
> doorsnede.bevat([0, 1])
true
> doorsnede.bevat([4, 5])
false
> console.log(doorsnede.toString())
Gebied([[0, 0], [0, 1], [1, 0]])
> console.log(gebied1.unie(onsamenhangend).toString())
Gebied([[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1], [4, 5], [5, 4], [5, 5]])
> gebied2.overlaptMet(onsamenhangend)
false
> gebied1.isGelijkAan(gebied1)
true
> gebied1.isGelijkAan(gebied2)
false

> const rooster = new Rooster(6, [[0, 2], [1, 0], [2, 3], [3, 5], [4, 1], [5, 4]]);
> console.log(rooster.toString())
..*...
*.....
...*..
.....*
.*....
....*.
> rooster.aantalSterren(gebied1)
1
> rooster.aantalSterren(gebied2)
1
> rooster.voegGebiedToe(gebied1)
> rooster.isBedekt()
false
> rooster.voegGebiedToe(gebied2)
> rooster.isBedekt()
false
> rooster.voegGebiedToe(onsamenhangend)
AssertionError: ongeldig gebied
> rooster.voegGebiedToe(new Gebied([[0, 4], [0, 5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]]))
> rooster.voegGebiedToe(new Gebied([[3, 0], [3, 1], [4, 0], [4, 1], [5, 0], [5, 1]]))
> rooster.voegGebiedToe(new Gebied([[3, 4], [3, 5], [4, 4]]))
> rooster.isBedekt()
false
> rooster.voegGebiedToe(new Gebied([[4, 5], [5, 4], [5, 5]]))
> rooster.isBedekt()