Sudoku Solver

Hard

You are given a Sudoku puzzle represented as an array of 9 strings. Each string corresponds to a row on the 9x9 Sudoku board. Empty cells, which need to be filled, are indicated by the character '.'.

Your task is to write a program that solves this Sudoku puzzle by filling in all the empty cells. To successfully solve the puzzle, you must ensure that the following classic Sudoku rules are met for the final grid:

Remember that a Sudoku board is valid if:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Do not return anything, instead modify the input board.

Input

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

Output

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

Explanation:

The initial board is solved by filling in the empty cells according to Sudoku rules. The board is modified in-place.

Input

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

Output

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

Hello! I am your ✨ AI assistant. I can provide you hints, explanations, give feedback on your code, and more. Just ask me anything related to the problem you're working on!

Example 1