


from __future__ import annotations





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase ):


						'''simple docstring'''






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

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

						return permissible_positions





def 	_lowerCAmelCase       (    _lowerCAmelCase ):


						'''simple docstring'''






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





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase      ,	_lowerCAmelCase ):


						'''simple docstring'''






						if is_complete(_lowerCAmelCase ):
												return True

						for position in get_valid_pos(_lowerCAmelCase      ,	len(_lowerCAmelCase ) ):
												__snake_case		,					__snake_case				=		position

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

						return False





def 	_lowerCAmelCase       (    _lowerCAmelCase ):


						'''simple docstring'''






						__snake_case				=		[[0 for i in range(_lowerCAmelCase )] for j in range(_lowerCAmelCase )]

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

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


if __name__ == "__main__":
	import doctest

	doctest.testmod()









import itertools
import string
from collections.abc import Generator, Iterable





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	Generator[tuple[str, ...], None, None]:


						'''simple docstring'''






						__snake_case				=		iter(_lowerCAmelCase )
						while True:
												__snake_case				=		tuple(itertools.islice(_lowerCAmelCase      ,	_lowerCAmelCase ) )
												if not chunk:
																		return
												yield chunk





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		"".join([c.upper() for c in dirty if c in string.ascii_letters] )
						__snake_case				=		""

						if len(_lowerCAmelCase ) < 2:
												return dirty

						for i in range(len(_lowerCAmelCase ) - 1 ):
												clean += dirty[i]

												if dirty[i] == dirty[i + 1]:
																		clean += "X"

						clean += dirty[-1]

						if len(_lowerCAmelCase ) & 1:
												clean += "X"

						return clean





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	list[str]:


						'''simple docstring'''






						__snake_case				=		"ABCDEFGHIKLMNOPQRSTUVWXYZ"
						# we're using a list instead of a '2d' array because it makes the math
						# for setting up the table and doing the actual encoding/decoding simpler
						__snake_case				=		[]

						# copy key chars into the table if they are in `alphabet` ignoring duplicates
						for char in key.upper():
												if char not in table and char in alphabet:
																		table.append(_lowerCAmelCase )

    # fill the rest of the table in with the remaining alphabet chars
						for char in alphabet:
												if char not in table:
																		table.append(_lowerCAmelCase )

						return table





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		generate_table(_lowerCAmelCase )
						__snake_case				=		prepare_input(_lowerCAmelCase )
						__snake_case				=		""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowerCAmelCase      ,	2 ):
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )

												if rowa == rowa:
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
												elif cola == cola:
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
												else:  # rectangle
																		ciphertext += table[rowa * 5 + cola]
																		ciphertext += table[rowa * 5 + cola]

						return ciphertext





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	str:


						'''simple docstring'''






						__snake_case				=		generate_table(_lowerCAmelCase )
						__snake_case				=		""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowerCAmelCase      ,	2 ):
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )
												__snake_case		,					__snake_case				=		divmod(table.index(_lowerCAmelCase )      ,	5 )

												if rowa == rowa:
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
												elif cola == cola:
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
												else:  # rectangle
																		plaintext += table[rowa * 5 + cola]
																		plaintext += table[rowa * 5 + cola]

						return plaintext





