0249HardArrayHash TableBacktrackingMatrixAlgorithm XDancing Links

Complete the Planting Frame

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A nursery plants seedlings into a 9-by-9 frame. Walkways split the frame after every third row and every third column, so it also reads as nine 3-by-3 plots. Nine varieties are on hand, labelled "1" through "9", and a completed frame carries each variety exactly once in every row, exactly once in every column, and exactly once in every 3-by-3 plot.

The frame arrives part planted as frame, a 9-by-9 grid of one-character strings: frame[r][c] is a variety label already planted there, or "." for a cell still bare.

Plant every bare cell in place, changing frame itself rather than building a second grid, and return that same grid so the finished layout can be read back. Labels the nursery already planted must stay where they are.

Exactly one completed frame extends the layout given, so the answer is unique.

Examples

Example 1

Input: frame = [[".", ".", ".", ".", ".", ".", ".", "6", "2"], [".", "2", "6", ".", "1", "8", "9", ".", "4"], [".", ".", "5", "2", ".", ".", "8", "1", "7"], ["5", ".", ".", ".", "2", "6", "1", ".", "."], ["1", ".", ".", ".", "4", ".", ".", ".", "9"], ["6", "9", ".", ".", ".", ".", ".", "4", "8"], [".", ".", ".", ".", ".", ".", ".", ".", "1"], [".", "6", "3", "1", "8", ".", "2", ".", "."], ["4", "1", ".", "5", "9", ".", ".", ".", "6"]]
Output: [["8", "7", "1", "4", "5", "9", "3", "6", "2"], ["3", "2", "6", "7", "1", "8", "9", "5", "4"], ["9", "4", "5", "2", "6", "3", "8", "1", "7"], ["5", "8", "4", "9", "2", "6", "1", "7", "3"], ["1", "3", "7", "8", "4", "5", "6", "2", "9"], ["6", "9", "2", "3", "7", "1", "5", "4", "8"], ["2", "5", "9", "6", "3", "7", "4", "8", "1"], ["7", "6", "3", "1", "8", "4", "2", "9", "5"], ["4", "1", "8", "5", "9", "2", "7", "3", "6"]]

Every row, every column and every 3-by-3 plot of the returned frame carries the nine labels once each, and each label the nursery had already planted is still in the cell it started in.

Example 2

Input: frame = [["5", "2", "8", "3", "1", "9", "4", "6", "7"], ["4", "6", "7", "2", "8", "5", "9", "3", "1"], ["9", "3", "1", "6", "7", "4", "5", "2", "8"], ["8", "9", "2", "4", ".", "1", "7", "5", "6"], ["1", "4", "3", "5", "6", "7", "8", "9", "2"], ["7", "5", "6", "9", "2", "8", "1", "4", "3"], ["3", "7", "4", "8", "5", "6", "2", "1", "9"], ["2", "1", "9", "7", "4", "3", "6", "8", "5"], ["6", "8", "5", "1", "9", "2", "3", "7", "4"]]
Output: [["5", "2", "8", "3", "1", "9", "4", "6", "7"], ["4", "6", "7", "2", "8", "5", "9", "3", "1"], ["9", "3", "1", "6", "7", "4", "5", "2", "8"], ["8", "9", "2", "4", "3", "1", "7", "5", "6"], ["1", "4", "3", "5", "6", "7", "8", "9", "2"], ["7", "5", "6", "9", "2", "8", "1", "4", "3"], ["3", "7", "4", "8", "5", "6", "2", "1", "9"], ["2", "1", "9", "7", "4", "3", "6", "8", "5"], ["6", "8", "5", "1", "9", "2", "3", "7", "4"]]

A single cell in row 4, column 5 was bare, and label "3" is the one label absent from that row, from that column and from that plot.

Example 3

