Tentje-boompje

Tentje-boompje, ook wel Tenten en Bomen of de Campingpuzzel is een logische puzzel. Het vierkante diagram van tentje-boompje stelt een camping voor. Op sommige vakjes staan bomen. De nummers aan de boven- en onderkant van het diagram geven aan hoeveel tenten er in de betreffende rij of kolom staan. De puzzel kan online en op papier worden gemaakt. De puzzels kunnen variëren in grootte en moeilijkheidsgraad.

Opgave

Het is warm en de camping staat vol met gasten. Iedereen wil een plekje in de schaduw van een van de bomen die verspreid op het terrein staan, maar niemand zit graag te dicht bij zijn buren. De campingbeheerder zoekt bij elke boom een plek voor de tent. Zo heeft elke tent zijn eigen boom. De kampeerplek moet voldoen aan onderstaande eisen:

Er zijn precies evenveel tenten als bomen.
Een tent mag echter ook naast andere bomen staan. Tenten raken elkaar nooit: noch horizontaal, noch verticaal, noch diagonaal.
Een tent kan contact maken met meerdere bomen, maar is slechts met één direct verbonden.
Het aantal tenten in elke rij en kolom moet overeenkomen met de nummers op de randen van het raster.

Strategie

Vanaf het begin kunnen met logisch nadenken al meerdere vakjes als ‘gras’ worden gemarkeerd (weggestreept)^[1]:

Rijen/kolommen met het cijfer 0
Vakjes die niet horizontaal of verticaal aan een boom grenzen
Ver van een boom verwijderde vakjes
Vakjes die enkel diagonaal zijn verbonden met een boom
Rijen/kolommen waarvan alle tenten zijn geplaatst
Soms moeten een aantal van bovenstaande regels worden herhaald om de puzzel volledig op te lossen
Als een boom nog meerdere opties voor het plaatsen van een tent heeft, maar al de opties maken het voor een bepaald vak onmogelijk om een tent te bevatten.

Sinds 1989

De puzzel werd bedacht door de Nederlander Léon Balmaekers en werd in 1989 voor het eerst gepubliceerd in het Nederlandse puzzelblad Breinbrekers, onder de naam "Alle ballen verzamelen".^[2]^[3]^[4] Varianten op het thema tentje/boompje zijn houthakker/bomen, gevangene/bewaker, bijen/bloemen en het toekennen van coronavaccins.

Computationele complexiteit

De vraag of een gegeven Tentje-boompje-puzzel een oplossing heeft is NP-volledig.^[5] Concreet betekent dat dat er geen efficiënt algoritme bestaat dat de vraag oplost (tenminste, als, zoals meestal aangenomen wordt, P ≠ NP).

Bron