[Solved] Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.

Question

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  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-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Machine Learning Projects
Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Machine Learning Projects

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

Python Solution

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        for i in range(9):
            for j in range(9):
                if board[i][j]!='.':
                    board[i][j] = int(board[i][j])
                else:
                    board[i][j] = 0
                    
        def return_empty(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j]==0:
                        return(i,j)
            return None
        
        def check(board,num,pos):
            row,col = pos
        
            # checking row
            for i in range(9):
                if board[row][i]==num and i!=col:
                    return False
        
            # checking col
            for i in range(9):
                if board[i][col]==num and i!=row:
                    return False
        
            # checking for sub-grid
            box_x = row//3
            box_y = col//3
        
            for i in range(box_x*3,box_x*3+3):
                for j in range(box_y*3,box_y*3+3):
                    if board[i][j]==num and (i,j)!=pos:
                        return False
            return True
        
        def solve(board):
            vacant = return_empty(board)
            if vacant is None:return True #means all cella are filled now and we have completed the sudoku
            row,col = vacant
            for i in range(1,10):
                if check(board,i,vacant):
                    board[row][col] = i
                    if solve(board):
                        return True
                    board[row][col] = 0
            return False
        
        solve(board)

        for i in range(9):
            l = ''
            for j in range(9):
                l+=str(board[i][j])
            board[i] = l
        
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 517

Leave a Reply

Your email address will not be published. Required fields are marked *