Sudoku Solver - Hard Problem
Explore how to solve a Sudoku puzzle using recursion and backtracking by safely placing digits in each empty cell to satisfy row, column, and 3x3 subgrid constraints. Understand step-by-step checking and recursive assignment to find the solution or determine if none exists.
We'll cover the following...
Problem statement
Given a partially filled (9 × 9) 2-D array grid[9][9], the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.
Let’s look at an example to understand the input and output format.
The 0 in the input matrix denotes the empty space in the Sudoku.
Solution: Backtracking approach
Like all other Backtracking problems, Sudoku can be solved by assigning numbers one by one to empty cells. Before assigning a number:
- Check whether it is safe to assign.
- Check that the same number is not present in the current row, current column, or in the current
3 X 3sub-grid.