# 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:

- Each cell contains at most one tent.
- No two horizontally, vertically, or diagonally adjacent cells both contain a tent.
- The number of tents in each row (resp. column) is equal to the hint associated with the corresponding row (resp. column).
- There is a perfect matching between trees and tents so that each matched tree is matched to an orthogonally adjacent tree.

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”.