Create a function that checks after assigning the current index the grid becomes unsafe or not.And if none of the number (1 to 9) leads to a solution, return false and print no solution exists. If the assignment doesn’t lead to a solution, then try the next number for the current empty cell. After checking for safety, assign the number, and recursively check whether this assignment leads to a solution or not. Check that the same number is not present in the current row, current column and current 3X3 subgrid. Before assigning a number, check whether it is safe to assign. Like all other Backtracking problems, Sudoku can be solved by one by one assigning numbers to empty cells. To store the output array a matrix is needed. i, j+1įor every unassigned index, there are 9 possible options so the time complexity is O(9^(n*n)).
if the current index is assigned then call the recursive function with index of next element, i.e.if the recursive call returns true then break the loop and return true. if the current index is not assigned then fill the element from 1 to 9 and recur for all 9 cases with the index of next element, i.e.The other base case is when the value of column is N, i.e j = N, then move to next row, i.e. i=N-1 and j=N then check if the grid is safe or not, if safe print the grid and return true else return false. If the index is at the end of the matrix, i.e. Create a recursive function that takes a grid and the current row and column index.If any number has a frequency greater than 1 in the hashMap return false else return true Keep Hashmap for the row, column and boxes.