


'''simple docstring'''


from __future__ import annotations







def 			snake_case_   (  SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       Dict     		=      position
				_SCREAMING_SNAKE_CASE :       List[str]     		=      [
				    (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),
				]
				_SCREAMING_SNAKE_CASE :       Optional[int]     		=      []

				for position in positions:
								_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       Optional[int]     		=      position
								if 0 <= y_test < n and 0 <= x_test < n:
												permissible_positions.append(SCREAMING_SNAKE_CASE__     )

				return permissible_positions







def 			snake_case_   (  SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





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







def 			snake_case_   (  SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





				if is_complete(SCREAMING_SNAKE_CASE__     ):
								return True

				for position in get_valid_pos(SCREAMING_SNAKE_CASE__							,      len(SCREAMING_SNAKE_CASE__     )     ):
								_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       int     		=      position

								if board[y][x] == 0:
												_SCREAMING_SNAKE_CASE :       Optional[int]     		=      curr + 1
												if open_knight_tour_helper(SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      curr + 1     ):
																return True
												_SCREAMING_SNAKE_CASE :       str     		=      0

				return False







def 			snake_case_   (  SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE :       str     		=      [[0 for i in range(SCREAMING_SNAKE_CASE__     )] for j in range(SCREAMING_SNAKE_CASE__     )]

				for i in range(SCREAMING_SNAKE_CASE__     ):
								for j in range(SCREAMING_SNAKE_CASE__     ):
												_SCREAMING_SNAKE_CASE :       Optional[int]     		=      1
												if open_knight_tour_helper(SCREAMING_SNAKE_CASE__							,      (i, j)							,      1     ):
																return board
												_SCREAMING_SNAKE_CASE :       Optional[int]     		=      0

				_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      f"""Open Kight Tour cannot be performed on a board of size {n}"""
				raise ValueError(SCREAMING_SNAKE_CASE__     )


if __name__ == "__main__":
				import doctest

				doctest.testmod()








'''simple docstring'''


from typing import Any





class     lowercase__  :





							'''simple docstring'''


							def __init__(    self    ,					__snake_case  ):
											_SCREAMING_SNAKE_CASE :       Dict     		=      data
											_SCREAMING_SNAKE_CASE :       Optional[int]     		=      None






							def __repr__(    self  ):
											return f"""Node({self.data})"""





class     lowercase__  :





							'''simple docstring'''


							def __init__(    self  ):
											_SCREAMING_SNAKE_CASE :       Any     		=      None






							def __iter__(    self  ):
											_SCREAMING_SNAKE_CASE :       Any     		=      self.head
											while node:
															yield node.data
															_SCREAMING_SNAKE_CASE :       List[Any]     		=      node.next






							def __len__(    self  ):
											return sum(1 for _ in self  )






							def __repr__(    self  ):
											return "->".join([str(__snake_case  ) for item in self]  )






							def __getitem__(    self    ,					__snake_case  ):
											if not 0 <= index < len(self  ):
															raise ValueError("""list index out of range."""  )
											for i, node in enumerate(self  ):
															if i == index:
																			return node
											return None






							def __setitem__(    self    ,					__snake_case    ,					__snake_case  ):
											if not 0 <= index < len(self  ):
															raise ValueError("""list index out of range."""  )
											_SCREAMING_SNAKE_CASE :       Any     		=      self.head
											for _ in range(__snake_case  ):
															_SCREAMING_SNAKE_CASE :       List[Any]     		=      current.next
											_SCREAMING_SNAKE_CASE :       Dict     		=      data






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											self.insert_nth(len(self  )    ,					__snake_case  )






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											self.insert_nth(0    ,					__snake_case  )






							def UpperCAmelCase_	(    self    ,					__snake_case    ,					__snake_case  ):
											if not 0 <= index <= len(self  ):
															raise IndexError("""list index out of range"""  )
											_SCREAMING_SNAKE_CASE :       Optional[int]     		=      Node(__snake_case  )
											if self.head is None:
															_SCREAMING_SNAKE_CASE :       str     		=      new_node
											elif index == 0:
															_SCREAMING_SNAKE_CASE :       Tuple     		=      self.head  # link new_node to head
															_SCREAMING_SNAKE_CASE :       str     		=      new_node
											else:
															_SCREAMING_SNAKE_CASE :       Tuple     		=      self.head
															for _ in range(index - 1  ):
																			_SCREAMING_SNAKE_CASE :       List[str]     		=      temp.next
															_SCREAMING_SNAKE_CASE :       Tuple     		=      temp.next
															_SCREAMING_SNAKE_CASE :       Dict     		=      new_node






							def UpperCAmelCase_	(    self  ):  # print every node data
											print(self  )






							def UpperCAmelCase_	(    self  ):
											return self.delete_nth(0  )






							def UpperCAmelCase_	(    self  ):  # delete from tail
											return self.delete_nth(len(self  ) - 1  )






							def UpperCAmelCase_	(    self    ,					__snake_case = 0  ):
											if not 0 <= index <= len(self  ) - 1:  # test if index is valid
															raise IndexError("""List index out of range."""  )
											_SCREAMING_SNAKE_CASE :       Tuple     		=      self.head  # default first node
											if index == 0:
															_SCREAMING_SNAKE_CASE :       List[Any]     		=      self.head.next
											else:
															_SCREAMING_SNAKE_CASE :       Tuple     		=      self.head
															for _ in range(index - 1  ):
																			_SCREAMING_SNAKE_CASE :       Any     		=      temp.next
															_SCREAMING_SNAKE_CASE :       Any     		=      temp.next
															_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      temp.next.next
											return delete_node.data






							def UpperCAmelCase_	(    self  ):
											return self.head is None






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       Dict     		=      None
											_SCREAMING_SNAKE_CASE :       int     		=      self.head

											while current:
															# Store the current node's next node.
															_SCREAMING_SNAKE_CASE :       List[Any]     		=      current.next
															# Make the current node's next point backwards
															_SCREAMING_SNAKE_CASE :       Tuple     		=      prev
															# Make the previous node be the current node
															_SCREAMING_SNAKE_CASE :       int     		=      current
															# Make the current node the next node (to progress iteration)
															_SCREAMING_SNAKE_CASE :       Any     		=      next_node
											# Return prev in order to put the head at the end
											_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      prev







def 			snake_case_   (  ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE :       Dict     		=      LinkedList()
				assert linked_list.is_empty() is True
				assert str(SCREAMING_SNAKE_CASE__     ) == ""

				try:
								linked_list.delete_head()
								raise AssertionError  # This should not happen.
				except IndexError:
								assert True  # This should happen.

				try:
								linked_list.delete_tail()
								raise AssertionError  # This should not happen.
				except IndexError:
								assert True  # This should happen.

				for i in range(10     ):
								assert len(SCREAMING_SNAKE_CASE__     ) == i
								linked_list.insert_nth(SCREAMING_SNAKE_CASE__							,      i + 1     )
				assert str(SCREAMING_SNAKE_CASE__     ) == "->".join(str(SCREAMING_SNAKE_CASE__     ) for i in range(1							,      11     )     )

				linked_list.insert_head(0     )
				linked_list.insert_tail(11     )
				assert str(SCREAMING_SNAKE_CASE__     ) == "->".join(str(SCREAMING_SNAKE_CASE__     ) for i in range(0							,      12     )     )

				assert linked_list.delete_head() == 0
				assert linked_list.delete_nth(9     ) == 10
				assert linked_list.delete_tail() == 11
				assert len(SCREAMING_SNAKE_CASE__     ) == 9
				assert str(SCREAMING_SNAKE_CASE__     ) == "->".join(str(SCREAMING_SNAKE_CASE__     ) for i in range(1							,      10     )     )

				assert all(linked_list[i] == i + 1 for i in range(0							,      9     )     ) is True

				for i in range(0							,      9     ):
								_SCREAMING_SNAKE_CASE :       List[str]     		=      -i
				assert all(linked_list[i] == -i for i in range(0							,      9     )     ) is True

				linked_list.reverse()
				assert str(SCREAMING_SNAKE_CASE__     ) == "->".join(str(SCREAMING_SNAKE_CASE__     ) for i in range(-8							,      1     )     )







def 			snake_case_   (  ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE :       Optional[int]     		=      [
				    -9,
				    100,
				    Node(7734_5112     ),
				    """dlrow olleH""",
				    7,
				    5555,
				    0,
				    -1_9_2.5_5_5_5_5,
				    """Hello, world!""",
				    7_7.9,
				    Node(10     ),
				    None,
				    None,
				    1_2.2_0,
				]
				_SCREAMING_SNAKE_CASE :       Optional[int]     		=      LinkedList()

				for i in test_input:
								linked_list.insert_tail(SCREAMING_SNAKE_CASE__     )

				# Check if it's empty or not
				assert linked_list.is_empty() is False
				assert (
				    str(SCREAMING_SNAKE_CASE__     ) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
				    "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
				)

				# Delete the head
				_SCREAMING_SNAKE_CASE :       Any     		=      linked_list.delete_head()
				assert result == -9
				assert (
				    str(SCREAMING_SNAKE_CASE__     ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
				    "Hello, world!->77.9->Node(10)->None->None->12.2"
				)

				# Delete the tail
				_SCREAMING_SNAKE_CASE :       List[Any]     		=      linked_list.delete_tail()
				assert result == 1_2.2
				assert (
				    str(SCREAMING_SNAKE_CASE__     ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
				    "Hello, world!->77.9->Node(10)->None->None"
				)

				# Delete a node in specific location in linked list
				_SCREAMING_SNAKE_CASE :       Optional[int]     		=      linked_list.delete_nth(10     )
				assert result is None
				assert (
				    str(SCREAMING_SNAKE_CASE__     ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
				    "Hello, world!->77.9->Node(10)->None"
				)

				# Add a Node instance to its head
				linked_list.insert_head(Node("""Hello again, world!"""     )     )
				assert (
				    str(SCREAMING_SNAKE_CASE__     )
				    == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
				    "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
				)

				# Add None to its tail
				linked_list.insert_tail(SCREAMING_SNAKE_CASE__     )
				assert (
				    str(SCREAMING_SNAKE_CASE__     )
				    == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
				    "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
				)

				# Reverse the linked list
				linked_list.reverse()
				assert (
				    str(SCREAMING_SNAKE_CASE__     )
				    == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
				    "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
				)







def 			snake_case_   (  ):







				"""simple docstring"""





				from doctest import testmod

				testmod()

				_SCREAMING_SNAKE_CASE :       Optional[int]     		=      LinkedList()
				linked_list.insert_head(input("""Inserting 1st at head """     ).strip()     )
				linked_list.insert_head(input("""Inserting 2nd at head """     ).strip()     )
				print("""\nPrint list:"""     )
				linked_list.print_list()
				linked_list.insert_tail(input("""\nInserting 1st at tail """     ).strip()     )
				linked_list.insert_tail(input("""Inserting 2nd at tail """     ).strip()     )
				print("""\nPrint list:"""     )
				linked_list.print_list()
				print("""\nDelete head"""     )
				linked_list.delete_head()
				print("""Delete tail"""     )
				linked_list.delete_tail()
				print("""\nPrint list:"""     )
				linked_list.print_list()
				print("""\nReverse linked list"""     )
				linked_list.reverse()
				print("""\nPrint list:"""     )
				linked_list.print_list()
				print("""\nString representation of linked list:"""     )
				print(SCREAMING_SNAKE_CASE__     )
				print("""\nReading/changing Node data using indexing:"""     )
				print(f"""Element at Position 1: {linked_list[1]}"""     )
				_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      input("""Enter New Value: """     ).strip()
				print("""New list:"""     )
				print(SCREAMING_SNAKE_CASE__     )
				print(f"""length of linked_list is : {len(SCREAMING_SNAKE_CASE__     )}"""     )


if __name__ == "__main__":
				main()




