





'''simple docstring'''

from __future__ import annotations

__lowerCamelCase : int											=			list[list[int]]

# assigning initial values to the grid
__lowerCamelCase : Any											=			[
    [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 : int											=			[
    [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 							UpperCAmelCase_    (	lowerCAmelCase_		,							lowerCAmelCase_		,							lowerCAmelCase_		,							lowerCAmelCase_							):

    """simple docstring"""






    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 							UpperCAmelCase_    (	lowerCAmelCase_							):

    """simple docstring"""






    for i in range(9							):
        for j in range(9							):
            if grid[i][j] == 0:
                return i, j
    return None







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

    """simple docstring"""






    if location := find_empty_location(lowerCAmelCase__							):
        lowercase   ,							lowercase         = location
    else:
        # If the location is ``None``, then the grid is solved.
        return grid

    for digit in range(1		,							10							):
        if is_safe(lowerCAmelCase__		,							lowerCAmelCase__		,							lowerCAmelCase__		,							lowerCAmelCase__							):
            lowercase         = digit

            if sudoku(lowerCAmelCase__							) is not None:
                return grid

            lowercase         = 0

    return None







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

    """simple docstring"""






    for row in grid:
        for cell in row:
            print(lowerCAmelCase__		,							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 : int											=			sudoku(example_grid)
      if solution is not None:
         print_solution(solution)
      else:
         print("Cannot find a solution.")











'''simple docstring'''

from __future__ import annotations

class       UpperCAmelCase :




		def __init__(self      :	Dict							,			A__      :	str							,			A__      :	str				)					-> str:
						lowercase   ,							lowercase         = text, pattern
						lowercase   ,							lowercase         = len(A__				), len(A__				)




		def 				UpperCAmelCase__   (self      :	Any							,			A__      :	str				)					-> int:

						for i in range(self.patLen - 1							,			-1							,			-1				):
										if char == self.pattern[i]:
														return i
						return -1




		def 				UpperCAmelCase__   (self      :	List[Any]							,			A__      :	int				)					-> int:

						for i in range(self.patLen - 1							,			-1							,			-1				):
										if self.pattern[i] != self.text[current_pos + i]:
														return current_pos + i
						return -1





		def 				UpperCAmelCase__   (self      :	Optional[Any]				)					-> list[int]:
						# searches pattern in text and returns index positions
						lowercase         = []
						for i in range(self.textLen - self.patLen + 1				):
										lowercase         = self.mismatch_in_text(A__				)
										if mismatch_index == -1:
														positions.append(A__				)
										else:
														lowercase         = self.match_in_pattern(self.text[mismatch_index]				)
														lowercase         = (
														    mismatch_index - match_index
														)  # shifting index lgtm [py/multiple-definition]
						return positions




__lowerCamelCase : List[str]											=			"ABAABA"
__lowerCamelCase : List[str]											=			"AB"
__lowerCamelCase : Union[str, Any]											=			BoyerMooreSearch(text, pattern)
__lowerCamelCase : List[str]											=			bms.bad_character_heuristic()

if len(positions) == 0:
			print("No match found")
else:
			print("Pattern found in following positions: ")
			print(positions)




