We have to design a [Sudoku] solver. The problem statement defined what is Sudoku and how it is played. The given board is always a fixed size of 9x9. So, the input is always a fixed board. In that case, whatever we do with the solution (unless we are doing terribly complicated things), it will be a O(1) solution.
In spite of the time complexity is O(1), we need to think of the total time the solution might take. For example, if you do a blind brute force, the total search space for the 9x9 board is going to be (9x9)^9 = 150094635296999121 ~ 1.5x10^17. So a naive brute force solution will not be feasible.
There are some restrictions on putting a value in an index in the board. So, we do not need to put all values from 0 to 9 to check if we can solve. This is a perfect example for Backtracking algorithms where you have a number of of constraints to check and if following the constraints for a particular set of values end-up in a dead end, then go back and change some of the values to try the next space.
Wikipedia has an amazing animation to demonstrate how backtracking works with sudoku.
Step 2: Implement Board Validation Function
Before implementation of the solver itself, first we need to create a function that can be used to see if we can put a value on an index in the board. The function will take the board, a row, a col and finally a val to put into that index of the board.
1
defvalidate_board(self,board,row,col,val):
The function will first check if there is same value as val in the same row or column in the board. We can check this easily by looping through that row and column once at a time.
1
2
3
4
5
6
7
8
9
# Check if duplicate in rowforrow_itinrange(9):ifboard[row_it][col]==val:returnFalse# Check if duplicate in colforcol_itinrange(9):ifboard[row][col_it]==val:returnFalse
Then we will check if the same value as val also appears in the same 3x3 block. To do this, we will take the current block where row and col resides. Then we will iterate through the block and check accordingly.
1
2
3
4
5
6
7
# Check if block has duplicaterow_block=row-row%3col_block=col-col%3forrow_itinrange(3):forcol_itinrange(3):ifboard[row_block+row_it][col_block+col_it]==val:returnFalse
Finally if none of these return False, we are sure that val at row, col position is a valid move. So we will return true.
1
2
# None of them return false. So satisfiesreturnTrue
Step 3: Base Conditions of Recursing Backtracking
We will start from the first element in the board. We will putting valid values in places and move forward. To do this, we will continuously put values, then increment col.
While incrementing col, we will reach at a point when col will be greater than 8 (out of the board). At that time, we reset col to zero and increment row. Finally row will go out of the board, so at that time, we will be sure that the board is solved.
1
2
3
4
5
6
ifrow==9:# If all rows are complete, we have solved it!returnTrueifcol==9:# This column is complete, go to next row's first colreturnself.recursiveSolve(board,row+1,0)
Also, if an index of the board is already filled by the problem, then we do not need to do anything at that index. So we will move forward.
1
2
3
ifboard[row][col]!='.':# This index is already filledreturnself.recursiveSolve(board,row,col+1)
Step 4: Implement Recursive Backtracking
For the backtracking, we will take numbers from 1 to 9 and fill each index of the board one by one. The problem gives us the board with characters in the indices. So we also need to put characters (or strings for python). For this, we will loop over the characters from ‘1’ to ‘9’.
Then we will see if we can put val in the index with the help of our previously implemented function validate_board.
1
ifself.validate_board(board,row,col,val):
If we can, we will put the value in the board and recursively go to the next index. And after continuously doing this, finally we will get an answer if puting val in this index results in a feasible board solution. If it is feasible, then we are done. If not, then we will have to backtrack. For backtracking we will again put a '.' in the index and continue with the next val.
1
2
3
4
5
6
7
# Put a correct valueboard[row][col]=val# Check if we can proceed to finishifself.recursiveSolve(board,row,col+1):returnTrue# Couldn't finish, so BackTrack!board[row][col]='.'
Finally there will be at least one state for which, recursiveSolve will return True. For that case, we are returning True. And for the rest of the case, we will return False.
1
2
# Dead end in this path. So return falsereturnFalse
Step 5: Start the Backtracking
We will start the backtracking process from row=0 and col=0. Even if there may be already a value in that index, our backtracking function will take care of it.
1
2
3
4
5
6
defsolveSudoku(self,board:[[str]])->None:"""
Modify board in-place
"""# Start solving from first indexself.recursiveSolve(board,0,0)
This is the most known algorithm for solving Sudoku. The time complexity as already mentioned is O(1). The space is only the board size. The problem expects you to change the board in place so this solution is perfect. If you could not change the board and return a new one, you can do a slight modification to this program like copying the board before the backtracking and returning the board after the process.
1
2
3
4
5
6
7
8
9
10
defsolveSudoku(self,board:[[str]])->[[str]]:"""
Modify board in-place
"""# Copy boardboard_copy=board.copy()# Start solving from first indexself.recursiveSolve(board_copy,0,0)# Return the copyreturnboard_copy
The complete solution of the problem is given by the following.
classSolution:defsolveSudoku(self,board:[[str]])->None:"""
Modify board in-place
"""# Start solving from first indexself.recursiveSolve(board,0,0)defvalidate_board(self,board,row,col,val):# Check if duplicate in rowforrow_itinrange(9):ifboard[row_it][col]==val:returnFalse# Check if duplicate in colforcol_itinrange(9):ifboard[row][col_it]==val:returnFalse# Check if block has duplicaterow_block=row-row%3col_block=col-col%3forrow_itinrange(3):forcol_itinrange(3):ifboard[row_block+row_it][col_block+col_it]==val:returnFalse# None of them return false. So satisfiesreturnTruedefrecursiveSolve(self,board,row,col):ifrow==9:# If all rows are complete, we have solved it!returnTrueifcol==9:# This column is complete, go to next row's first colreturnself.recursiveSolve(board,row+1,0)ifboard[row][col]!='.':# This index is already filledreturnself.recursiveSolve(board,row,col+1)# Try putting all values in 1-9forvalin'123456789':ifself.validate_board(board,row,col,val):# Put a correct valueboard[row][col]=val# Check if we can proceed to finishifself.recursiveSolve(board,row,col+1):returnTrue# Couldn't finish, so BackTrack!board[row][col]='.'# Dead end in this path. So return falsereturnFalse
classSolution{public:voidsolveSudoku(vector<vector<char>>&board){// Start solving from first index
recursiveSolve(board,0,0);}private:boolvalidateBoard(vector<vector<char>>&board,introw,intcol,intval){// Check if duplicate in row
for(introwI=0;rowI<board.size();rowI++)if(board[rowI][col]==val)returnfalse;// Check if duplicate in col
for(intcolI=0;colI<board.size();colI++)if(board[row][colI]==val)returnfalse;// Check if block has duplicate
introwBlock=row-row%3;intcolBlock=col-col%3;for(introwI=0;rowI<3;rowI++)for(intcolI=0;colI<3;colI++)if(board[rowBlock+rowI][colBlock+colI]==val)returnfalse;// None of them return false. So satisfies
returntrue;}boolrecursiveSolve(vector<vector<char>>&board,introw,intcol){// If all rows are complete, we have solve it!
if(row==9)returntrue;// This column is done, go to next row's first col
if(col==9)returnrecursiveSolve(board,row+1,0);// This index is already filled
if(board[row][col]!='.')returnrecursiveSolve(board,row,col+1);// Try putting all values in 1-9
for(charval='1';val<='9';val++){if(validateBoard(board,row,col,val)){// Put a correct value
board[row][col]=val;// Check if we can proceed to finish
if(recursiveSolve(board,row,col+1))returntrue;// Couldn't finish, so BackTrack!
board[row][col]='.';}}// Dead end in this path, So return false
returnfalse;}};
classSolution{publicvoidsolveSudoku(char[][]board){// Start solving from first indexrecursiveSolve(board,0,0);}privatebooleanvalidateBoard(char[][]board,introw,intcol,intval){// Check if duplicate in rowfor(introwI=0;rowI<board.length;rowI++)if(board[rowI][col]==val)returnfalse;// Check if duplicate in colfor(intcolI=0;colI<board.length;colI++)if(board[row][colI]==val)returnfalse;// Check if block has duplicateintrowBlock=row-row%3;intcolBlock=col-col%3;for(introwI=0;rowI<3;rowI++)for(intcolI=0;colI<3;colI++)if(board[rowBlock+rowI][colBlock+colI]==val)returnfalse;// None of them return false. So satisfiesreturntrue;}privatebooleanrecursiveSolve(char[][]board,introw,intcol){// If all rows are complete, we have solve it!if(row==9)returntrue;// This column is done, go to next row's first colif(col==9)returnrecursiveSolve(board,row+1,0);// This index is already filledif(board[row][col]!='.')returnrecursiveSolve(board,row,col+1);// Try putting all values in 1-9for(charval='1';val<='9';val++){if(validateBoard(board,row,col,val)){// Put a correct valueboard[row][col]=val;// Check if we can proceed to finishif(recursiveSolve(board,row,col+1))returntrue;// Couldn't finish, so BackTrack!board[row][col]='.';}}// Dead end in this path, So return falsereturnfalse;}}