




"""simple docstring"""




import os
import tempfile
import unittest

from transformers import NezhaConfig, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_torch_gpu, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
			import torch

			from transformers import (
			    MODEL_FOR_PRETRAINING_MAPPING,
			    NezhaForMaskedLM,
			    NezhaForMultipleChoice,
			    NezhaForNextSentencePrediction,
			    NezhaForPreTraining,
			    NezhaForQuestionAnswering,
			    NezhaForSequenceClassification,
			    NezhaForTokenClassification,
			    NezhaModel,
			)
			from transformers.models.nezha.modeling_nezha import NEZHA_PRETRAINED_MODEL_ARCHIVE_LIST

class    UpperCAmelCase_  :
		def __init__(		self							,		UpperCamelCase_							,		UpperCamelCase_=13							,		UpperCamelCase_=7							,		UpperCamelCase_=True							,		UpperCamelCase_=True							,		UpperCamelCase_=True							,		UpperCamelCase_=True							,		UpperCamelCase_=99							,		UpperCamelCase_=32							,		UpperCamelCase_=5							,		UpperCamelCase_=4							,		UpperCamelCase_=37							,		UpperCamelCase_="gelu"							,		UpperCamelCase_=0.1							,		UpperCamelCase_=0.1							,		UpperCamelCase_=1_28							,		UpperCamelCase_=32							,		UpperCamelCase_=16							,		UpperCamelCase_=2							,		UpperCamelCase_=0.0_2							,		UpperCamelCase_=3							,		UpperCamelCase_=4							,		UpperCamelCase_=None							,		)		->    List[str]:
					__lowercase       :   Optional[Any]        =    parent
					__lowercase       :   Dict        =    batch_size
					__lowercase       :   Optional[Any]        =    seq_length
					__lowercase       :   Optional[Any]        =    is_training
					__lowercase       :   Union[str, Any]        =    use_input_mask
					__lowercase       :   List[Any]        =    use_token_type_ids
					__lowercase       :   str        =    use_labels
					__lowercase       :   Optional[Any]        =    vocab_size
					__lowercase       :   Union[str, Any]        =    hidden_size
					__lowercase       :   Optional[int]        =    num_hidden_layers
					__lowercase       :   Optional[int]        =    num_attention_heads
					__lowercase       :   List[Any]        =    intermediate_size
					__lowercase       :   List[str]        =    hidden_act
					__lowercase       :   List[Any]        =    hidden_dropout_prob
					__lowercase       :   Optional[int]        =    attention_probs_dropout_prob
					__lowercase       :   Dict        =    max_position_embeddings
					__lowercase       :   Any        =    type_vocab_size
					__lowercase       :   Any        =    type_sequence_label_size
					__lowercase       :   List[Any]        =    initializer_range
					__lowercase       :   Dict        =    num_labels
					__lowercase       :   Any        =    num_choices
					__lowercase       :   Union[str, Any]        =    scope
		def      _lowerCamelCase				(		self    )		->    Tuple:
					__lowercase       :   int        =    ids_tensor([self.batch_size, self.seq_length]							,		self.vocab_size    )

					__lowercase       :   Tuple        =    None
					if self.use_input_mask:
								__lowercase       :   Tuple        =    random_attention_mask([self.batch_size, self.seq_length]    )

					__lowercase       :   Tuple        =    None
					if self.use_token_type_ids:
								__lowercase       :   List[Any]        =    ids_tensor([self.batch_size, self.seq_length]							,		self.type_vocab_size    )

					__lowercase       :   Optional[int]        =    None
					__lowercase       :   Optional[Any]        =    None
					__lowercase       :   Optional[int]        =    None
					if self.use_labels:
								__lowercase       :   Any        =    ids_tensor([self.batch_size]							,		self.type_sequence_label_size    )
								__lowercase       :   Union[str, Any]        =    ids_tensor([self.batch_size, self.seq_length]							,		self.num_labels    )
								__lowercase       :   List[Any]        =    ids_tensor([self.batch_size]							,		self.num_choices    )

					__lowercase       :   Dict        =    self.get_config()

					return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels
		def      _lowerCamelCase				(		self    )		->    Dict:
					return NezhaConfig(
					    vocab_size=self.vocab_size							,		hidden_size=self.hidden_size							,		num_hidden_layers=self.num_hidden_layers							,		num_attention_heads=self.num_attention_heads							,		intermediate_size=self.intermediate_size							,		hidden_act=self.hidden_act							,		hidden_dropout_prob=self.hidden_dropout_prob							,		attention_probs_dropout_prob=self.attention_probs_dropout_prob							,		max_position_embeddings=self.max_position_embeddings							,		type_vocab_size=self.type_vocab_size							,		is_decoder=UpperCamelCase_							,		initializer_range=self.initializer_range							,		)
		def      _lowerCamelCase				(		self    )		->    Optional[Any]:
					(
					    __lowercase				
					)       :   List[Any]        =    self.prepare_config_and_inputs()

					__lowercase       :   List[Any]        =    True
					__lowercase       :   Tuple        =    floats_tensor([self.batch_size, self.seq_length, self.hidden_size]    )
					__lowercase       :   Tuple        =    ids_tensor([self.batch_size, self.seq_length]							,		vocab_size=2    )

					return (
					    config,
					    input_ids,
					    token_type_ids,
					    input_mask,
					    sequence_labels,
					    token_labels,
					    choice_labels,
					    encoder_hidden_states,
					    encoder_attention_mask,
					)
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    Optional[Any]:
					__lowercase       :   List[str]        =    NezhaModel(config=UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   Dict        =    model(UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_    )
					__lowercase       :   List[str]        =    model(UpperCamelCase_							,		token_type_ids=UpperCamelCase_    )
					__lowercase       :   Any        =    model(UpperCamelCase_    )
					self.parent.assertEqual(result.last_hidden_state.shape							,		(self.batch_size, self.seq_length, self.hidden_size)    )
					self.parent.assertEqual(result.pooler_output.shape							,		(self.batch_size, self.hidden_size)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		)		->    Optional[Any]:
					__lowercase       :   Union[str, Any]        =    True
					__lowercase       :   Optional[int]        =    NezhaModel(UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   Any        =    model(
					    UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		encoder_hidden_states=UpperCamelCase_							,		encoder_attention_mask=UpperCamelCase_							,		)
					__lowercase       :   Dict        =    model(
					    UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		encoder_hidden_states=UpperCamelCase_							,		)
					__lowercase       :   List[str]        =    model(UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_    )
					self.parent.assertEqual(result.last_hidden_state.shape							,		(self.batch_size, self.seq_length, self.hidden_size)    )
					self.parent.assertEqual(result.pooler_output.shape							,		(self.batch_size, self.hidden_size)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    Union[str, Any]:
					__lowercase       :   List[Any]        =    NezhaForMaskedLM(config=UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   Dict        =    model(UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		labels=UpperCamelCase_    )
					self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.seq_length, self.vocab_size)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    List[str]:
					__lowercase       :   List[Any]        =    NezhaForNextSentencePrediction(config=UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   str        =    model(
					    UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		labels=UpperCamelCase_							,		)
					self.parent.assertEqual(result.logits.shape							,		(self.batch_size, 2)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    List[Any]:
					__lowercase       :   Tuple        =    NezhaForPreTraining(config=UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   Optional[int]        =    model(
					    UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		labels=UpperCamelCase_							,		next_sentence_label=UpperCamelCase_							,		)
					self.parent.assertEqual(result.prediction_logits.shape							,		(self.batch_size, self.seq_length, self.vocab_size)    )
					self.parent.assertEqual(result.seq_relationship_logits.shape							,		(self.batch_size, 2)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    Union[str, Any]:
					__lowercase       :   Optional[Any]        =    NezhaForQuestionAnswering(config=UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   Tuple        =    model(
					    UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		start_positions=UpperCamelCase_							,		end_positions=UpperCamelCase_							,		)
					self.parent.assertEqual(result.start_logits.shape							,		(self.batch_size, self.seq_length)    )
					self.parent.assertEqual(result.end_logits.shape							,		(self.batch_size, self.seq_length)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    Union[str, Any]:
					__lowercase       :   Any        =    self.num_labels
					__lowercase       :   Optional[Any]        =    NezhaForSequenceClassification(UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   Tuple        =    model(UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		labels=UpperCamelCase_    )
					self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.num_labels)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    Tuple:
					__lowercase       :   Dict        =    self.num_labels
					__lowercase       :   str        =    NezhaForTokenClassification(config=UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   Any        =    model(UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		labels=UpperCamelCase_    )
					self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.seq_length, self.num_labels)    )
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_    )		->    Optional[Any]:
					__lowercase       :   Optional[Any]        =    self.num_choices
					__lowercase       :   Any        =    NezhaForMultipleChoice(config=UpperCamelCase_    )
					model.to(UpperCamelCase_    )
					model.eval()
					__lowercase       :   int        =    input_ids.unsqueeze(1    ).expand(-1							,		self.num_choices							,		-1    ).contiguous()
					__lowercase       :   str        =    token_type_ids.unsqueeze(1    ).expand(-1							,		self.num_choices							,		-1    ).contiguous()
					__lowercase       :   Optional[Any]        =    input_mask.unsqueeze(1    ).expand(-1							,		self.num_choices							,		-1    ).contiguous()
					__lowercase       :   Any        =    model(
					    UpperCamelCase_							,		attention_mask=UpperCamelCase_							,		token_type_ids=UpperCamelCase_							,		labels=UpperCamelCase_							,		)
					self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.num_choices)    )
		def      _lowerCamelCase				(		self    )		->    Tuple:
					__lowercase       :   int        =    self.prepare_config_and_inputs()
					(
					    __lowercase				
					)       :   Any        =    config_and_inputs
					__lowercase       :   str        =    {'input_ids': input_ids, 'token_type_ids': token_type_ids, 'attention_mask': input_mask}
					return config, inputs_dict


@require_torch
class    UpperCAmelCase_  (       snake_case					, snake_case					, snake_case					, unittest.TestCase						):
		UpperCamelCase						 =(
		    (
		        NezhaModel,
		        NezhaForMaskedLM,
		        NezhaForMultipleChoice,
		        NezhaForNextSentencePrediction,
		        NezhaForPreTraining,
		        NezhaForQuestionAnswering,
		        NezhaForSequenceClassification,
		        NezhaForTokenClassification,
		    )
		    if is_torch_available()
		    else ()
		)
		UpperCamelCase						 =(
		    {
		        "feature-extraction": NezhaModel,
		        "fill-mask": NezhaForMaskedLM,
		        "question-answering": NezhaForQuestionAnswering,
		        "text-classification": NezhaForSequenceClassification,
		        "token-classification": NezhaForTokenClassification,
		        "zero-shot": NezhaForSequenceClassification,
		    }
		    if is_torch_available()
		    else {}
		)
		UpperCamelCase						 =True
		def      _lowerCamelCase				(		self							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_=False    )		->    Optional[int]:
					__lowercase       :   int        =    super()._prepare_for_class(UpperCamelCase_							,		UpperCamelCase_							,		return_labels=UpperCamelCase_    )

					if return_labels:
								if model_class in get_values(UpperCamelCase_    ):
											__lowercase       :   Tuple        =    torch.zeros(
											    (self.model_tester.batch_size, self.model_tester.seq_length)							,		dtype=torch.long							,		device=UpperCamelCase_    )
											__lowercase       :   Optional[Any]        =    torch.zeros(
											    self.model_tester.batch_size							,		dtype=torch.long							,		device=UpperCamelCase_    )
					return inputs_dict
		def      _lowerCamelCase				(		self    )		->    List[str]:
					__lowercase       :   Optional[int]        =    NezhaModelTester(self    )
					__lowercase       :   Optional[int]        =    ConfigTester(self							,		config_class=UpperCamelCase_							,		hidden_size=37    )
		def      _lowerCamelCase				(		self    )		->    Optional[int]:
					self.config_tester.run_common_tests()
		def      _lowerCamelCase				(		self    )		->    List[str]:
					__lowercase       :   List[str]        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_model(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    Any:
					__lowercase       :   int        =    self.model_tester.prepare_config_and_inputs_for_decoder()
					self.model_tester.create_and_check_model_as_decoder(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    Optional[int]:
					(
					    __lowercase				
					)       :   str        =    self.model_tester.prepare_config_and_inputs_for_decoder()

					__lowercase       :   str        =    None

					self.model_tester.create_and_check_model_as_decoder(
					    UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		UpperCamelCase_							,		)
		def      _lowerCamelCase				(		self    )		->    Dict:
					__lowercase       :   int        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_masked_lm(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    str:
					__lowercase       :   Union[str, Any]        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_multiple_choice(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    List[Any]:
					__lowercase       :   Optional[int]        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_next_sequence_prediction(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    Optional[Any]:
					__lowercase       :   List[str]        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_pretraining(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    Optional[int]:
					__lowercase       :   Optional[int]        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_question_answering(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    Dict:
					__lowercase       :   int        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_sequence_classification(*UpperCamelCase_    )
		def      _lowerCamelCase				(		self    )		->    List[Any]:
					__lowercase       :   Any        =    self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_token_classification(*UpperCamelCase_    )
		@slow
		def      _lowerCamelCase				(		self    )		->    Union[str, Any]:







					for model_name in NEZHA_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
								__lowercase       :   Optional[Any]        =    NezhaModel.from_pretrained(UpperCamelCase_    )
								self.assertIsNotNone(UpperCamelCase_    )
		@slow
		@require_torch_gpu
		def      _lowerCamelCase				(		self    )		->    str:
					__lowercase       :   Optional[int]        =    self.model_tester.prepare_config_and_inputs_for_common()
					for model_class in self.all_model_classes:
								# NezhaForMultipleChoice behaves incorrectly in JIT environments.
								if model_class == NezhaForMultipleChoice:
											return

								__lowercase       :   Dict        =    True
								__lowercase       :   Any        =    model_class(config=UpperCamelCase_    )

								__lowercase       :   Union[str, Any]        =    self._prepare_for_class(UpperCamelCase_							,		UpperCamelCase_    )
								__lowercase       :   int        =    torch.jit.trace(
								    UpperCamelCase_							,		(inputs_dict['''input_ids'''].to('''cpu'''    ), inputs_dict['''attention_mask'''].to('''cpu'''    ))    )

								with tempfile.TemporaryDirectory() as tmp:
											torch.jit.save(UpperCamelCase_							,		os.path.join(UpperCamelCase_							,		'''bert.pt'''    )    )
											__lowercase       :   Any        =    torch.jit.load(os.path.join(UpperCamelCase_							,		'''bert.pt'''    )							,		map_location=UpperCamelCase_    )
											loaded(inputs_dict['''input_ids'''].to(UpperCamelCase_    )							,		inputs_dict['''attention_mask'''].to(UpperCamelCase_    )    )


@require_torch
class    UpperCAmelCase_  (       unittest.TestCase						):
		@slow
		def      _lowerCamelCase				(		self    )		->    Any:
					__lowercase       :   str        =    NezhaModel.from_pretrained('''sijunhe/nezha-cn-base'''    )
					__lowercase       :   Any        =    torch.tensor([[0, 1, 2, 3, 4, 5]]    )
					__lowercase       :   Union[str, Any]        =    torch.tensor([[0, 1, 1, 1, 1, 1]]    )
					with torch.no_grad():
								__lowercase       :   Optional[int]        =    model(UpperCamelCase_							,		attention_mask=UpperCamelCase_    )[0]
					__lowercase       :   Union[str, Any]        =    torch.Size((1, 6, 7_68)    )
					self.assertEqual(output.shape							,		UpperCamelCase_    )
					__lowercase       :   Optional[int]        =    torch.tensor([[[0.0_6_8_5, 0.2_4_4_1, 0.1_1_0_2], [0.0_6_0_0, 0.1_9_0_6, 0.1_3_4_9], [0.0_2_2_1, 0.0_8_1_9, 0.0_5_8_6]]]    )

					self.assertTrue(torch.allclose(output[:, 1:4, 1:4]							,		UpperCamelCase_							,		atol=1E-4    )    )
		@slow
		def      _lowerCamelCase				(		self    )		->    Optional[Any]:
					__lowercase       :   Any        =    NezhaForMaskedLM.from_pretrained('''sijunhe/nezha-cn-base'''    )
					__lowercase       :   Optional[int]        =    torch.tensor([[0, 1, 2, 3, 4, 5]]    )
					__lowercase       :   Optional[int]        =    torch.tensor([[1, 1, 1, 1, 1, 1]]    )
					with torch.no_grad():
								__lowercase       :   Optional[int]        =    model(UpperCamelCase_							,		attention_mask=UpperCamelCase_    )[0]
					__lowercase       :   int        =    torch.Size((1, 6, 2_11_28)    )
					self.assertEqual(output.shape							,		UpperCamelCase_    )
					__lowercase       :   List[Any]        =    torch.tensor(
					    [[-2.7_9_3_9, -1.7_9_0_2, -2.2_1_8_9], [-2.8_5_8_5, -1.8_9_0_8, -2.3_7_2_3], [-2.6_4_9_9, -1.7_7_5_0, -2.2_5_5_8]]    )

					self.assertTrue(torch.allclose(output[:, 1:4, 1:4]							,		UpperCamelCase_							,		atol=1E-4    )    )





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  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		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  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		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  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		Matrix | None:
			if location := find_empty_location(SCREAMING_SNAKE_CASE_     ):
						lowerCAmelCase__      ,				lowerCAmelCase__      :      Any         =		location
			else:
						# If the location is ``None``, then the grid is solved.
						return grid

			for digit in range(1       ,							10     ):
						if is_safe(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     ):
									lowerCAmelCase__      :      Optional[Any]         =		digit

									if sudoku(SCREAMING_SNAKE_CASE_     ) is not None:
												return grid

									lowerCAmelCase__      :      List[Any]         =		0

			return None
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		None:
			for row in grid:
						for cell in row:
									print(SCREAMING_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.""")