Input: frame = [["6", "9", "7", "4", "8", "1", "5", "2", "3"], ["1", "4", "8", "2", "3", "5", "6", "9", "7"], ["5", "2", "3", "9", "7", "6", "1", "4", "8"], ["3", "5", "4", "6", "2", "7", "8", "1", "9"], ["7", "6", "2", "1", "9", "8", "3", "5", "4"], ["8", "1", "9", "5", "4", "3", "7", "6", "2"], ["4", "3", "1", "7", "5", "2", "9", "8", "6"], ["9", "8", "6", "3", "1", "4", "2", "7", "5"], ["2", "7", "5", "8", "6", "9", "4", "3", "1"]]
Output: [["6", "9", "7", "4", "8", "1", "5", "2", "3"], ["1", "4", "8", "2", "3", "5", "6", "9", "7"], ["5", "2", "3", "9", "7", "6", "1", "4", "8"], ["3", "5", "4", "6", "2", "7", "8", "1", "9"], ["7", "6", "2", "1", "9", "8", "3", "5", "4"], ["8", "1", "9", "5", "4", "3", "7", "6", "2"], ["4", "3", "1", "7", "5", "2", "9", "8", "6"], ["9", "8", "6", "3", "1", "4", "2", "7", "5"], ["2", "7", "5", "8", "6", "9", "4", "3", "1"]]

Nothing was left bare, so the frame is already complete and comes back exactly as it arrived.

Constraints

frame.length == 9
frame[i].length == 9
frame[i][j] is a one-character string: a label "1" through "9", or "."
The labels already planted break none of the three rules
Exactly one completed frame extends the layout given

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fill_frame(frame: list[list[str]]) -> list[list[str]]:

Java

public void fillFrame(char[][] frame)

The intended approach

Time O(9^b) branches in the worst case for b bare cells, each visited in O(1) because the masks answer candidacy without rescanning; the masks cut the real search far below that bound.Space O(b) for the recursion stack and the bare-cell list, on top of the grid, which is filled in place.

Read the planted labels once into three arrays of nine bitmasks, one per row, one per column and one per plot, and collect the bare cells. Then plant the bare cells in that fixed order: at each one, the union of its row, column and plot masks names every label already ruled out, so only the clear bits are tried. Setting a label flips three bits and writing into the grid; abandoning it flips the same three bits back and blanks the cell again.

Pythonentry point: fill_frame

def fill_frame(frame):
    rows = [0] * 9
    cols = [0] * 9
    plots = [0] * 9
    bare = []
    for r in range(9):
        for c in range(9):
            label = frame[r][c]
            if label == ".":
                bare.append((r, c))
            else:
                bit = 1 << (ord(label) - 49)
                rows[r] |= bit
                cols[c] |= bit
                plots[(r // 3) * 3 + c // 3] |= bit

    def plant(k):
        if k == len(bare):
            return True
        r, c = bare[k]
        p = (r // 3) * 3 + c // 3
        taken = rows[r] | cols[c] | plots[p]
        for d in range(9):
            bit = 1 << d
            if taken & bit:
                continue
            rows[r] |= bit
            cols[c] |= bit
            plots[p] |= bit
            frame[r][c] = chr(49 + d)
            if plant(k + 1):
                return True
            frame[r][c] = "."
            rows[r] ^= bit
            cols[c] ^= bit
            plots[p] ^= bit
        return False

    plant(0)
    return frame

The obvious version

Rescan for the first bare cell, then for each candidate label rescan its row, its column and its plot to see whether the label is free, recursing on success and clearing the cell on failure. O(b * 9 * 27) work per branch and no incremental state at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fill_frame(frame):
    def free(r, c, label):
        for i in range(9):
            if frame[r][i] == label:
                return False
            if frame[i][c] == label:
                return False
        top = (r // 3) * 3
        left = (c // 3) * 3
        for i in range(top, top + 3):
            for j in range(left, left + 3):
                if frame[i][j] == label:
                    return False
        return True

    def walk():
        for r in range(9):
            for c in range(9):
                if frame[r][c] == ".":
                    for label in "123456789":
                        if free(r, c, label):
                            frame[r][c] = label
                            if walk():
                                return True
                            frame[r][c] = "."
                    return False
        return True

    walk()
    return frame

How this problem was checked

Reference solution executed against 5 test cases — 5 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Complete the Planting Frame

Examples

Constraints

The signature

Create a free account to unlock the solution

More on the same topics