SourceBae Blogs

#### Write a Python Program to Solve a Sudoku Puzzle by Filling The Empty Cells

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.

Each of the digits 1-9 must occur exactly once in each column.

Each of the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid. The ‘.’ character indicates empty cells.

## Python Program to Solve a Sudoku Puzzle

```Input: 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"]]
```

Output: [[“5″,”3″,”4″,”6″,”7″,”8″,”9″,”1″,”2”],[“6″,”7″,”2″,”1″,”9″,”5″,”3″,”4″,”8”],[“1″,”9″,”8″,”3″,”4″,”2″,”5″,”6″,”7”],[“8″,”5″,”9″,”7″,”6″,”1″,”4″,”2″,”3”],[“4″,”2″,”6″,”8″,”5″,”3″,”7″,”9″,”1”],[“7″,”1″,”3″,”9″,”2″,”4″,”8″,”5″,”6”],[“9″,”6″,”1″,”5″,”3″,”7″,”2″,”8″,”4”],[“2″,”8″,”7″,”4″,”1″,”9″,”6″,”3″,”5”],[“3″,”4″,”5″,”2″,”8″,”6″,”1″,”7″,”9”]]

Explanation: The input board is shown above and the only valid solution is shown below: Constraints:

board.length == 9

board[i].length == 9

board[i][j] is a digit or ‘.’.

It is guaranteed that the input board has only one solution.

Sure, here’s a Python program that solves a Sudoku puzzle by filling the empty cells using a backtracking algorithm:

```def solve_sudoku(board): def is_valid(x, y, num): for i in range(9): if board[x][i] == num or board[i][y] == num: return False for i in range(3): for j in range(3): if board[(x // 3) * 3 + i][(y // 3) * 3 + j] == num: return False return True def dfs(): for i in range(9): for j in range(9): if board[i][j] == '.': for num in '123456789': if is_valid(i, j, num): board[i][j] = num if dfs(): return True board[i][j] = '.' return False return True dfs() return board # Example usage 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"]] print(solve_sudoku(board))
```

# Output: [[“5″,”3″,”4″,”6″,”7″,”8″,”9″,”1″,”2”], # [“6″,”7″,”2″,”1″,”9″,”5″,”3″,”4″,”8”], # [“1″,”9″,”8″,”3″,”4″,”2″,”5″,”6″,”7”], # [“8″,”5″,”9″,”7″,”6″,”1″,”4″,”2″,”3”], # [“4″,”2″,”6″,”8″,”5″,”3″,”7″,”9″,”1”], # [“7″,”1″,”3″,”9″,”2″,”4″,”8″,”5″,”6”], # [“9″,”6″,”1″,”5″,”3″,”7″,”2″,”8″,”4”], # [“2″,”8″,”7″,”4″,”1″,”9″,”6″,”3″,”5”], # [“3″,”4″,”5″,”2″,”8″,”6″,”1″,”7″,”9”]]

This program uses a backtracking algorithm to fill in the empty cells of the Sudoku puzzle. The dfs function starts by iterating through each cell of the puzzle, and if a cell is empty, it tries to fill it with a number from 1 to 9.

Before filling a cell, the program checks whether the move is valid by calling the is_valid function which checks the current row, column and 3×3 sub-box whether the number already exists or not. If the move is valid, the program fills the cell and continues to the next empty cell.

If the move is not valid or if the function reaches a point where there are no more empty cells, the function backtracks to the previous cell and tries the next number. Once the function has successfully filled all the cells, it returns True and the puzzle is solved. The program then returns the completed board as the output.

It’s important to note that the input board must be a 2D list of strings, where each string is either a digit from 1 to 9 or a ‘.’ character, representing an empty cell. The constraints mentioned in the problem statement are also checked and satisfied in this program.

Please let me know if you have any questions or if there’s anything else I can help with.