






import itertools
import string
from collections.abc import Generator, Iterable






def   UpperCamelCase  (       snake_case__     :   Iterable[str]	,snake_case__     :   int  ):




     '''simple docstring'''






     __snake_case			:Dict          =						iter(snake_case__  )
     while True:
          __snake_case			:int          =						tuple(itertools.islice(snake_case__	,snake_case__  )  )
          if not chunk:
               return
          yield chunk






def   UpperCamelCase  (       snake_case__     :   str  ):




     '''simple docstring'''






     __snake_case			:str          =						"""""".join([c.upper() for c in dirty if c in string.ascii_letters]  )
     __snake_case			:List[Any]          =						""""""

     if len(snake_case__  ) < 2:
          return dirty

     for i in range(len(snake_case__  ) - 1  ):
          clean += dirty[i]

          if dirty[i] == dirty[i + 1]:
               clean += "X"

     clean += dirty[-1]

     if len(snake_case__  ) & 1:
          clean += "X"

     return clean






def   UpperCamelCase  (       snake_case__     :   str  ):




     '''simple docstring'''






     __snake_case			:str          =						"""ABCDEFGHIKLMNOPQRSTUVWXYZ"""
     # we're using a list instead of a '2d' array because it makes the math
     # for setting up the table and doing the actual encoding/decoding simpler
     __snake_case			:Any          =						[]

     # copy key chars into the table if they are in `alphabet` ignoring duplicates
     for char in key.upper():
          if char not in table and char in alphabet:
               table.append(snake_case__  )

    # fill the rest of the table in with the remaining alphabet chars
     for char in alphabet:
          if char not in table:
               table.append(snake_case__  )

     return table






def   UpperCamelCase  (       snake_case__     :   str	,snake_case__     :   str  ):




     '''simple docstring'''






     __snake_case			:List[Any]          =						generate_table(snake_case__  )
     __snake_case			:List[str]          =						prepare_input(snake_case__  )
     __snake_case			:int          =						""""""

     # https://en.wikipedia.org/wiki/Playfair_cipher#Description
     for chara, chara in chunker(snake_case__	,2  ):
          __snake_case       , __snake_case			:Optional[Any]          =						divmod(table.index(snake_case__  )	,5  )
          __snake_case       , __snake_case			:Any          =						divmod(table.index(snake_case__  )	,5  )

          if rowa == rowa:
               ciphertext += table[rowa * 5 + (cola + 1) % 5]
               ciphertext += table[rowa * 5 + (cola + 1) % 5]
          elif cola == cola:
               ciphertext += table[((rowa + 1) % 5) * 5 + cola]
               ciphertext += table[((rowa + 1) % 5) * 5 + cola]
          else:  # rectangle
               ciphertext += table[rowa * 5 + cola]
               ciphertext += table[rowa * 5 + cola]

     return ciphertext






def   UpperCamelCase  (       snake_case__     :   str	,snake_case__     :   str  ):




     '''simple docstring'''






     __snake_case			:Union[str, Any]          =						generate_table(snake_case__  )
     __snake_case			:Union[str, Any]          =						""""""

     # https://en.wikipedia.org/wiki/Playfair_cipher#Description
     for chara, chara in chunker(snake_case__	,2  ):
          __snake_case       , __snake_case			:str          =						divmod(table.index(snake_case__  )	,5  )
          __snake_case       , __snake_case			:List[str]          =						divmod(table.index(snake_case__  )	,5  )

          if rowa == rowa:
               plaintext += table[rowa * 5 + (cola - 1) % 5]
               plaintext += table[rowa * 5 + (cola - 1) % 5]
          elif cola == cola:
               plaintext += table[((rowa - 1) % 5) * 5 + cola]
               plaintext += table[((rowa - 1) % 5) * 5 + cola]
          else:  # rectangle
               plaintext += table[rowa * 5 + cola]
               plaintext += table[rowa * 5 + cola]

     return plaintext










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   UpperCamelCase  (       snake_case__     :   Matrix	,snake_case__     :   int	,snake_case__     :   int	,snake_case__     :   int  ):




     '''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  (       snake_case__     :   Matrix  ):




     '''simple docstring'''






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






def   UpperCamelCase  (       snake_case__     :   Matrix  ):




     '''simple docstring'''






     if location := find_empty_location(snake_case__  ):
          __snake_case       , __snake_case			:Optional[int]          =						location
     else:
          # If the location is ``None``, then the grid is solved.
          return grid

     for digit in range(1	,10  ):
          if is_safe(snake_case__	,snake_case__	,snake_case__	,snake_case__  ):
               __snake_case			:Union[str, Any]          =						digit

               if sudoku(snake_case__  ) is not None:
                    return grid

               __snake_case			:Tuple          =						0

     return None






def   UpperCamelCase  (       snake_case__     :   Matrix  ):




     '''simple docstring'''






     for row in grid:
          for cell in row:
               print(snake_case__	,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.""")


