Tents

A single player game in which trees are arranged in a grid and the player places pairwise non-adjacent tents next to them so that trees and tents can be matched.

Description

Tents is a single player game played on a rectangular grid. Initially, each cell of the grid is either empty or it is occupied by a tree. A hint, i.e., a non-negative integer, is associated with each row and each column of the grid.

The player can place tents into empty cells with the goal of satisfying the following conditions:

The figure shows a solved instance of Tents.

Computational complexity

The problem of deciding whether an instance of Tents admits a solution is NP-Complete [1].

The variant of the problem in which there are no hints (and hence the number of tents in each row/column is unconstrained) is also NP-Complete [1].

References

Picture by Wikipedia user Tulp8 (CC BY-SA 4.0).

[1] M. De Biasi, “The Complexity of Camping”.

@misc{cog:tents,
    author = "{CoG contributors}",
    title  = "{Tents --- Complexity of Games}",
    year   = "2022",
    url    = "https://www.isnphard.com/i/tents/",
    note   = "[Online; accessed 2022-02-06]"
}