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
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 . . . . . .
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.
This uses the same notation as the above example;
T for trees,
A for tents, and
. for empty spaces.
. . . . . . . . . (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 . .
(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 . .