



from __future__ import annotations

_lowercase: Tuple      			=		list[list[int]]

# assigning initial values to the grid
_lowercase: Matrix      			=		[
    [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
_lowercase: Matrix      			=		[
    [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     a(      A       :    Matrix ,     A       :    int ,     A       :    int ,     A       :    int       )		->       bool:
					"""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     a(      A       :    Matrix       )		->       tuple[int, int] | None:
					"""simple docstring"""





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






def     a(      A       :    Matrix       )		->       Matrix | None:
					"""simple docstring"""





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

					for digit in range(1 ,     10       ):
										if is_safe(A ,     A ,     A ,     A       ):
															a					     =   digit

															if sudoku(A       ) is not None:
																				return grid

															a					     =   0

					return None






def     a(      A       :    Matrix       )		->       None:
					"""simple docstring"""





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





import unittest

from transformers.models.xlm_prophetnet.tokenization_xlm_prophetnet import SPIECE_UNDERLINE, XLMProphetNetTokenizer
from transformers.testing_utils import get_tests_dir, require_sentencepiece, slow
from transformers.utils import cached_property

from ...test_tokenization_common import TokenizerTesterMixin


_lowercase: Optional[int]      			=		get_tests_dir("fixtures/test_sentencepiece.model")



@require_sentencepiece
class 	_lowercase							(   lowerCAmelCase,      unittest.TestCase	):





	"""simple docstring"""
	__A							=							XLMProphetNetTokenizer
	__A							=							False
	__A							=							True




	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						super().setUp()

						# We have a SentencePiece fixture for testing
						a					     =   XLMProphetNetTokenizer(lowerCamelCase_		,       keep_accents=lowerCamelCase_		)
						tokenizer.save_pretrained(self.tmpdirname		)




	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						a					     =   "[PAD]"
						a					     =   0

						self.assertEqual(self.get_tokenizer()._convert_token_to_id(lowerCamelCase_		)		,       lowerCamelCase_		)
						self.assertEqual(self.get_tokenizer()._convert_id_to_token(lowerCamelCase_		)		,       lowerCamelCase_		)




	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						a					     =   list(self.get_tokenizer().get_vocab().keys()		)

						self.assertEqual(vocab_keys[0]		,       "[PAD]"		)
						self.assertEqual(vocab_keys[1]		,       "[CLS]"		)
						self.assertEqual(vocab_keys[-1]		,       "j"		)
						self.assertEqual(len(lowerCamelCase_		)		,       1012		)




	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						self.assertEqual(self.get_tokenizer().vocab_size		,       1012		)




	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						a					     =   XLMProphetNetTokenizer(lowerCamelCase_		,       keep_accents=lowerCamelCase_		)

						a					     =   tokenizer.tokenize("This is a test"		)
						self.assertListEqual(lowerCamelCase_		,       ["▁This", "▁is", "▁a", "▁t", "est"]		)

						self.assertListEqual(
						    tokenizer.convert_tokens_to_ids(lowerCamelCase_		)		,       [value + tokenizer.fairseq_offset for value in [285, 46, 10, 170, 382]]		,       )

						a					     =   tokenizer.tokenize("I was born in 92000, and this is falsé."		)
						self.assertListEqual(
						    lowerCamelCase_		,       [
						        SPIECE_UNDERLINE + "I",
						        SPIECE_UNDERLINE + "was",
						        SPIECE_UNDERLINE + "b",
						        "or",
						        "n",
						        SPIECE_UNDERLINE + "in",
						        SPIECE_UNDERLINE + "",
						        "9",
						        "2",
						        "0",
						        "0",
						        "0",
						        ",",
						        SPIECE_UNDERLINE + "and",
						        SPIECE_UNDERLINE + "this",
						        SPIECE_UNDERLINE + "is",
						        SPIECE_UNDERLINE + "f",
						        "al",
						        "s",
						        "é",
						        ".",
						    ]		,       )
						a					     =   tokenizer.convert_tokens_to_ids(lowerCamelCase_		)
						self.assertListEqual(
						    lowerCamelCase_		,       [
						        value + tokenizer.fairseq_offset
						        for value in [8, 21, 84, 55, 24, 19, 7, -9, 602, 347, 347, 347, 3, 12, 66, 46, 72, 80, 6, -9, 4]
						    ]		,       )

						a					     =   tokenizer.convert_ids_to_tokens(lowerCamelCase_		)
						self.assertListEqual(
						    lowerCamelCase_		,       [
						        SPIECE_UNDERLINE + "I",
						        SPIECE_UNDERLINE + "was",
						        SPIECE_UNDERLINE + "b",
						        "or",
						        "n",
						        SPIECE_UNDERLINE + "in",
						        SPIECE_UNDERLINE + "",
						        "[UNK]",
						        "2",
						        "0",
						        "0",
						        "0",
						        ",",
						        SPIECE_UNDERLINE + "and",
						        SPIECE_UNDERLINE + "this",
						        SPIECE_UNDERLINE + "is",
						        SPIECE_UNDERLINE + "f",
						        "al",
						        "s",
						        "[UNK]",
						        ".",
						    ]		,       )




	@cached_property
	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						return XLMProphetNetTokenizer.from_pretrained("microsoft/xprophetnet-large-wiki100-cased"		)




	@slow
	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						a					     =   "Hello World!"
						a					     =   [35389, 6672, 49, 2]
						self.assertListEqual(lowerCamelCase_		,       self.big_tokenizer.encode(lowerCamelCase_		)		)




	@slow
	def      UpperCamelCase_       (self		):
						"""simple docstring"""

						a					     =   {"input_ids": [[11073, 82783, 18, 26, 82783, 549, 51540, 248, 17209, 1301, 217, 20, 215186, 1325, 147, 17209, 1301, 217, 20, 56370, 53, 122020, 20, 16477, 27, 87355, 4548, 20, 4728, 78392, 17, 159969, 18, 26, 24491, 629, 15, 538, 22704, 5439, 15, 2788, 24491, 9885, 15, 43534, 605, 15, 814, 18403, 33200, 29, 15, 43534, 24458, 12410, 111, 24966, 83669, 9637, 144068, 26, 850, 22346, 27, 147, 24966, 83669, 83490, 26, 39113, 735, 27, 689, 656, 2800, 1339, 4600, 53, 122020, 115785, 34, 816, 1339, 46887, 18, 147, 53905, 1951, 42238, 41170, 17732, 834, 436, 15, 27523, 98733, 217, 147, 5542, 4981, 930, 17347, 16, 2], [20091, 629, 94, 82786, 58, 490, 20, 1528, 84, 53905, 344, 80592, 110128, 18822, 5267, 1306, 62, 152537, 308, 7997, 401, 124427, 549, 35442, 225, 109, 15055, 25748, 147, 7119, 43712, 34, 767, 135366, 18, 16, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [592, 63784, 119466, 17, 147808, 88214, 18, 656, 81, 32, 3296, 10280, 16, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], "attention_mask": [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]}  # noqa: E501
						# fmt: on

						self.tokenizer_integration_test_util(
						    expected_encoding=lowerCamelCase_		,       model_name="microsoft/xprophetnet-large-wiki100-cased"		,       revision="1acad1643ddd54a44df6a1b797ada8373685d90e"		,       )
