


'''simple docstring'''



from __future__ import annotations

__lowercase     :						int	=     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   lowerCamelCase							(_SCREAMING_SNAKE_CASE				:       Matrix						,				_SCREAMING_SNAKE_CASE				:       int						,				_SCREAMING_SNAKE_CASE				:       int						,				_SCREAMING_SNAKE_CASE				:       int       ):
					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				:       Matrix       ):
					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       ):
					if location := find_empty_location(_SCREAMING_SNAKE_CASE       ):
										__a   ,    __a      :	str    =  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       ):
															__a      :	Optional[int]    =  digit

															if sudoku(_SCREAMING_SNAKE_CASE       ) is not None:
																				return grid

															__a      :	Tuple    =  0

					return None






def   lowerCamelCase							(_SCREAMING_SNAKE_CASE				:       Matrix       ):
					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:')
		__lowercase     :						List[str]	=     sudoku(example_grid)
		if solution is not None:
			print_solution(solution)
		else:
			print('Cannot find a solution.')







'''simple docstring'''



import gc
import importlib.metadata
import tempfile
import unittest

from packaging import version

from transformers import (
    AutoModel,
    AutoModelForCausalLM,
    AutoModelForSeqaSeqLM,
    AutoModelForSequenceClassification,
    AutoTokenizer,
    BitsAndBytesConfig,
    pipeline,
)
from transformers.testing_utils import (
    is_torch_available,
    require_accelerate,
    require_bitsandbytes,
    require_torch,
    require_torch_gpu,
    require_torch_multi_gpu,
    slow,
)






def   lowerCamelCase							(_SCREAMING_SNAKE_CASE				:       str       ):
					if model.config.model_type == "gpt2":
										return model.transformer.h[0].mlp.c_fc
					return model.transformer.h[0].mlp.dense_ah_to_h


if is_torch_available():
	import torch
	import torch.nn as nn





	class 							__UpperCamelCase    (		nn.Module ):




		def __init__(       self						,    __a						,    __a							):

							'''simple docstring'''





							super().__init__()
							__a      :	int    =  module
							__a      :	List[Any]    =  nn.Sequential(
							    nn.Linear(module.in_features						,    __a						,    bias=__a							)						,    nn.Linear(__a						,    module.out_features						,    bias=__a							)						,    )
							__a      :	int    =  (2.0 / (5 * min(module.in_features						,    module.out_features							))) ** 0.5
							nn.init.normal_(self.adapter[0].weight						,    std=__a							)
							nn.init.zeros_(self.adapter[1].weight							)
							self.adapter.to(module.weight.device							)





		def 				__UpperCAmelCase							(       self						,    __a						,    *__a						,    **__a							):

							'''simple docstring'''





							return self.module(__a						,    *__a						,    **__a							) + self.adapter(__a							)





@require_bitsandbytes
@require_accelerate
@require_torch
@require_torch_gpu
@slow
class 							__UpperCamelCase    (		unittest.TestCase ):
	# We keep the constants inside the init function and model loading inside setUp function

	# We need to test on relatively large models (aka >1b parameters otherwise the quantiztion may not work as expected)
	# Therefore here we use only bloom-1b3 to test our module
	A_           =   "bigscience/bloom-1b7"

	# Constant values
	A_           =   2.109659552692574

	A_           =   "Hello my name is"
	A_           =   set()
	EXPECTED_OUTPUTS.add("Hello my name is John and I am a professional photographer. I" )
	EXPECTED_OUTPUTS.add("Hello my name is John.\nI am a friend of your father.\n" )
	EXPECTED_OUTPUTS.add("Hello my name is John Doe, I am a student at the University" )
	A_           =   10




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	List[Any]    =  AutoTokenizer.from_pretrained(self.model_name							)





