Plant Flowers in Neighborhood

Level: L3-L4 Topics: Backtracking, Constraint Satisfaction, Grid Problems

Problem Statement

You are given an N x N grid representing a neighborhood. Each cell contains either a house (H) or an empty block (0). You need to plant flowers in some of the empty blocks following these rules:

• Rule 1: Each house must have exactly one flower planted in a cell directly adjacent to it (up, down, left, or right).
• Rule 2: There must be exactly one flower in each row and exactly one flower in each column (like placing N non-attacking rooks).

Find a valid placement of flowers, or report that none exists.

Background & Constraints

• The grid is N x N where N is typically small (4 to 8).
• A house can be adjacent to multiple empty cells, but exactly one of them must receive a flower.
• A flower satisfies a house if and only if the flower is in a horizontally or vertically adjacent cell.
• Flowers can only be placed on empty (0) cells.
• A single flower can satisfy multiple houses if it is adjacent to more than one.
• Not every grid has a valid solution.

Example

Input (5x5):

0  0  0  H  0
H  0  0  0  0
0  0  0  0  H
0  H  0  0  0
0  0  H  0  0

Houses at: (0,3), (1,0), (2,4), (3,1), (4,2).

One valid output:

F  0  0  H  0
H  0  0  F  0
0  0  F  0  H
0  H  0  0  F
0  F  H  0  0

Flowers at: (0,0), (1,3), (2,2), (3,4), (4,1).

Verification — Rule 1 (each house has exactly one adjacent flower):

House	Adjacent cells	Adjacent flower(s)	Count
(0,3)	(0,2), (0,4), (1,3)	F at (1,3)	1 ✓
(1,0)	(0,0), (1,1), (2,0)	F at (0,0)	1 ✓
(2,4)	(1,4), (2,3), (3,4)	F at (3,4)	1 ✓
(3,1)	(2,1), (3,0), (3,2), (4,1)	F at (4,1)	1 ✓
(4,2)	(3,2), (4,1), (4,3)	F at (4,1)	1 ✓

Note: the flower at (4,1) satisfies both house (3,1) and house (4,2). This is valid — one flower can be adjacent to multiple houses.

Verification — Rule 2 (one flower per row, one per column):

• Rows: 0→col 0, 1→col 3, 2→col 2, 3→col 4, 4→col 1. All distinct. ✓
• Columns: col 0→row 0, col 1→row 4, col 2→row 2, col 3→row 1, col 4→row 3. All distinct. ✓

Hints & Common Pitfalls

• This is a constraint satisfaction problem. Backtracking is a natural approach.
• Process one row at a time: decide which column gets the flower in that row, check all constraints, and recurse.
• Prune early: if placing a flower in a position violates Rule 1 for any house (gives a house two adjacent flowers, or makes it impossible for a remaining house to get a flower), backtrack immediately.
• Track which houses are "satisfied" as you place flowers. At the end, verify all houses are satisfied.
• A common mistake is forgetting that a flower placed to satisfy one house might be adjacent to another house, satisfying it as well (or over-satisfying it).

Follow-Up Questions

1. Output all valid solutions: Modify your approach to enumerate every valid placement. How do you deduplicate layouts that are structurally identical (e.g., rotational symmetry)?
2. Relaxed Rule 2: Instead of exactly one flower per row and column, you are given target counts for each row and each column (e.g., row 0 needs 2 flowers, row 1 needs 1). How does this generalize the problem? What changes in your backtracking?