The frameworkhardBacktracking with incremental constraint sets4 min · 108 of 290

Greenhouse rotation

Fill a part-planted 9x9 greenhouse so every row, column and block holds each crop once, by carrying three constraint sets through the recursion.

Half the beds are already planted and the rest have to be filled in without breaking the rotation rule. A crop that fits today can still be wrong four beds later, which is what makes this a search rather than a scan.

The problem

A greenhouse floor is nine rows of nine beds, divided into nine 3×3 blocks. The nursery grows nine crops, labelled 1 to 9, and the rotation rule is that every row, every column and every 3×3 block holds each crop exactly once.

Some beds are already planted. Fill in the rest so the rule holds everywhere. The plan you are given is guaranteed to have exactly one completion.

Input. beds — nine strings of nine characters. A digit 1–9 is a bed already planted with that crop; . is an empty bed.

Output. Nine strings of nine digits: the same floor, fully planted.

Example.

beds = [".....14..",      ->  ["697381452",
        "831..49..",           "831254976",
        "..596.1..",           "245967183",
        "...5..6.7",           "183542697",
        "7........",           "769813245",
        ".2.6....8",           "524679318",
        "...7.68.1",           "452796831",
        "97..3..2.",           "976138524",
        "3.8...7.9"]           "318425769"]

Thirty beds are planted, fifty-one are empty. Bed (0,0) is only forced to 6 once the rest of its block is settled, so no single pass over the floor fills it.

A second example, the same floor with one bed left:

beds = ["69738145.", "831254976", "245967183",
        "183542697", "769813245", "524679318",
        "452796831", "976138524", "318425769"]
  ->  the last bed takes 2, and the search never backtracks

Constraints.

  • beds is always 9 strings of 9 characters, each 1–9 or ..
  • The planted beds never break the rule, and exactly one completion exists.

Hints

Hint 1

Testing whether crop c fits bed (r, k) by scanning the row, the column and the block costs 27 reads, and you will run that test millions of times. What would make it one lookup?

Hint 2

Every bed sits in exactly one row, one column and one block, and its block index is (r // 3) * 3 + k // 3.

Hint 3

A placement writes to four places. Undoing it has to write to all four, or the search rejects legal crops later and reports that the plan has no completion.

Approach

Brute force

Fill the empty beds with every combination of crops and check the floor at the end: 9⁵¹ ≈ 4 × 10⁴⁸ floors for the example. Checking as you go rather than at the end is the whole difference between impossible and instant.

The insight

A crop is legal in a bed exactly when it is missing from that bed's row set, column set and block set — so keep those 27 sets live, and legality costs three membership tests instead of 27 reads.

The sets restate the rule exactly rather than approximating it: a floor is valid if and only if no placement ever collided with them. Each placement touches one set per family, so adding and removing it is O(1), which is what lets a branch be abandoned cheaply. The rest is the standard frame — choose a bed, try each legal crop, recurse, undo — with the return value carrying "this branch finished" upward.

Algorithm

  1. Convert the strings to a grid of integers and collect the empty beds in a list.
  2. Build row[9], col[9], block[9] as sets from the planted beds.
  3. fill(i): if i is past the last empty bed, return true.
  4. Take bed (r, k), whose block is (r // 3) * 3 + k // 3.
  5. For each crop absent from all three sets: write it to the grid and the three sets, and return true if fill(i + 1) does; otherwise erase it from all four.
  6. If no crop fits, return false — this bed cannot be planted from here.

Complexity

Time O(9^b) worst case, where b is the number of empty beds; the sets cut the real tree to a few thousand nodes on a plan this size. Space O(b) for the recursion depth, plus 27 sets holding 81 entries between them.

Solution

Python 3 · standard library57 lines · 4 test cases, all passing
"""Greenhouse rotation — backtracking with live row, column and block sets."""


def block_of(row, col):
    """The 3x3 block index of a bed, 0-8 reading left to right, top to bottom."""
    return (row // 3) * 3 + col // 3


def solve(beds):
    floor = [[0 if ch == "." else int(ch) for ch in row] for row in beds]
    row_used = [set() for _ in range(9)]
    col_used = [set() for _ in range(9)]
    block_used = [set() for _ in range(9)]
    empty = []

    for r in range(9):
        for c in range(9):
            crop = floor[r][c]
            if crop:
                row_used[r].add(crop)
                col_used[c].add(crop)
                block_used[block_of(r, c)].add(crop)
            else:
                empty.append((r, c))

    def fill(i):
        # invariant: the beds before empty[i] are planted and legal, and the three
        # set families name exactly the crops written into the floor so far.
        if i == len(empty):
            return True
        r, c = empty[i]
        b = block_of(r, c)
        for crop in range(1, 10):
            if crop in row_used[r] or crop in col_used[c] or crop in block_used[b]:
                continue
            floor[r][c] = crop
            row_used[r].add(crop)
            col_used[c].add(crop)
            block_used[b].add(crop)
            if fill(i + 1):
                return True
            # undo all four writes, or a later branch is denied a legal crop
            floor[r][c] = 0
            row_used[r].discard(crop)
            col_used[c].discard(crop)
            block_used[b].discard(crop)
        return False

    fill(0)
    return ["".join(str(crop) for crop in row) for row in floor]


SOLVED = [
    "697381452", "831254976", "245967183",
    "183542697", "769813245", "524679318",
    "452796831", "976138524", "318425769",
]
The cases that ran
TESTS = [
    (([".....14..",
       "831..49..",
       "..596.1..",
       "...5..6.7",
       "7........",
       ".2.6....8",
       "...7.68.1",
       "97..3..2.",
       "3.8...7.9"],), SOLVED),
    ((["69738145.", "831254976", "245967183",
       "183542697", "769813245", "524679318",
       "452796831", "976138524", "318425769"],), SOLVED),
    ((SOLVED,), SOLVED),
    (([".35....6.",
       "......5..",
       ".7...198.",
       "..3..8.4.",
       "82.7..3.1",
       ".67.35...",
       ".8.6.4.3.",
       "....138..",
       ".5..2...4"],),
     ["135982467", "298467513", "674351982",
      "513298746", "829746351", "467135298",
      "982674135", "746513829", "351829674"]),
]

Pitfalls

  • Undoing the grid but not the sets. The crop stays marked as used in its row, so a later branch that needs it is refused and the solver reports no completion on a plan that has one.
  • Ignoring the recursive call's return value. Calling fill(i + 1) and then carrying on to the next crop makes the first dead end unwind every placement, and you hand back a floor still full of ..
  • Computing the block as r // 3 + k // 3. That index collides — (0,3) and (3,0) both give 1 — so two blocks share a set and legal crops get rejected.

Variants

  • Gallery sweep — the same place-and-undo bookkeeping on a smaller board, counting layouts rather than finding one.
  • Drill roster — the same frame, where the branch dies on length rather than on a conflict.