Last Updated: 10 Sep, 2020
Sudoku Solver
Hard
Asked in companies
You have been given a 9x9 2d integer matrix 'MAT' representing a Sudoku puzzle. The empty cells of the Sudoku are filled with zeros, and the rest of the cells are filled with integers from 1 to 9. Your task is to fill all the empty cells such that the final matrix represents a Sudoku solution.
Note:
A Sudoku solution must satisfy all the following conditions-
1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9, 3x3 sub-grids of the grid.
You can also assume that there will be only one sudoku solution for the given matrix.
Input Format:
The input consists of 9 lines. Each line contains 9 single space-separated integers representing a row of the matrix. An empty cell is represented by 0.
Constraints :
Size of MAT is 9x9
0 <= MAT[i][j] <= 9
where an empty cell is given by 0 in the matrix.
Output Format :
The output is consists of 9 lines. Each line contains 9 single space-separated integers where the empty cells from the input matrix are replaced by some integers.
Note
You are not required to print anything, and it has already been taken care of. Just implement the function.
Approaches
The naive or brute force approach will be to try every possible configuration of numbers from 1 to 9 for each of the empty cells. After filling all the empty cells in the matrix, we check that the matrix is a valid sudoku solution or not. If we don’t find it valid, we keep checking it for the next configurations recursively until we find one.
Backtracking is a general algorithm for finding all (or some) solutions to a problem that incrementally builds candidates to the solution. As soon as it determines that a candidate can not possibly be the solution to the problem, it abandons it (“backtracks”). We can solve this problem using backtracking.
- Before we assign a number in an empty cell, we will check whether it is safe to assign. We will have an ‘isSafe’ function for it, which will check that the same number is not present in the current row, current column, and in the current sub-grid.
- If it is safe to assign the number, we will assign it to the empty cell and recursively check whether this assignment leads to a solution or not.
- If this assignment doesn’t lead to a solution, then we will try the next number for the current empty cell. And if none of the numbers from 1 to 9 leads to a solution, we will return false.