




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						str	,					__UpperCamelCase      :						str				)  ->							bool:
    UpperCAmelCase_										=					len(__UpperCamelCase				) + 1
    UpperCAmelCase_										=					len(__UpperCamelCase				) + 1

    # dp is a 2d matrix where dp[i][j] denotes whether prefix string of
    # length i of input_string matches with prefix string of length j of
    # given pattern.
    # "dp" stands for dynamic programming.
    UpperCAmelCase_										=					[[0 for i in range(__UpperCamelCase				)] for j in range(__UpperCamelCase				)]

    # since string of zero length match pattern of zero length
    UpperCAmelCase_										=					1

    # since pattern of zero length will never match with string of non-zero length
    for i in range(1	,					__UpperCamelCase				):
        UpperCAmelCase_										=					0

    # since string of zero length will match with pattern where there
    # is at least one * alternatively
    for j in range(1	,					__UpperCamelCase				):
        UpperCAmelCase_										=					dp[0][j - 2] if pattern[j - 1] == '''*''' else 0

    # now using bottom-up approach to find for all remaining lengths
    for i in range(1	,					__UpperCamelCase				):
        for j in range(1	,					__UpperCamelCase				):
            if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
                UpperCAmelCase_										=					dp[i - 1][j - 1]

            elif pattern[j - 1] == "*":
                if dp[i][j - 2] == 1:
                    UpperCAmelCase_										=					1
                elif pattern[j - 2] in (input_string[i - 1], "."):
                    UpperCAmelCase_										=					dp[i - 1][j]
                else:
                    UpperCAmelCase_										=					0
            else:
                UpperCAmelCase_										=					0

    return bool(dp[-1][-1]				)


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 # inputing the strings
 # input_string = input("input a string :")
 # pattern = input("input a pattern :")

 _lowerCamelCase      			=						'aab'
 _lowerCamelCase      			=						'c*a*b'

 # using function to check whether given string matches the given pattern
 if match_pattern(input_string, pattern):
  print(F"{input_string} matches the given pattern {pattern}")
 else:
  print(F"{input_string} does not match with the given pattern {pattern}")











from __future__ import annotations

_lowerCamelCase      			=						list[list[int]]

# assigning initial values to the grid
_lowerCamelCase      			=						[
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]

# a grid with no solution
_lowerCamelCase      			=						[
    [5, 0, 6, 5, 0, 8, 4, 0, 3],
    [5, 2, 0, 0, 0, 0, 0, 0, 2],
    [1, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						Matrix	,					__UpperCamelCase      :						int	,					__UpperCamelCase      :						int	,					__UpperCamelCase      :						int				)  ->							bool:
    for i in range(9				):
        if grid[row][i] == n or grid[i][column] == n:
            return False

    for i in range(3				):
        for j in range(3				):
            if grid[(row - row % 3) + i][(column - column % 3) + j] == n:
                return False

    return True




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						Matrix				)  ->							tuple[int, int] | None:
    for i in range(9				):
        for j in range(9				):
            if grid[i][j] == 0:
                return i, j
    return None




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						Matrix				)  ->							Matrix | None:
    if location := find_empty_location(__UpperCamelCase				):
        UpperCAmelCase_			,							UpperCAmelCase_										=					location
    else:
        # If the location is ``None``, then the grid is solved.
        return grid

    for digit in range(1	,					10				):
        if is_safe(__UpperCamelCase	,					__UpperCamelCase	,					__UpperCamelCase	,					__UpperCamelCase				):
            UpperCAmelCase_										=					digit

            if sudoku(__UpperCamelCase				) is not None:
                return grid

            UpperCAmelCase_										=					0

    return None




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						Matrix				)  ->							None:
    for row in grid:
        for cell in row:
            print(__UpperCamelCase	,					end=''' '''				)
        print()


if __name__ == "__main__":
 # make a copy of grid so that you can compare with the unmodified grid
 for example_grid in (initial_grid, no_solution):
  print('\nExample grid:\n' + '=' * 20)
  print_solution(example_grid)
  print('\nExample grid solution:')
  _lowerCamelCase      			=						sudoku(example_grid)
  if solution is not None:
   print_solution(solution)
  else:
   print('Cannot find a solution.')





