




import os




def  SCREAMING_SNAKE_CASE     (	__UpperCamelCase      :						Tuple				)  ->							int:
    UpperCAmelCase_										=					len(grid[0]				)
    UpperCAmelCase_										=					len(__UpperCamelCase				)

    UpperCAmelCase_										=					0
    UpperCAmelCase_										=					0
    UpperCAmelCase_										=					0

    # Check vertically, horizontally, diagonally at the same time (only works
    # for nxn grid)
    for i in range(__UpperCamelCase				):
        for j in range(n_rows - 3				):
            UpperCAmelCase_										=					grid[j][i] * grid[j + 1][i] * grid[j + 2][i] * grid[j + 3][i]
            UpperCAmelCase_										=					grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3]

            # Left-to-right diagonal (\) product
            if i < n_columns - 3:
                UpperCAmelCase_										=					(
                    grid[i][j]
                    * grid[i + 1][j + 1]
                    * grid[i + 2][j + 2]
                    * grid[i + 3][j + 3]
                )

            # Right-to-left diagonal(/) product
            if i > 2:
                UpperCAmelCase_										=					(
                    grid[i][j]
                    * grid[i - 1][j + 1]
                    * grid[i - 2][j + 2]
                    * grid[i - 3][j + 3]
                )

            UpperCAmelCase_										=					max(
                __UpperCamelCase	,					__UpperCamelCase	,					__UpperCamelCase	,					__UpperCamelCase				)
            if max_product > largest:
                UpperCAmelCase_										=					max_product

    return largest




def  SCREAMING_SNAKE_CASE     (	)  ->							Optional[Any]:
    UpperCAmelCase_										=					[]
    with open(os.path.dirname(__UpperCamelCase				) + '''/grid.txt'''				) as file:
        for line in file:
            grid.append(line.strip('''\n'''				).split(''' '''				)				)

    UpperCAmelCase_										=					[[int(__UpperCamelCase				) for i in grid[j]] for j in range(len(__UpperCamelCase				)				)]

    return largest_product(__UpperCamelCase				)


if __name__ == "__main__":
 print(solution())











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.')