class 							__UpperCamelCase    (		lowerCAmelCase_ ):




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						super().setUp()

						# Models and tokenizer
						__a      :	int    =  AutoModelForCausalLM.from_pretrained(
						    self.model_name						,    torch_dtype=torch.floataa						,    device_map='auto'							)
						__a      :	Union[str, Any]    =  AutoModelForCausalLM.from_pretrained(self.model_name						,    load_in_abit=__a						,    device_map='auto'							)




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						del self.model_fpaa
						del self.model_abit

						gc.collect()
						torch.cuda.empty_cache()




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	List[str]    =  self.model_abit.config

						self.assertTrue(hasattr(__a						,    'quantization_config'							)							)

						__a      :	Union[str, Any]    =  config.to_dict()
						__a      :	Tuple    =  config.to_diff_dict()

						__a      :	Tuple    =  config.to_json_string()




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						from bitsandbytes.nn import Paramsabit

						__a      :	List[Any]    =  self.model_fpaa.get_memory_footprint()
						__a      :	List[Any]    =  self.model_abit.get_memory_footprint()

						self.assertAlmostEqual(mem_fpaa / mem_abit						,    self.EXPECTED_RELATIVE_DIFFERENCE							)
						__a      :	Tuple    =  get_some_linear_layer(self.model_abit							)
						self.assertTrue(linear.weight.__class__ == Paramsabit							)




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						from transformers import TaPreTrainedModel

						self.model_fpaa.get_memory_footprint()
						self.model_abit.get_memory_footprint()

						for name, module in self.model_abit.named_modules():
											if isinstance(__a						,    torch.nn.Linear							):
																if name not in ["lm_head"] + TaPreTrainedModel._keep_in_fpaa_modules:
																					# 4-bit parameters are packed in uint8 variables
																					self.assertTrue(module.weight.dtype == torch.uinta							)




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	Union[str, Any]    =  self.tokenizer(self.input_text						,    return_tensors='pt'							)
						__a      :	Union[str, Any]    =  self.model_abit.generate(input_ids=encoded_input['input_ids'].to(0							)						,    max_new_tokens=10							)

						self.assertIn(self.tokenizer.decode(output_sequences[0]						,    skip_special_tokens=__a							)						,    self.EXPECTED_OUTPUTS							)




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	Tuple    =  BitsAndBytesConfig()
						__a      :	Tuple    =  True

						__a      :	int    =  AutoModelForCausalLM.from_pretrained(
						    self.model_name						,    quantization_config=__a						,    device_map='auto'							)

						__a      :	str    =  self.tokenizer(self.input_text						,    return_tensors='pt'							)
						__a      :	List[Any]    =  model_abit_from_config.generate(
						    input_ids=encoded_input['input_ids'].to(0							)						,    max_new_tokens=10							)

						self.assertIn(self.tokenizer.decode(output_sequences[0]						,    skip_special_tokens=__a							)						,    self.EXPECTED_OUTPUTS							)




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						with self.assertRaises(__a							), tempfile.TemporaryDirectory() as tmpdirname:
											self.model_abit.save_pretrained(__a							)




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	str    =  BitsAndBytesConfig()

						with self.assertRaises(__a							):
											__a      :	List[str]    =  AutoModelForCausalLM.from_pretrained(
											    self.model_name						,    quantization_config=__a						,    load_in_abit=__a						,    device_map='auto'						,    bnb_abit_quant_type='nf4'						,    )




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						with self.assertRaises(__a							):
											# Tries with `str`
											self.model_abit.to('cpu'							)

						with self.assertRaises(__a							):
											# Tries with a `dtype``
											self.model_abit.to(torch.floataa							)

						with self.assertRaises(__a							):
											# Tries with a `device`
											self.model_abit.to(torch.device('cuda:0'							)							)

						with self.assertRaises(__a							):
											# Tries with a `device`
											self.model_abit.float()

						with self.assertRaises(__a							):
											# Tries with a `device`
											self.model_abit.half()

						# Test if we did not break anything
						__a      :	List[str]    =  self.tokenizer(self.input_text						,    return_tensors='pt'							)

						__a      :	Optional[int]    =  self.model_fpaa.to(torch.floataa							)
						__a      :	Tuple    =  self.model_fpaa.generate(input_ids=encoded_input['input_ids'].to(0							)						,    max_new_tokens=10							)

						# Check this does not throw an error
						__a      :	List[Any]    =  self.model_fpaa.to('cpu'							)

						# Check this does not throw an error
						__a      :	Union[str, Any]    =  self.model_fpaa.half()

						# Check this does not throw an error
						__a      :	Union[str, Any]    =  self.model_fpaa.float()





	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	str    =  AutoModelForSeqaSeqLM.from_pretrained('t5-small'						,    load_in_abit=__a						,    device_map='auto'							)
						self.assertTrue(model.decoder.block[0].layer[2].DenseReluDense.wo.weight.dtype == torch.floataa							)





