Bij het kamperen is de keuze waar je je tent opzet essentieel: liefst op een schaduwrijke plaats zodat je tent ‘s ochtends niet te hard opwarmt en ook liefst niet te dicht bij andere kampeerders. Helaas is dat een nogal moeilijk¹ probleem.

Gelukkig kan jij een oplossing programmeren!

Probleem

Gegeven is een rooster van \(r\) rijen en \(k\) kolommen waarop een aantal bomen staan, en voor elke rij en kolom een getal dat zegt hoeveel tenten er exact in die rij of kolom moeten staan. Bijvoorbeeld:

Gevraagd is een ingevuld rooster waarop tenten staan ingevuld zodat:

• er precies evenveel bomen als tenten zijn
• geen enkele tent naast een andere tent staat (horizontaal, verticaal of diagonaal)
• elke tent naast minstens één boom staat (horizontaal, verticaal of diagonaal)
• het aantal tenten in elke rij en kolom exact gelijk is aan de gevraagde hoeveelheid tenten in die rij of kolom

Een geldige oplossing van bovenstaand voorbeeld ziet er zo uit:

Implementatiedetails

Schrijf een klasse MijnTentjesPlaatser die de gegeven interface TentjesPlaatser² implementeert. Daarin wordt gevraagd om de methode char[][] plaatsTentjes(char[][] veld, int[] rijen, int[] kolommen) te implementeren.

Een veld met bomen wordt voorgesteld door een tweedimensionale char[][]-tabel waarbij een boom voorgesteld wordt door een hoofdletter 'B' en een lege plaats (waar een tent kan staan) voorgesteld wordt door een spatie (' '). Tenten moet je plaatsen met een hoofdletter 'T'.

Het is verplicht om een backtracking-algoritme te schrijven dat een geldige oplossing zoekt voor het gegeven veld. Als er geen oplossingen zijn geef je null terug. Je mag de gegeven input niet aanpassen. Je mag veronderstellen dat elke opgave met een oplossing ook een oplossing heeft met de extra voorwaarde dat bij elke boom juist één tent hoort.

Gebruik de testklasse SimpleTest³ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.