No-Repeat Garden Beds

Mediumhash mapAlso known as Valid Sudoku

A community garden is laid out as a 9 by 9 grid of plots, split into nine square beds of 3 by 3 plots. There are nine kinds of plant, numbered 1 to 9. To stop pests spreading along a line, the gardeners agreed a rule: no kind of plant may appear twice in the same row, the same column, or the same bed.

The planting plan is only partly filled in, with 0 for a plot nobody has claimed yet. Before the next work day, you want to check that what is already planned breaks no rule.

Your task

Write validPlan(plots). plots is a 9 × 9 grid, plots[r][c] being the plant in row r, column c, or 0 if the plot is empty. Bed boundaries fall after rows 2 and 5 and after columns 2 and 5.

Return true if no plant number (1 to 9) appears twice in any row, any column or any bed, and false otherwise. Empty plots never break a rule. You only check the plots already planned, not whether the empty ones could all be filled.

validPlan(plots: int[][]) → bool

Examples

Example 1

Input

plots = [[0, 2, 0, 0, 0, 0, 0, 0, 9], [0, 5, 6, 0, 8, 9, 1, 2, 0], [0, 0, 0, 1, 0, 0, 4, 0, 6], [0, 3, 4, 0, 0, 0, 0, 0, 0], [5, 6, 7, 0, 9, 1, 0, 3, 0], [0, 9, 0, 0, 0, 4, 0, 0, 7], [0, 0, 5, 0, 7, 8, 0, 0, 0], [6, 0, 8, 0, 1, 2, 0, 0, 0], [0, 1, 0, 3, 0, 0, 6, 7, 0]]

Output

true

Why

Every row, every column and every bed holds each plant at most once. Plenty of plots are empty, and that is fine.

Example 2

Input

plots = [[0, 2, 0, 0, 0, 0, 0, 0, 9], [0, 5, 6, 0, 8, 9, 1, 2, 0], [2, 0, 0, 1, 0, 0, 4, 0, 6], [0, 3, 4, 0, 0, 0, 0, 0, 0], [5, 6, 7, 0, 9, 1, 0, 3, 0], [0, 9, 0, 0, 0, 4, 0, 0, 7], [0, 0, 5, 0, 7, 8, 0, 0, 0], [6, 0, 8, 0, 1, 2, 0, 0, 0], [0, 1, 0, 3, 0, 0, 6, 7, 0]]

Output

false

Why

This is the first plan with plant 2 added at row 2, column 0. Row 2 holds 1, 4 and 6, and column 0 holds 5 and 6, so both are fine. But that plot is in the top-left bed, which already has a 2 at row 0, column 1. The bed rule is broken.

Constraints

plots has exactly 9 rows, each with exactly 9 numbers.
0 ≤ plots[r][c] ≤ 9

Start with brute force

For every planted plot, scan the rest of its row, its column and its bed, looking for the same plant.

On a 9 × 9 garden this is about 81 × 24 checks, which is small, so it is not too slow here. The real cost is the code: three different scanning loops, the fiddly bed bounds, and on a bigger n × n garden the work grows like n³. Recording each plant once in the right three groups is both shorter and faster.

Hints

0 of 4 shown

Hint 1
Take the plot at row 2, column 0 in the second example. To know whether its plant breaks a rule, which three groups of plots do you have to look at?
Hint 2
Every plot belongs to exactly one row, one column and one bed. So there are 27 groups in total, and for each one you are asking "have I seen this plant in this group before?"
Hint 3
Rows and columns are numbered by r and c. Can you number the beds 0 to 8 from r and c as well? Divide r and c by 3, rounding down, and try it on a few plots.
Hint 4
Keep 9 sets for rows, 9 for columns and 9 for beds, with bed number (r ÷ 3, rounded down) × 3 + (c ÷ 3, rounded down). Visit every plot once, skip zeros, and return false if the plant is already in its row, column or bed set. Otherwise add it to all three. Return true at the end.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The rule is really 27 small duplicate checks, one per row, column and bed. Give each of those groups its own set and visit every plot once, dropping its plant into the three sets it belongs to.

The only tricky part is the bed number. Dividing r by 3 and rounding down (Math.floor(r / 3), or r // 3 in Python) says which band of rows a plot is in: 0, 1 or 2. Doing the same with c gives the band of columns. Treat them as the row and column of a 3 × 3 grid of beds: bed = band row × 3 + band column. For example, plot (4, 7) is in band row 1, band column 2, so bed 1 × 3 + 2 = 5.

Trace the start of the second example, reading row by row:

(0, 1) = 2, bed 0. Row 0, column 1 and bed 0 all get a 2.
(0, 8) = 9, bed 2. Recorded.
Row 1 adds 5, 6, 8, 9, 1, 2. None repeats in its row, column or bed. Bed 0 now holds 2, 5, 6.
(2, 0) = 2, bed 0. Row 2 has no 2 yet and column 0 has no 2 yet, but bed 0 already has one. Return false.

A common slip is r / 3 + c / 3 as the bed number. It sends plot (0, 4) and plot (4, 0) to the same "bed" 1, though they are in different beds, and then flags a repeat that is not there.

Reference solution

function validPlan(plots) {
  const rows = [], cols = [], beds = [];
  for (let i = 0; i < 9; i++) { rows.push(new Set()); cols.push(new Set()); beds.push(new Set()); }
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const v = plots[r][c];
      if (v === 0) continue; // empty plot
      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3); // bed 0..8
      if (rows[r].has(v) || cols[c].has(v) || beds[b].has(v)) return false;
      rows[r].add(v); cols[c].add(v); beds[b].add(v);
    }
  }
  return true;
}

def valid_plan(plots):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    beds = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            v = plots[r][c]
            if v == 0:  # empty plot
                continue
            b = (r // 3) * 3 + c // 3  # bed 0..8
            if v in rows[r] or v in cols[c] or v in beds[b]:
                return False
            rows[r].add(v)
            cols[c].add(v)
            beds[b].add(v)
    return True

TimeO(n²)For an n × n garden every plot is visited once with O(1) set work; here n = 9, so 81 plots.

SpaceO(n²)The 3n sets hold at most n plants each.

Learn the idea: Hash Tables Arrays

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code