Sudoku Solver

You can create a recursive function to solve the Sudoku puzzle, filling the empty cells according to the rules. Here’s the code for that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def is_valid(board, row, col, num):
            # Check if the number is in the current row
            for r in range(9):
                if board[r][col] == num:
                    return False
            # Check if the number is in the current column
            for c in range(9):
                if board[row][c] == num:
                    return False
            # Check if the number is in the current 3x3 grid
            row_start, col_start = 3 * (row // 3), 3 * (col // 3)
            for r in range(row_start, row_start + 3):
                for c in range(col_start, col_start + 3):
                    if board[r][c] == num:
                        return False
            return True

        def solve(board):
            for r in range(9):
                for c in range(9):
                    if board[r][c] == '.':
                        for num in '123456789':
                            if is_valid(board, r, c, num):
                                board[r][c] = num
                                if solve(board):
                                    return True
                                board[r][c] = '.' # Backtrack if the solution is not found
                        return False # No solution found for this path
            return True # Entire board is filled
        
        solve(board)

The function is_valid checks whether a number can be placed in a specific cell based on the rules of Sudoku. The recursive function solve attempts to place a number in an empty cell and then recurses to solve the rest of the board. If a solution is found, the board is updated in place. If the current path doesn’t lead to a solution, the function backtracks by setting the cell back to ‘.’ and continues searching.

10 Prerequisite LeetCode Problems

“Sudoku Solver” involves the use of backtracking algorithm to fill a partially filled sudoku. Here are 10 problems for a better understanding:

1. “Valid Sudoku” (LeetCode Problem #36): This problem requires you to check whether a partially filled Sudoku is valid according to the Sudoku rules or not.

2. “Subsets” (LeetCode Problem #78): This problem introduces you to the concept of generating all possible subsets of a given set using backtracking.

3. “Combination Sum” (LeetCode Problem #39): Here, you’ll be using backtracking to find all unique combinations that sum up to a target.

4. “Permutations” (LeetCode Problem #46): This problem is about finding all possible permutations of a given list of numbers, which requires using a backtracking approach.

5. “Word Search” (LeetCode Problem #79): This is a good problem to apply backtracking in a 2D grid which is similar to a Sudoku grid.

6. “Generate Parentheses” (LeetCode Problem #22): This problem uses backtracking to create all possible combinations of well-formed parentheses.

7. “Palindrome Partitioning” (LeetCode Problem #131): This problem involves backtracking and also introduces the concept of palindromes.

8. “Restore IP Addresses” (LeetCode Problem #93): This problem requires you to generate all possible valid IP addresses from given string, involving concepts of both string manipulation and backtracking.

9. “Letter Combinations of a Phone Number” (LeetCode Problem #17): This problem, like many others in this list, requires backtracking to generate all possible letter combinations that the number could represent.

10. “Binary Watch” (LeetCode Problem #401): This problem helps in understanding combinations and backtracking in a simpler context.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        n = 9

        def isValid(row, col, ch):
            row, col = int(row), int(col)

            for i in range(9):

                if board[i][col] == ch:
                    return False
                if board[row][i] == ch:
                    return False

                if board[3*(row//3) + i//3][3*(col//3) + i%3] == ch:
                    return False

            return True

        def solve(row, col):
            if row == n:
                return True
            if col == n:
                return solve(row+1, 0)

            if board[row][col] == ".":
                for i in range(1, 10):
                    if isValid(row, col, str(i)):
                        board[row][col] = str(i)

                        if solve(row, col + 1):
                            return True
                        else:
                            board[row][col] = "."
                return False
            else:
                return solve(row, col + 1)

        solve(0, 0)

Problem Classification

This problem involves filling up a partially filled grid with numbers such that no number is repeated in any row, column or 3x3 subgrid. It’s a popular puzzle that requires a strategy of backtracking, which involves placing numbers and reverting if it doesn’t lead to a valid solution. Thus, it’s categorized under Number Placement Puzzle.

This problem involves filling up a partially filled grid with numbers ensuring no number repeats in any row, column, or 3x3 subgrid. It’s like solving a popular puzzle where you sometimes need to go back on your steps if they don’t lead to a solution. This is classified as Puzzle Solving / Backtracking.

Category: Puzzle Solving / Backtracking.

Language Agnostic Coding Drills

This code is solving the Sudoku problem using a recursive, backtracking approach.

1. Understanding Multi-dimensional Lists: The code uses a 2-dimensional list to represent the Sudoku board.

2. Understanding Conditional Statements: The code uses conditional statements to perform actions based on specific conditions.

3. Understanding Loop Constructs: The code uses nested loops to iterate over the Sudoku board and check various conditions.

4. Understanding Functions: The code uses two main functions, isValid and solve, which are recursively called.

5. Understanding Recursion: The main engine of this code is the recursive function solve, which uses backtracking to solve the Sudoku problem.

6. Understanding Backtracking: This is a specific type of recursion where you try out solutions and if they don’t lead to a valid answer, you undo the previous step (or “backtrack”) and try a different path.

Here’s how you can arrange the drills in order of increasing difficulty:

1. Manipulating and working with multi-dimensional lists.
2. Understanding and using conditional statements.
3. Writing loops and nested loops.
4. Writing and using functions.
5. Writing recursive functions.
6. Implementing backtracking.

The problem-solving approach for this Sudoku solver works like this:

1. Start from the top left cell of the Sudoku board.
2. If the cell is empty, try to fill it with a number from 1 to 9. But before placing a number, check if it’s valid to place that number in the current cell.
3. A number is valid if the same number doesn’t exist in the current row, column, and the 3x3 grid the cell belongs to.
4. If placing the number is valid, place it and move to the next cell.
5. If placing the number is not valid or if the next cells don’t lead to a solution, remove the number from the current cell and try the next number.
6. If none of the numbers can be placed in the current cell, return to the previous cell (backtrack) and try the next number in that cell.
7. If all cells are filled and no conflict occurs, it means the Sudoku is solved.

Targeted Drills in Python

1. Manipulating and working with multi-dimensional lists:

   Drill: Create a 2-dimensional list (matrix), then write a function that prints each row on a separate line.

   1 2 3 4 5 6

   def print_matrix(matrix): for row in matrix: print(row) matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] print_matrix(matrix)

2. Understanding and using conditional statements:

   Drill: Write a function that takes an integer as input and prints whether the number is positive, negative or zero.

   1 2 3 4 5 6 7 8 9 10 11

   def check_number(n): if n > 0: print("Positive") elif n < 0: print("Negative") else: print("Zero") check_number(5) check_number(-3) check_number(0)

3. Writing loops and nested loops:

   Drill: Write a function that prints a square pattern with the character ‘*’. The size of the square is determined by the input parameter.

   1 2 3 4 5 6 7

   def print_square(n): for i in range(n): for j in range(n): print('*', end = '') print() print_square(4)

4. Writing and using functions:

   Drill: Write a function that takes two numbers as parameters and returns their sum.

   1 2 3 4

   def add(a, b): return a + b print(add(3, 4))

5. Writing recursive functions:

   Drill: Write a recursive function that calculates the factorial of a number.

   1 2 3 4 5 6 7

   def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n-1) print(factorial(5))

6. Implementing backtracking:

   Drill: Write a Python function that solves the N-queens problem using backtracking. The N-queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

   This drill is considerably more complex than the previous ones and requires a good understanding of backtracking.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

   def solve_n_queens(n): def is_safe(board, row, col): for i in range(col): if board[row][i] == 1: return False for i, j in zip(range(row, -1, -1), range(col, -1, -1)): if board[i][j] == 1: return False for i, j in zip(range(row, n, 1), range(col, -1, -1)): if board[i][j] == 1: return False return True def solve(board, col): if col >= n: return True for i in range(n): if is_safe(board, i, col): board[i][col] = 1 if solve(board, col + 1): return True board[i][col] = 0 return False board = [[0]*n for _ in range(n)] if solve(board, 0): return board else: return None print(solve_n_queens(4))

Remember to always practice with simpler problems and progressively increase the complexity as you get comfortable with the concepts.