
from __future__ import annotations


def 							__A(lowerCAmelCase						,  lowerCAmelCase )		->				list[tuple[int, int]]:

		"""simple docstring"""






		_UpperCamelCase    ,	_UpperCamelCase						    =	position
		_UpperCamelCase						    =	[
		    (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),
		]
		_UpperCamelCase						    =	[]

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

		return permissible_positions


def 							__A(lowerCAmelCase )		->				bool:

		"""simple docstring"""






		return not any(elem == 0 for row in board for elem in row )


def 							__A(lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase )		->				bool:

		"""simple docstring"""






		if is_complete(lowerCAmelCase ):
				return True

		for position in get_valid_pos(lowerCAmelCase						,  len(lowerCAmelCase ) ):
				_UpperCamelCase    ,	_UpperCamelCase						    =	position

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

		return False


def 							__A(lowerCAmelCase )		->				list[list[int]]:

		"""simple docstring"""






		_UpperCamelCase						    =	[[0 for i in range(lowerCAmelCase )] for j in range(lowerCAmelCase )]

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

		_UpperCamelCase						    =	F'Open Kight Tour cannot be performed on a board of size {n}'
		raise ValueError(lowerCAmelCase )


if __name__ == "__main__":
						import doctest

						doctest.testmod()





def 							__A(lowerCAmelCase )		->				list[list[int]]:

		"""simple docstring"""






		_UpperCamelCase						    =	[]
		if len(lowerCAmelCase ) == 1:
				return [nums.copy()]
		for _ in range(len(lowerCAmelCase ) ):
				_UpperCamelCase						    =	nums.pop(0 )
				_UpperCamelCase						    =	permute(lowerCAmelCase )
				for perm in permutations:
						perm.append(lowerCAmelCase )
				result.extend(lowerCAmelCase )
				nums.append(lowerCAmelCase )
		return result


def 							__A(lowerCAmelCase )		->				Optional[int]:

		"""simple docstring"""






		def backtrack(lowerCAmelCase ):
				if start == len(lowerCAmelCase ) - 1:
						output.append(nums[:] )
				else:
						for i in range(lowerCAmelCase						,  len(lowerCAmelCase ) ):
								_UpperCamelCase    ,	_UpperCamelCase						    =	nums[i], nums[start]
								backtrack(start + 1 )
								_UpperCamelCase    ,	_UpperCamelCase						    =	nums[i], nums[start]  # backtrack

		_UpperCamelCase						    =	[]
		backtrack(0 )
		return output


if __name__ == "__main__":
		import doctest

		# use res to print the data in permute2 function
		lowerCamelCase__	=							permutea([1, 2, 3])
		print(res)
		doctest.testmod()



