Show problems as
Classic problem #37HardArrayHash TableBacktrackingMatrixAlgorithm XDancing Links

Sudoku Solver

Real-world version: Complete the Planting Frame
Tracked in this browser only
Read Sudoku Solver on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstRecursive Search · Recursion, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fill_frame(frame: list[list[str]]) -> list[list[str]]:
Java
public void fillFrame(char[][] frame)

More on the same topics