Sudoku Solver
Explore how to solve a 9x9 Sudoku puzzle using backtracking. Understand the rules for rows, columns, and 3x3 sub-box constraints. This lesson guides you through implementing a solution that fills empty cells while maintaining validity, helping you grasp backtracking approaches for complex constraint problems.
We'll cover the following...
Statement
Given a 9 x 9 sudoku board, solve the puzzle by completing the empty cells. The sudoku board is only considered valid if the following rules are satisfied:
Each row must contain digits between 1 and 9, and there should be no repetition of digits within a row.
Each column must contain digits between 1 and 9, and there should be no repetition of digits within a column.
The board consists of 9 non-overlapping sub-boxes, each containing 3 rows and 3 columns. Each of these 3 x 3 sub-boxes must contain digits between 1 and 9, and there should be no repetition of digits within a sub-box.
Constraints:
board.lengthboard[i].lengthboard[i][j]is a digit or..The input board is guaranteed to have one solution.
Example
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Sudoku Solver
Is the 9 x 9 sudoku board given below valid?
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3
3 1 2 8 4 5 9 6 7
6 9 7 3 1 2 8 4 5
8 4 5 6 9 7 3 1 2
2 3 1 5 7 4 6 9 8
9 6 8 2 3 1 5 7 4
5 7 4 9 6 8 2 3 1
Yes
No
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Note: As an additional challenge, we have intentionally hidden the solution to this puzzle.
Try it yourself
Implement your solution in the following coding playground.
We have left the solution to this challenge as an exercise for you. An optimal solution to this problem runs in O(9(n*m)) time and takes O(n*m) space. You may try to translate the logic of the solved puzzle into a coded solution.
class Solution {public static char[][] solveSudoku(char[][] board) {// Replace this placeholder return statement with your codereturn board;}}