





import unittest

from transformers import XLMConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

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


if is_torch_available():
		import torch

		from transformers import (
		    XLMForMultipleChoice,
		    XLMForQuestionAnswering,
		    XLMForQuestionAnsweringSimple,
		    XLMForSequenceClassification,
		    XLMForTokenClassification,
		    XLMModel,
		    XLMWithLMHeadModel,
		)
		from transformers.models.xlm.modeling_xlm import XLM_PRETRAINED_MODEL_ARCHIVE_LIST

class 		snake_case_   :







	'''simple docstring'''




	def __init__(						self							:     int					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     Union[str, Any]=13					,      __lowerCamelCase							:     str=7					,      __lowerCamelCase							:     Dict=True					,      __lowerCamelCase							:     Any=True					,      __lowerCamelCase							:     Optional[int]=True					,      __lowerCamelCase							:     Union[str, Any]=True					,      __lowerCamelCase							:     str=True					,      __lowerCamelCase							:     Optional[int]=False					,      __lowerCamelCase							:     Union[str, Any]=False					,      __lowerCamelCase							:     List[str]=False					,      __lowerCamelCase							:     Union[str, Any]=2					,      __lowerCamelCase							:     Dict=99					,      __lowerCamelCase							:     Union[str, Any]=0					,      __lowerCamelCase							:     Any=32					,      __lowerCamelCase							:     List[Any]=5					,      __lowerCamelCase							:     List[str]=4					,      __lowerCamelCase							:     Dict=0.1					,      __lowerCamelCase							:     Any=0.1					,      __lowerCamelCase							:     Any=512					,      __lowerCamelCase							:     Tuple=2					,      __lowerCamelCase							:     Any=0.02					,      __lowerCamelCase							:     str=2					,      __lowerCamelCase							:     Optional[int]=4					,      __lowerCamelCase							:     Union[str, Any]="last"					,      __lowerCamelCase							:     Tuple=True					,      __lowerCamelCase							:     Union[str, Any]=None					,      __lowerCamelCase							:     List[Any]=0					,      )       -> Union[str, Any]:

			'''simple docstring'''




			__lowercase											=     parent
			__lowercase											=     batch_size
			__lowercase											=     seq_length
			__lowercase											=     is_training
			__lowercase											=     use_input_lengths
			__lowercase											=     use_token_type_ids
			__lowercase											=     use_labels
			__lowercase											=     gelu_activation
			__lowercase											=     sinusoidal_embeddings
			__lowercase											=     causal
			__lowercase											=     asm
			__lowercase											=     n_langs
			__lowercase											=     vocab_size
			__lowercase											=     n_special
			__lowercase											=     hidden_size
			__lowercase											=     num_hidden_layers
			__lowercase											=     num_attention_heads
			__lowercase											=     hidden_dropout_prob
			__lowercase											=     attention_probs_dropout_prob
			__lowercase											=     max_position_embeddings
			__lowercase											=     type_sequence_label_size
			__lowercase											=     initializer_range
			__lowercase											=     num_labels
			__lowercase											=     num_choices
			__lowercase											=     summary_type
			__lowercase											=     use_proj
			__lowercase											=     scope
			__lowercase											=     bos_token_id




	def    UpperCAmelCase			(						self							:     Optional[int]   )       -> List[Any]:

			'''simple docstring'''




			__lowercase											=     ids_tensor([self.batch_size, self.seq_length]					,      self.vocab_size   )
			__lowercase											=     random_attention_mask([self.batch_size, self.seq_length]   )

			__lowercase											=     None
			if self.use_input_lengths:
					__lowercase											=     (
					    ids_tensor([self.batch_size]					,      vocab_size=2   ) + self.seq_length - 2
					)  # small variation of seq_length

			__lowercase											=     None
			if self.use_token_type_ids:
					__lowercase											=     ids_tensor([self.batch_size, self.seq_length]					,      self.n_langs   )

			__lowercase											=     None
			__lowercase											=     None
			__lowercase											=     None
			if self.use_labels:
					__lowercase											=     ids_tensor([self.batch_size]					,      self.type_sequence_label_size   )
					__lowercase											=     ids_tensor([self.batch_size, self.seq_length]					,      self.num_labels   )
					__lowercase											=     ids_tensor([self.batch_size]					,      2   ).float()
					__lowercase											=     ids_tensor([self.batch_size]					,      self.num_choices   )

			__lowercase											=     self.get_config()

			return (
			    config,
			    input_ids,
			    token_type_ids,
			    input_lengths,
			    sequence_labels,
			    token_labels,
			    is_impossible_labels,
			    choice_labels,
			    input_mask,
			)




	def    UpperCAmelCase			(						self							:     Union[str, Any]   )       -> str:

			'''simple docstring'''




			return XLMConfig(
			    vocab_size=self.vocab_size					,      n_special=self.n_special					,      emb_dim=self.hidden_size					,      n_layers=self.num_hidden_layers					,      n_heads=self.num_attention_heads					,      dropout=self.hidden_dropout_prob					,      attention_dropout=self.attention_probs_dropout_prob					,      gelu_activation=self.gelu_activation					,      sinusoidal_embeddings=self.sinusoidal_embeddings					,      asm=self.asm					,      causal=self.causal					,      n_langs=self.n_langs					,      max_position_embeddings=self.max_position_embeddings					,      initializer_range=self.initializer_range					,      summary_type=self.summary_type					,      use_proj=self.use_proj					,      num_labels=self.num_labels					,      bos_token_id=self.bos_token_id					,      )




	def    UpperCAmelCase			(						self							:     int					,      __lowerCamelCase							:     Union[str, Any]					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     Tuple					,      __lowerCamelCase							:     Dict					,      __lowerCamelCase							:     str					,      __lowerCamelCase							:     Dict					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     Tuple					,      )       -> List[str]:

			'''simple docstring'''




			__lowercase											=     XLMModel(config=__lowerCamelCase   )
			model.to(__lowerCamelCase   )
			model.eval()
			__lowercase											=     model(__lowerCamelCase					,      lengths=__lowerCamelCase					,      langs=__lowerCamelCase   )
			__lowercase											=     model(__lowerCamelCase					,      langs=__lowerCamelCase   )
			__lowercase											=     model(__lowerCamelCase   )
			self.parent.assertEqual(result.last_hidden_state.shape					,      (self.batch_size, self.seq_length, self.hidden_size)   )




	def    UpperCAmelCase			(						self							:     int					,      __lowerCamelCase							:     str					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     str					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     List[str]					,      )       -> Optional[Any]:

			'''simple docstring'''




			__lowercase											=     XLMWithLMHeadModel(__lowerCamelCase   )
			model.to(__lowerCamelCase   )
			model.eval()

			__lowercase											=     model(__lowerCamelCase					,      token_type_ids=__lowerCamelCase					,      labels=__lowerCamelCase   )
			self.parent.assertEqual(result.loss.shape					,      ()   )
			self.parent.assertEqual(result.logits.shape					,      (self.batch_size, self.seq_length, self.vocab_size)   )




	def    UpperCAmelCase			(						self							:     Any					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     Union[str, Any]					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     Any					,      )       -> Any:

			'''simple docstring'''




			__lowercase											=     XLMForQuestionAnsweringSimple(__lowerCamelCase   )
			model.to(__lowerCamelCase   )
			model.eval()

			__lowercase											=     model(__lowerCamelCase   )

			__lowercase											=     model(__lowerCamelCase					,      start_positions=__lowerCamelCase					,      end_positions=__lowerCamelCase   )
			__lowercase											=     outputs
			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    UpperCAmelCase			(						self							:     List[str]					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     Tuple					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     str					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     str					,      )       -> List[Any]:

			'''simple docstring'''




			__lowercase											=     XLMForQuestionAnswering(__lowerCamelCase   )
			model.to(__lowerCamelCase   )
			model.eval()

			__lowercase											=     model(__lowerCamelCase   )

			__lowercase											=     model(
			    __lowerCamelCase					,      start_positions=__lowerCamelCase					,      end_positions=__lowerCamelCase					,      cls_index=__lowerCamelCase					,      is_impossible=__lowerCamelCase					,      p_mask=__lowerCamelCase					,      )

			__lowercase											=     model(
			    __lowerCamelCase					,      start_positions=__lowerCamelCase					,      end_positions=__lowerCamelCase					,      cls_index=__lowerCamelCase					,      is_impossible=__lowerCamelCase					,      )

			((__lowercase)						,      )											=     result_with_labels.to_tuple()

			__lowercase											=     model(__lowerCamelCase					,      start_positions=__lowerCamelCase					,      end_positions=__lowerCamelCase   )

			((__lowercase)						,      )											=     result_with_labels.to_tuple()

			self.parent.assertEqual(result_with_labels.loss.shape					,      ()   )
			self.parent.assertEqual(result.start_top_log_probs.shape					,      (self.batch_size, model.config.start_n_top)   )
			self.parent.assertEqual(result.start_top_index.shape					,      (self.batch_size, model.config.start_n_top)   )
			self.parent.assertEqual(
			    result.end_top_log_probs.shape					,      (self.batch_size, model.config.start_n_top * model.config.end_n_top)   )
			self.parent.assertEqual(
			    result.end_top_index.shape					,      (self.batch_size, model.config.start_n_top * model.config.end_n_top)   )
			self.parent.assertEqual(result.cls_logits.shape					,      (self.batch_size,)   )




	def    UpperCAmelCase			(						self							:     List[Any]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     str					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     List[str]					,      )       -> Optional[int]:

			'''simple docstring'''




			__lowercase											=     XLMForSequenceClassification(__lowerCamelCase   )
			model.to(__lowerCamelCase   )
			model.eval()

			__lowercase											=     model(__lowerCamelCase   )
			__lowercase											=     model(__lowerCamelCase					,      labels=__lowerCamelCase   )
			self.parent.assertEqual(result.loss.shape					,      ()   )
			self.parent.assertEqual(result.logits.shape					,      (self.batch_size, self.type_sequence_label_size)   )




	def    UpperCAmelCase			(						self							:     List[str]					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     Union[str, Any]					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     List[str]					,      )       -> str:

			'''simple docstring'''




			__lowercase											=     self.num_labels
			__lowercase											=     XLMForTokenClassification(__lowerCamelCase   )
			model.to(__lowerCamelCase   )
			model.eval()

			__lowercase											=     model(__lowerCamelCase					,      attention_mask=__lowerCamelCase					,      labels=__lowerCamelCase   )
			self.parent.assertEqual(result.logits.shape					,      (self.batch_size, self.seq_length, self.num_labels)   )




	def    UpperCAmelCase			(						self							:     int					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     Dict					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     Tuple					,      __lowerCamelCase							:     str					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     Dict					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     Union[str, Any]					,      )       -> List[Any]:

			'''simple docstring'''




			__lowercase											=     self.num_choices
			__lowercase											=     XLMForMultipleChoice(config=__lowerCamelCase   )
			model.to(__lowerCamelCase   )
			model.eval()
			__lowercase											=     input_ids.unsqueeze(1   ).expand(-1					,      self.num_choices					,      -1   ).contiguous()
			__lowercase											=     token_type_ids.unsqueeze(1   ).expand(-1					,      self.num_choices					,      -1   ).contiguous()
			__lowercase											=     input_mask.unsqueeze(1   ).expand(-1					,      self.num_choices					,      -1   ).contiguous()
			__lowercase											=     model(
			    __lowerCamelCase					,      attention_mask=__lowerCamelCase					,      token_type_ids=__lowerCamelCase					,      labels=__lowerCamelCase					,      )
			self.parent.assertEqual(result.logits.shape					,      (self.batch_size, self.num_choices)   )






	def    UpperCAmelCase			(						self							:     Dict   )       -> str:

			'''simple docstring'''




			__lowercase											=     self.prepare_config_and_inputs()
			(
			    (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      (
			    __lowercase
			)						,      
			)											=     config_and_inputs
			__lowercase											=     {'input_ids': input_ids, 'token_type_ids': token_type_ids, 'lengths': input_lengths}
			return config, inputs_dict





@require_torch
class 		snake_case_   (							UpperCAmelCase_     ,     UpperCAmelCase_     ,     UpperCAmelCase_     ,     unittest.TestCase						):







	'''simple docstring'''
	__UpperCamelCase   =		(
	    (
	        XLMModel,
	        XLMWithLMHeadModel,
	        XLMForQuestionAnswering,
	        XLMForSequenceClassification,
	        XLMForQuestionAnsweringSimple,
	        XLMForTokenClassification,
	        XLMForMultipleChoice,
	    )
	    if is_torch_available()
	    else ()
	)
	__UpperCamelCase   =		(
	    (XLMWithLMHeadModel,) if is_torch_available() else ()
	)  # TODO (PVP): Check other models whether language generation is also applicable
	__UpperCamelCase   =		(
	    {
	        '''feature-extraction''': XLMModel,
	        '''fill-mask''': XLMWithLMHeadModel,
	        '''question-answering''': XLMForQuestionAnsweringSimple,
	        '''text-classification''': XLMForSequenceClassification,
	        '''text-generation''': XLMWithLMHeadModel,
	        '''token-classification''': XLMForTokenClassification,
	        '''zero-shot''': XLMForSequenceClassification,
	    }
	    if is_torch_available()
	    else {}
	)




	def    UpperCAmelCase			(						self							:     Any					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     Optional[int]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     List[Any]   )       -> Optional[int]:

			'''simple docstring'''




			if (
			    pipeline_test_casse_name == "QAPipelineTests"
			    and tokenizer_name is not None
			    and not tokenizer_name.endswith('Fast'   )
			):
					# `QAPipelineTests` fails for a few models when the slower tokenizer are used.
					# (The slower tokenizers were never used for pipeline tests before the pipeline testing rework)
					# TODO: check (and possibly fix) the `QAPipelineTests` with slower tokenizer
					return True

			return False




	def    UpperCAmelCase			(						self							:     List[Any]					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     Optional[Any]					,      __lowerCamelCase							:     List[Any]=False   )       -> Optional[int]:

			'''simple docstring'''




			__lowercase											=     super()._prepare_for_class(__lowerCamelCase					,      __lowerCamelCase					,      return_labels=__lowerCamelCase   )

			if return_labels:
					if model_class.__name__ == "XLMForQuestionAnswering":
							__lowercase											=     torch.zeros(
							    self.model_tester.batch_size					,      dtype=torch.long					,      device=__lowerCamelCase   )
							__lowercase											=     torch.zeros(
							    self.model_tester.batch_size					,      dtype=torch.long					,      device=__lowerCamelCase   )

			return inputs_dict




	def    UpperCAmelCase			(						self							:     Dict   )       -> Any:

			'''simple docstring'''




			__lowercase											=     XLMModelTester(self   )
			__lowercase											=     ConfigTester(self					,      config_class=__lowerCamelCase					,      emb_dim=37   )




	def    UpperCAmelCase			(						self							:     List[Any]   )       -> Optional[int]:

			'''simple docstring'''




			self.config_tester.run_common_tests()




	def    UpperCAmelCase			(						self							:     Optional[int]   )       -> List[str]:

			'''simple docstring'''




			__lowercase											=     self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_xlm_model(*__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     int   )       -> Any:

			'''simple docstring'''




			__lowercase											=     self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_xlm_lm_head(*__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Union[str, Any]   )       -> List[Any]:

			'''simple docstring'''




			__lowercase											=     self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_xlm_simple_qa(*__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Tuple   )       -> str:

			'''simple docstring'''




			__lowercase											=     self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_xlm_qa(*__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Optional[Any]   )       -> List[Any]:

			'''simple docstring'''




			__lowercase											=     self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_xlm_sequence_classif(*__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     str   )       -> Tuple:

			'''simple docstring'''




			__lowercase											=     self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_xlm_token_classif(*__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Tuple   )       -> Optional[int]:

			'''simple docstring'''




			__lowercase											=     self.model_tester.prepare_config_and_inputs()
			self.model_tester.create_and_check_xlm_for_multiple_choice(*__lowerCamelCase   )




	def    UpperCAmelCase			(						self							:     Dict					,      __lowerCamelCase							:     Tuple					,      __lowerCamelCase							:     Union[str, Any]					,      __lowerCamelCase							:     Tuple					,      __lowerCamelCase							:     List[str]					,      __lowerCamelCase							:     str					,      __lowerCamelCase							:     List[Any]=False					,      __lowerCamelCase							:     int=1   )       -> int:

			'''simple docstring'''




			self.assertIsInstance(__lowerCamelCase					,      __lowerCamelCase   )
			self.assertListEqual(
			    [isinstance(__lowerCamelCase					,      __lowerCamelCase   ) for iter_attentions in attentions]					,      [True] * len(__lowerCamelCase   )   )
			self.assertEqual(len(__lowerCamelCase   )					,      (max_length - min_length) * num_beam_groups   )

			for idx, iter_attentions in enumerate(__lowerCamelCase   ):
					# adds PAD dummy token
					__lowercase											=     min_length + idx + 1
					__lowercase											=     min_length + idx + 1

					__lowercase											=     (
					    batch_size * num_beam_groups,
					    config.num_attention_heads,
					    tgt_len,
					    src_len,
					)
					# check attn size
					self.assertListEqual(
					    [layer_attention.shape for layer_attention in iter_attentions]					,      [expected_shape] * len(__lowerCamelCase   )   )




	def    UpperCAmelCase			(						self							:     List[Any]					,      __lowerCamelCase							:     List[Any]					,      __lowerCamelCase							:     Dict					,      __lowerCamelCase							:     Any					,      __lowerCamelCase							:     Tuple					,      __lowerCamelCase							:     int					,      __lowerCamelCase							:     Tuple=False					,      __lowerCamelCase							:     Optional[int]=1   )       -> int:

			'''simple docstring'''




			self.assertIsInstance(__lowerCamelCase					,      __lowerCamelCase   )
			self.assertListEqual(
			    [isinstance(__lowerCamelCase					,      __lowerCamelCase   ) for iter_hidden_states in hidden_states]					,      [True] * len(__lowerCamelCase   )					,      )
			self.assertEqual(len(__lowerCamelCase   )					,      (max_length - min_length) * num_beam_groups   )

			for idx, iter_hidden_states in enumerate(__lowerCamelCase   ):
					# adds PAD dummy token
					__lowercase											=     min_length + idx + 1
					__lowercase											=     (batch_size * num_beam_groups, seq_len, config.hidden_size)
					# check hidden size
					self.assertListEqual(
					    [layer_hidden_states.shape for layer_hidden_states in iter_hidden_states]					,      [expected_shape] * len(__lowerCamelCase   )					,      )
			pass






	@slow
	def    UpperCAmelCase			(						self							:     Optional[Any]   )       -> List[str]:

			'''simple docstring'''




			for model_name in XLM_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
					__lowercase											=     XLMModel.from_pretrained(__lowerCamelCase   )
					self.assertIsNotNone(__lowerCamelCase   )





@require_torch
class 		snake_case_   (							unittest.TestCase						):







	'''simple docstring'''




	@slow
	def    UpperCAmelCase			(						self							:     Dict   )       -> Optional[Any]:

			'''simple docstring'''




			__lowercase											=     XLMWithLMHeadModel.from_pretrained('xlm-mlm-en-2048'   )
			model.to(__lowerCamelCase   )
			__lowercase											=     torch.tensor([[14, 447]]					,      dtype=torch.long					,      device=__lowerCamelCase   )  # the president
			__lowercase											=     [
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			    14,
			    447,
			]  # the president the president the president the president the president the president the president the president the president the president
			# TODO(PVP): this and other input_ids I tried for generation give pretty bad results. Not sure why. Model might just not be made for auto-regressive inference
			__lowercase											=     model.generate(__lowerCamelCase					,      do_sample=__lowerCamelCase   )
			self.assertListEqual(output_ids[0].cpu().numpy().tolist()					,      __lowerCamelCase   )











from __future__ import annotations



def  SCREAMING_SNAKE_CASE				(      snake_case						,   snake_case							)		->    list[tuple[int, int]]:
		__lowercase						,      __lowercase											=     position
		__lowercase											=     [
		    (y + 1, x + 2),
		    (y - 1, x + 2),
		    (y + 1, x - 2),
		    (y - 1, x - 2),
		    (y + 2, x + 1),
		    (y + 2, x - 1),
		    (y - 2, x + 1),
		    (y - 2, x - 1),
		]
		__lowercase											=     []

		for position in positions:
				__lowercase						,      __lowercase											=     position
				if 0 <= y_test < n and 0 <= x_test < n:
						permissible_positions.append(snake_case							)

		return permissible_positions



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    bool:
		return not any(elem == 0 for row in board for elem in row							)



def  SCREAMING_SNAKE_CASE				(      snake_case						,   snake_case						,   snake_case							)		->    bool:

		if is_complete(snake_case							):
				return True

		for position in get_valid_pos(snake_case						,   len(snake_case							)							):
				__lowercase						,      __lowercase											=     position

				if board[y][x] == 0:
						__lowercase											=     curr + 1
						if open_knight_tour_helper(snake_case						,   snake_case						,   curr + 1							):
								return True
						__lowercase											=     0

		return False



def  SCREAMING_SNAKE_CASE				(      snake_case							)		->    list[list[int]]:
		__lowercase											=     [[0 for i in range(snake_case							)] for j in range(snake_case							)]

		for i in range(snake_case							):
				for j in range(snake_case							):
						__lowercase											=     1
						if open_knight_tour_helper(snake_case						,   (i, j)						,   1							):
								return board
						__lowercase											=     0

		__lowercase											=     F"Open Kight Tour cannot be performed on a board of size {n}"
		raise ValueError(snake_case							)


if __name__ == "__main__":
		import doctest

		doctest.testmod()