@require_bitsandbytes
@require_accelerate
@require_torch
@require_torch_gpu
@slow
class 							__UpperCamelCase    (		unittest.TestCase ):




	@classmethod
	def 				__UpperCAmelCase							(       cls							):

						'''simple docstring'''





						__a      :	Any    =  't5-small'
						__a      :	Tuple    =  'google/flan-t5-small'  # flan-t5 uses dense-act instead of dense-relu-dense
						__a      :	int    =  AutoTokenizer.from_pretrained(cls.model_name							)
						__a      :	Union[str, Any]    =  'Translate in German: Hello, my dog is cute'




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						gc.collect()
						torch.cuda.empty_cache()




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						from transformers import TaForConditionalGeneration

						__a      :	Optional[int]    =  TaForConditionalGeneration._keep_in_fpaa_modules
						__a      :	List[str]    =  None

						# test with `t5-small`
						__a      :	List[str]    =  TaForConditionalGeneration.from_pretrained(self.model_name						,    load_in_abit=__a						,    device_map='auto'							)
						__a      :	Optional[int]    =  self.tokenizer(self.input_text						,    return_tensors='pt'							).to(0							)
						__a      :	Any    =  model.generate(**__a							)

						# test with `flan-t5-small`
						__a      :	List[str]    =  TaForConditionalGeneration.from_pretrained(
						    self.dense_act_model_name						,    load_in_abit=__a						,    device_map='auto'							)
						__a      :	str    =  self.tokenizer(self.input_text						,    return_tensors='pt'							).to(0							)
						__a      :	List[Any]    =  model.generate(**__a							)
						__a      :	Optional[int]    =  modules





	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						import bitsandbytes as bnb

						from transformers import TaForConditionalGeneration

						# test with `t5-small`
						__a      :	List[Any]    =  TaForConditionalGeneration.from_pretrained(self.model_name						,    load_in_abit=__a						,    device_map='auto'							)

						# there was a bug with decoders - this test checks that it is fixed
						self.assertTrue(isinstance(model.decoder.block[0].layer[0].SelfAttention.q						,    bnb.nn.Linearabit							)							)

						__a      :	str    =  self.tokenizer(self.input_text						,    return_tensors='pt'							).to(0							)
						__a      :	List[str]    =  model.generate(**__a							)

						# test with `flan-t5-small`
						__a      :	List[Any]    =  TaForConditionalGeneration.from_pretrained(
						    self.dense_act_model_name						,    load_in_abit=__a						,    device_map='auto'							)
						__a      :	Optional[Any]    =  self.tokenizer(self.input_text						,    return_tensors='pt'							).to(0							)
						__a      :	int    =  model.generate(**__a							)





class 							__UpperCamelCase    (		lowerCAmelCase_ ):




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						super().setUp()
						# model_name
						__a      :	List[Any]    =  'bigscience/bloom-560m'
						__a      :	Union[str, Any]    =  't5-small'

						# Different types of model

						__a      :	Optional[Any]    =  AutoModel.from_pretrained(self.model_name						,    load_in_abit=__a						,    device_map='auto'							)
						# Sequence classification model
						__a      :	Dict    =  AutoModelForSequenceClassification.from_pretrained(
						    self.model_name						,    load_in_abit=__a						,    device_map='auto'							)
						# CausalLM model
						__a      :	Union[str, Any]    =  AutoModelForCausalLM.from_pretrained(self.model_name						,    load_in_abit=__a						,    device_map='auto'							)
						# Seq2seq model
						__a      :	Any    =  AutoModelForSeqaSeqLM.from_pretrained(
						    self.seq_to_seq_name						,    load_in_abit=__a						,    device_map='auto'							)




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						del self.base_model
						del self.sequence_model
						del self.model_abit
						del self.seq_to_seq_model

						gc.collect()
						torch.cuda.empty_cache()





	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						from bitsandbytes.nn import Paramsabit

						self.assertTrue(self.base_model.h[-1].mlp.dense_ah_to_h.weight.__class__ == Paramsabit							)

						# Other heads should be nn.Parameter
						self.assertTrue(self.model_abit.lm_head.weight.__class__ == torch.nn.Parameter							)
						self.assertTrue(self.sequence_model.score.weight.__class__ == torch.nn.Parameter							)
						self.assertTrue(self.seq_to_seq_model.lm_head.weight.__class__ == torch.nn.Parameter							)





