Background
Tents and Trees (try here) is a puzzle played on a square (or rectangular) grid, where the objective is to place tents horizontally or vertically adjacent to each of the trees, so that no two tents touch each other in 8 directions (horizontally, vertically, and diagonally) and the number of tents on each row/column matches the given clues.
Example puzzle and solution
In these examples, trees are T
and tents are A
.
Puzzle
2 0 2 0 2 1
2 . T . T . .
1 . . . . T .
1 T . T . . .
2 . . . . . T
1 T . . . . .
0 . . . . . .
Solution
2 0 2 0 2 1
2 . T A T A .
1 A . . . T .
1 T . T . A .
2 A . A . . T
1 T . . . . A
0 . . . . . .
Challenge
Given a grid with some tents and trees, determine whether the tents are placed correctly. Ignore the number clues in this challenge. In particular, your program should check the following:
- The number of tents equals the number of trees,
- The tents do not touch each other in 8 directions, and
- There is at least one way to associate every tent with an adjacent tree in 4 directions, so that every tree is used exactly once.
If all of the above are satisfied, output a truthy value; otherwise, output a falsy value. You can choose to follow your language's convention of truthy/falsy, or use two distinct values for true/false respectively.
You may take the input in any reasonable way to represent a matrix containing three distinct values to represent a tree, a tent, and an empty space respectively.
Standard code-golf rules apply. The shortest code in bytes wins.
Test cases
This uses the same notation as the above example; T
for trees, A
for tents, and .
for empty spaces.
Truthy
. . .
. . .
. . . (empty board)
T A
A T A
. . T
A T A
T . T
A T A
(note that there are two ways to associate tents with trees)
A . .
T T A
A T T
. . A
. T A .
A . . T
T T . A
. A . .
Falsy
(The number of Ts and As don't match)
T
A
T A T
(Two A's touch each other)
T A T
A . .
A . . A
T T T T
. A A .
(Some T's are not associated with an A)
A T A
T T .
A T A
A . T
T T A
A . .