Problem 61062. A Nedlish Country Garden - Check for Valid Arrangement

Nedland is famous for its stately gardens, which typically have a centerpiece of a square grid, with certain squares featuring an elaborate potted-plant display. Nedlish design principles dictate that true garden serenity is achieved only if these displays are arranged such that each one can be seen from the edge of the grid in a straight line horizontally, vertically, and diagonally, without any other pot getting in the way. That is, each pot must be placed in a different row, and in a different column, and on different diagonals:
A 5-by-5 checkerboard has five flower pots on it, in locations (1,5), (2,2), (3,4), (4,1), and (5,3). Lines through the pot at (2,2) illustrate how this is a valid arrangement. The second row and second column have no other pots. The main diagonal (1,1), (2,2), (3,3), etc, also has no other pots. Nor does the antidiagonal through (2,2): (3,1), (2,2), and (1,3).
If any pot has another pot on the same row, column, or diagonals, that is an invalid arrangement, causing visitors to the garden significant aesthetic anguish, and resulting in the gardener being subjected to endless ridicule and shame:
The same 5-by-5 checkerboard as before, but now the pots are in locations (1,5), (2,2), (3,4), (4,3), and (5,1). A line through the antidiagonal through (4,3) and (3,4) shows that this is an invalid arrangement, as these two pots share the same antidiagonal.
Obviously, the goal is to have as many pots as possible. The requirement of each pot being on its own row (or column) immediately limits that maximum to the size of the height (or width) of the grid.
To reduce stress among Nedland's already mentally fragile gardening community, the Nedland Association for Topiary Organization is developing tools to verify a gardener's proposed arrangement. Given an n-by-n matrix P, where P(j,k) = 1 if there is a pot on the (j,k)th square, and P(j,k) = 0 otherwise, determine whether P represents a valid Nedlish garden arrangement. That is, check whether each row and each column of P contains exactly one 1, and that no diagonal (or antidiagonal) has more than one 1.
Examples
Valid arrangement
>> P = [0 0 0 0 1;0 1 0 0 0;0 0 0 1 0;1 0 0 0 0;0 0 1 0 0]
P =
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
>> ok = isvalidgarden(P)
ok =
logical
1
Invalid arrangement due to two pots sharing a diagonal
>> P = [0 0 0 0 1;0 1 0 0 0;0 0 1 0 0;1 0 0 0 0;0 0 0 1 0]
P =
0 0 0 0 1
0 1 0 0 0
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
>> ok = isvalidgarden(P)
ok =
logical
0
Invalid arrangement due to insufficient pots
>> P = [0 0 0 0 1;0 0 0 0 0;0 0 1 0 0;1 0 0 0 0;0 0 0 1 0]
P =
0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
>> ok = isvalidgarden(P)
ok =
logical
0
Assumptions
The input will be a square matrix of 0s and 1s. It can be verified that there is no valid arrangement when n = 2 or n = 3. Thankfully, no self-respecting Nedlish gardener would even consider a layout smaller than 4-by-4, so you can assume n ≥ 4. Return a logical true if P represents a valid arrangement, or false if not.
Solve

Solution Stats

63.82% Correct | 36.18% Incorrect
Last Solution submitted on Dec 03, 2025

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers75

Suggested Problems

More from this Author33

Problem Tags

diagonals indexing matrix

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!