class 							__UpperCamelCase    (		lowerCAmelCase_ ):




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						super().setUp()




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						del self.pipe

						gc.collect()
						torch.cuda.empty_cache()





	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	Dict    =  pipeline(
						    'text-generation'						,    model=self.model_name						,    model_kwargs={'device_map': 'auto', 'load_in_4bit': True, 'torch_dtype': torch.floataa}						,    max_new_tokens=self.MAX_NEW_TOKENS						,    )

						# Real second forward pass
						__a      :	str    =  self.pipe(self.input_text							)
						self.assertIn(pipeline_output[0]['generated_text']						,    self.EXPECTED_OUTPUTS							)





@require_torch_multi_gpu
class 							__UpperCamelCase    (		lowerCAmelCase_ ):




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						super().setUp()





	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	Any    =  AutoModelForCausalLM.from_pretrained(
						    self.model_name						,    load_in_abit=__a						,    device_map='balanced'							)

						# Check correct device map
						self.assertEqual(set(model_parallel.hf_device_map.values()							)						,    {0, 1}							)

						# Check that inference pass works on the model
						__a      :	List[Any]    =  self.tokenizer(self.input_text						,    return_tensors='pt'							)

						# Second real batch
						__a      :	str    =  model_parallel.generate(input_ids=encoded_input['input_ids'].to(0							)						,    max_new_tokens=10							)
						self.assertIn(self.tokenizer.decode(output_parallel[0]						,    skip_special_tokens=__a							)						,    self.EXPECTED_OUTPUTS							)





class 							__UpperCamelCase    (		lowerCAmelCase_ ):




	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						__a      :	Union[str, Any]    =  'facebook/opt-350m'
						super().setUp()





	def 				__UpperCAmelCase							(       self							):

						'''simple docstring'''





						if version.parse(importlib.metadata.version('bitsandbytes'							)							) < version.parse('0.37.0'							):
											return

						# Step 1: freeze all parameters
						__a      :	Union[str, Any]    =  AutoModelForCausalLM.from_pretrained(self.model_name						,    load_in_abit=__a							)

						self.assertEqual(set(model.hf_device_map.values()							)						,    {torch.cuda.current_device()}							)

						for param in model.parameters():
											__a      :	Tuple    =  False  # freeze the model - train adapters later
											if param.ndim == 1:
																# cast the small parameters (e.g. layernorm) to fp32 for stability
																__a      :	Tuple    =  param.data.to(torch.floataa							)

        # Step 2: add adapters
						for _, module in model.named_modules():
											if "OPTAttention" in repr(type(__a							)							):
																__a      :	str    =  LoRALayer(module.q_proj						,    rank=16							)
																__a      :	str    =  LoRALayer(module.k_proj						,    rank=16							)
																__a      :	Optional[int]    =  LoRALayer(module.v_proj						,    rank=16							)

        # Step 3: dummy batch
						__a      :	List[str]    =  self.tokenizer('Test batch '						,    return_tensors='pt'							).to(0							)

						# Step 4: Check if the gradient is not None
						with torch.cuda.amp.autocast():
											__a      :	int    =  model.forward(**__a							)
											out.logits.norm().backward()

						for module in model.modules():
											if isinstance(__a						,    __a							):
																self.assertTrue(module.adapter[1].weight.grad is not None							)
																self.assertTrue(module.adapter[1].weight.grad.norm().item() > 0							)
											elif isinstance(__a						,    nn.Embedding							):
																self.assertTrue(module.weight.grad is None							)





class 							__UpperCamelCase    (		lowerCAmelCase_ ):
	A_           =   "gpt2-xl"
	A_           =   3.3191854854152187



