Description
Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy: Each row, column, and 3x3 box contains digits 1-9 without repetition. Empty cells are indicated by '.'.
Examples
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]Solved board with all cells filledFill in the dots to complete the valid sudoku.
board = [[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","1"],[".",".",".","4","1","1",".",".","9"]]No solution existsThis Sudoku puzzle has no valid solution because there are two 1's in the bottom row (positions 4 and 5), which violates the rule that each row must contain digits 1-9 without repetition. This example demonstrates how the solver should handle invalid puzzles.
board = [["1","2","3","4","5","6","7","8","."],["4","5","6","7","8","9","1","2","."],["7","8","9","1","2","3","4","5","."],["2","3","4","5","6","7","8","9","."],["5","6","7","8","9","1","2","3","."],["8","9","1","2","3","4","5","6","."],["3","4","5","6","7","8","9","1","."],["6","7","8","9","1","2","3","4","."],["9","1","2","3","4","5","6","7","."]][["1","2","3","4","5","6","7","8","9"],["4","5","6","7","8","9","1","2","3"],["7","8","9","1","2","3","4","5","6"],["2","3","4","5","6","7","8","9","1"],["5","6","7","8","9","1","2","3","4"],["8","9","1","2","3","4","5","6","7"],["3","4","5","6","7","8","9","1","2"],["6","7","8","9","1","2","3","4","5"],["9","1","2","3","4","5","6","7","8"]]This puzzle has only the last column empty (9 cells), making it easier to solve since most constraints are already satisfied. Each row and column already contains 8 out of 9 digits, so the solver only needs to find the missing digit for each position. This tests the solver's efficiency with minimal empty cells.
Constraints
- •
board.length == 9 - •
board[i].length == 9 - •
board[i][j] is a digit or '.'