• Le pavage d'un échiquier troué 2 sur 2 ne pose aucun problème.
• Pour un échiquier \(2^n \times 2^n \) :
  L' échiquier se découpe en 4 sous-échiquiers de taille \( 2^{n-1} \times 2^{n-1} \). Un seul de ces 4 sous-échiquiers contient le trou. On place un trimino au centre du grand échiquier de façon à ce qu'il couvre une case exactement de chacun des 3 sous-échiquiers ne possédant pas le trou.
  On est ramené au cas d'échiquiers \( 2^{n-1} \times 2^{n-1} \) troués, en considérant que l'unique case couverte par un morceau du trimino est un trou.

"""

On travaille avec un  échiquier 2^n sur 2^n.

Exemple d'échiquier 2^3 sur 2^3 avec les couples de coordonnées de chaque case :

|(lb, cb)  | (lb, cb+1) | (lb, cb+2) | (lb, cb+3) | (lb, cb+4) | (lb, cb+5) | (lb, cb+6) | (lb, cb+7) | 
|(lb+1, cb)|(lb+1, cb+1)|(lb+1, cb+2)|(lb+1, cb+3)|(lb+1, cb+4)|(lb+1, cb+5)|(lb+1, cb+6)|(lb+1, cb+7)| 
|(lb+2, cb)|(lb+2, cb+1)|(lb+2, cb+2)|(lb+2, cb+3)|(lb+2, cb+4)|(lb+2, cb+5)|(lb+2, cb+6)|(lb+2, cb+7)| 
|(lb+3, cb)|(lb+3, cb+1)|(lb+3, cb+2)|(lb+3, cb+3)|(lb+3, cb+4)|(lb+3, cb+5)|(lb+3, cb+6)|(lb+3, cb+7)| 
|(lb+4, cb)|(lb+4, cb+1)|(lb+4, cb+2)|(lb+4, cb+3)|(lb+4, cb+4)|(lb+4, cb+5)|(lb+4, cb+6)|(lb+4, cb+7)| 
|(lb+5, cb)|(lb+5, cb+1)|(lb+5, cb+2)|(lb+5, cb+3)|(lb+5, cb+4)|(lb+5, cb+5)|(lb+5, cb+6)|(lb+5, cb+7)| 
|(lb+6, cb)|(lb+6, cb+1)|(lb+6, cb+2)|(lb+6, cb+3)|(lb+6, cb+4)|(lb+6, cb+5)|(lb+6, cb+6)|(lb+6, cb+7)| 
|(lb+7, cb)|(lb+7, cb+1)|(lb+7, cb+2)|(lb+7, cb+3)|(lb+7, cb+4)|(lb+7, cb+5)|(lb+7, cb+6)|(lb+7, cb+7)| 


On note cote = 2^n

Les quatres cases centrales de l'échiquier 2^n sur 2^n ont pour coordonnées :

(lb + cote//2 - 1, cb + cote//2 -1 )  |  (lb + cote//2 - 1, cb + cote//2 + 0 )
-------------------------------------------------------------------------------
(lb + cote//2 + 0, cb + cote//2 -1 )  |  (lb + cote//2 + 0 , cb + cote//2 + 0 )
 


Au départ toutes les cases de l'échiquier sont à 0 sauf la case trouée.
Ensuite, une case porte le numéro du trimino placé dessus.

"""





from random import randint



def definir_echiquier(k) :
	"""
	définit un échiquier de taille 2^k sur 2^k
	avec un trou tiré au hasard
	"""
	n = 2**k
	echikier =  [[0 for j in range(n)] for i in range(n)]
	# on troue une case au hasard : 
	echikier[randint(0,n-1)][randint(0,n-1)] = -1  
	return echikier
 
 
def affiche_echiquier(echikier) :
	"""
	Fonction d'affichage de l'échiquier
	"""
	nbLignes = len(echikier)
	nbColonnes = len(echikier[0])
	for i in range(nbLignes) :
		for j in range(nbColonnes) :
			print(echikier[i][j], end="\t")
		print()

		
		
				
def reperetrou(echikier, lb, cb, cote):
	"""
	Dans le sous-echiquier de echikier
	de première case (en haut à gauche) de coordonnées (lb, cb) et de côté cote, 
	on considère qu'il n'y a qu'une seule case non nulle, 
	cette case peut alors être considérée comme un trou.
	
	On découpe ce sous-échiquer en 4 quarts et 
	on retourne (-1,-1) pour un trou dans le quart haut gauche
	(-1, 0) pour un trou dans le quart haut droit
	(0,-1) pour un trou dans le quart bas gauche
	(0,0) pour un trou dans le quart bas droit
	"""
	lm = lb + cote//2
	cm = cb + cote//2
	for i in range(lb, lb+cote):
		for j in range(cb, cb+cote):
			if echikier[i][j] != 0 : return(-(i < lm),-(j < cm))

		
def triminoAuCentre(echikier, lb, cb, cote, numero) :
	"""
	Dans le sous-echiquier de echikier
	de première case  (en haut à gauche) de coordonnées  (lb, cb) et de côté cote, 
	supposé n'avoir qu'un seul trou,  on place un trimino au centre.
	Ce trimino est placé de telle façon qu'il couvre une case exactement
	de chacun des quarts ne contenant pas le trou.
	
	Le trimino est représenté par un numéro (les trois cases recouvertes par ce 
	trimino seront donc recouvertes par ce même numéro)
	"""
	lm = lb + cote//2
	cm = cb + cote//2      
	(troux,trouy) = reperetrou(echikier, lb, cb, cote)
		
	for (x,y) in [(-1,-1), (-1,0), (0,0), (0,-1)] :
		if (x,y) != (troux,trouy) : echikier[lm+x][cm+y] = numero  

	# on ajoute une marque spéciale dans la case correspondant au coin
	# du trimino posé qui facilitera le dessin après coup 
	# bd : bas droit, trimino en J
	# hg : haut gauche, trimino en r
	# bg : bas gauche, trimino en L
	# hd : haut droit
	
	if (troux,trouy) == (-1,-1) : echikier[lm][cm] = str(echikier[lm][cm]) + 'bd'
	if (troux,trouy) == (0,0) : echikier[lm-1][cm-1] = str(echikier[lm-1][cm-1]) + 'hg'
	if (troux,trouy) == (-1,0) : echikier[lm][cm-1] = str(echikier[lm][cm-1]) + 'bg'
	if (troux,trouy) == (0,-1) : echikier[lm-1][cm] = str(echikier[lm-1][cm]) + 'hd'
	
	
 
def pavons(echikier) :
			
	n = len(echikier)
	numero = 1
	
	def pave(lb=0, cb=0, cote=n) :
		nonlocal numero
		if cote > 1:
            # on place un trimino au centre :
			triminoAuCentre(echikier, lb, cb, cote, numero)
			numero += 1
			
			# couverture par appels récursifs des 4 quarts :
			demicote = cote//2
			for (x,y) in [(0,0),(0,demicote),(demicote,0),(demicote,demicote)]:
				pave(lb+x, cb+y, demicote)
				 
				
	pave()
	
	

# on définit un échiquier :
echiquier = definir_echiquier(3)
# on lance le calcul de son pavage par triminos :
pavons(echiquier)
# on affiche le résultat :
affiche_echiquier(echiquier)

On trouvera la doc sur le module turtle ici.

"""

On travaille avec un  échiquier 2^n sur 2^n.

Exemple d'échiquier 2^3 sur 2^3 avec les couples de coordonnées de chaque case :

|(lb, cb)  | (lb, cb+1) | (lb, cb+2) | (lb, cb+3) | (lb, cb+4) | (lb, cb+5) | (lb, cb+6) | (lb, cb+7) | 
|(lb+1, cb)|(lb+1, cb+1)|(lb+1, cb+2)|(lb+1, cb+3)|(lb+1, cb+4)|(lb+1, cb+5)|(lb+1, cb+6)|(lb+1, cb+7)| 
|(lb+2, cb)|(lb+2, cb+1)|(lb+2, cb+2)|(lb+2, cb+3)|(lb+2, cb+4)|(lb+2, cb+5)|(lb+2, cb+6)|(lb+2, cb+7)| 
|(lb+3, cb)|(lb+3, cb+1)|(lb+3, cb+2)|(lb+3, cb+3)|(lb+3, cb+4)|(lb+3, cb+5)|(lb+3, cb+6)|(lb+3, cb+7)| 
|(lb+4, cb)|(lb+4, cb+1)|(lb+4, cb+2)|(lb+4, cb+3)|(lb+4, cb+4)|(lb+4, cb+5)|(lb+4, cb+6)|(lb+4, cb+7)| 
|(lb+5, cb)|(lb+5, cb+1)|(lb+5, cb+2)|(lb+5, cb+3)|(lb+5, cb+4)|(lb+5, cb+5)|(lb+5, cb+6)|(lb+5, cb+7)| 
|(lb+6, cb)|(lb+6, cb+1)|(lb+6, cb+2)|(lb+6, cb+3)|(lb+6, cb+4)|(lb+6, cb+5)|(lb+6, cb+6)|(lb+6, cb+7)| 
|(lb+7, cb)|(lb+7, cb+1)|(lb+7, cb+2)|(lb+7, cb+3)|(lb+7, cb+4)|(lb+7, cb+5)|(lb+7, cb+6)|(lb+7, cb+7)| 


On note cote = 2^n

Les quatres cases centrales de l'échiquier 2^n sur 2^n ont pour coordonnées :

(lb + cote//2 - 1, cb + cote//2 -1 )  |  (lb + cote//2 - 1, cb + cote//2 + 0 )
-------------------------------------------------------------------------------
(lb + cote//2 + 0, cb + cote//2 -1 )  |  (lb + cote//2 + 0 , cb + cote//2 + 0 )
 


Au départ toutes les cases de l'échiquier sont à 0 sauf la case trouée.
Ensuite, une case porte le numéro du trimino placé dessus.

"""





from random import randint
import turtle as tl

# pour définir les couleurs tortue en rgb :
tl.colormode(255)
# on cache la tortue :
tl.hideturtle()
# tortue rapide :
tl.speed(0)

# on définit une unité pour les dessins :
unite = 20



def definir_echiquier(k) :
	"""
	définit un échiquier de taille 2^k sur 2^k
	avec un trou tiré au hasard
	"""
	n = 2**k
	echikier =  [[0 for j in range(n)] for i in range(n)]
	# on troue une case au hasard : 
	echikier[randint(0,n-1)][randint(0,n-1)] = -1  
	return echikier
 
 
def affiche_echiquier(echikier) :
	"""
	Fonction d'affichage de l'échiquier
	"""
	nbLignes = len(echikier)
	nbColonnes = len(echikier[0])
	for i in range(nbLignes) :
		for j in range(nbColonnes) :
			print(echikier[i][j], end="\t")
		print()

		
		
				
def reperetrou(echikier, lb, cb, cote):
	"""
	Dans le sous-echiquier de echikier
	de première case (en haut à gauche) de coordonnées (lb, cb) et de côté cote, 
	on considère qu'il n'y a qu'une seule case non nulle, 
	cette case peut alors être considérée comme un trou.
	
	On découpe ce sous-échiquer en 4 quarts et 
	on retourne (-1,-1) pour un trou dans le quart haut gauche
	(-1, 0) pour un trou dans le quart haut droit
	(0,-1) pour un trou dans le quart bas gauche
	(0,0) pour un trou dans le quart bas droit
	"""
	lm = lb + cote//2
	cm = cb + cote//2
	for i in range(lb, lb+cote):
		for j in range(cb, cb+cote):
			if echikier[i][j] != 0 : return(-(i < lm),-(j < cm))

		
def triminoAuCentre(echikier, lb, cb, cote, numero) :
	"""
	Dans le sous-echiquier de echikier
	de première case  (en haut à gauche) de coordonnées  (lb, cb) et de côté cote, 
	supposé n'avoir qu'un seul trou,  on place un trimino au centre.
	Ce trimino est placé de telle façon qu'il couvre une case exactement
	de chacun des quarts ne contenant pas le trou.
	
	Le trimino est représenté par un numéro (les trois cases recouvertes par ce 
	trimino seront donc recouvertes par ce même numéro)
	"""
	lm = lb + cote//2
	cm = cb + cote//2      
	(troux,trouy) = reperetrou(echikier, lb, cb, cote)
		
	for (x,y) in [(-1,-1), (-1,0), (0,0), (0,-1)] :
		if (x,y) != (troux,trouy) : echikier[lm+x][cm+y] = numero  

	# on ajoute une marque spéciale dans la case correspondant au coin
	# du trimino posé qui facilitera le dessin après coup 
    # bd : bas droit, trimino en J
    # hg : haut gauche, trimino en r
    # bg : bas gauche, trimino en L
    # hd : haut droit
	
	if (troux,trouy) == (-1,-1) : echikier[lm][cm] = str(echikier[lm][cm]) + 'bd'
	if (troux,trouy) == (0,0) : echikier[lm-1][cm-1] = str(echikier[lm-1][cm-1]) + 'hg'
	if (troux,trouy) == (-1,0) : echikier[lm][cm-1] = str(echikier[lm][cm-1]) + 'bg'
	if (troux,trouy) == (0,-1) : echikier[lm-1][cm] = str(echikier[lm-1][cm]) + 'hd'
	
	
 
def pavons(echikier) :
			
	n = len(echikier)
	numero = 1
	
	def pave(lb=0, cb=0, cote=n) :
		nonlocal numero
		if cote > 1:
            # on place un trimino au centre :
			triminoAuCentre(echikier, lb, cb, cote, numero)
			numero += 1
			
			# couverture par appels récursifs des 4 quarts :
			demicote = cote//2
			for (x,y) in [(0,0),(0,demicote),(demicote,0),(demicote,demicote)]:
				pave(lb+x, cb+y, demicote)
				 
				
	pave()
	
	
	
	
	
	

def dessine_trimino(orientation, coinx, coiny, cote = unite) :
	""" orientation : bg, bd, hg ou hd. """
	
	
	tl.penup()
	tl.pensize(2)
	
	tl.pencolor(255, 255, 255)
	tl.fillcolor(randint(0,255), randint(0,255), randint(0,255))
	
	
	
	if orientation == "bg" : 
		tl.setheading(90)
		tl.setposition(coinx * unite, coiny *unite)
	elif orientation == "hg" : 
		tl.setheading(0)
		tl.setposition(coinx * unite, (coiny+1) *unite)
	elif orientation == "bd" : 
		tl.setheading(180)
		tl.setposition((coinx+1) * unite, coiny *unite)
	else : 
		tl.setheading(-90)
		tl.setposition( (coinx+1) * unite, (coiny+1) *unite)
	
	tl.pendown()
	tl.begin_fill()
	tl.forward(cote)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.left(90)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.forward(cote)
	tl.end_fill()




def dessine_grille(n, cote = unite) :
	tl.pensize(1)
	tl.pencolor(100,100,100)
	
	tl.setheading(0)
	for i in range(n+1) :
		tl.penup()
		tl.setposition(0,i * cote)
		tl.pendown()
		for k in range(n) : tl.forward(cote)
		
	tl.setheading(90)
	for i in range(n+1) :
		tl.penup()
		tl.setposition(i * cote, 0)
		tl.pendown()
		for k in range(n) : tl.forward(cote)
		 
		
		
		
		
def dessine_pavage(echikier, cote = unite) :
	
	nbLignes = len(echikier)
	nbColonnes = len(echikier[0])
	
	for i in range(nbLignes) :
		for j in range(nbColonnes) :
			marque = echikier[i][j]
			if isinstance( marque, str) :
				dessine_trimino(marque[-2:], j, nbLignes -1 - i)
	
	
	

# échiquier :
k = 3
n = 2**k
# on dessine une grille :
dessine_grille(n, cote = unite)
# on définit un échiquier :
echiquier = definir_echiquier(k)
# on lance le calcul de son pavage par triminos :
pavons(echiquier)
# on affiche le résultat :
affiche_echiquier(echiquier)
dessine_pavage(echiquier) 
# fermeture de la fenêtre tortue par clic :
tl.exitonclick()

Dans cette seconde version, on trace les triminos au fur et à mesure du pavage afin de voir l'ordre dans lequel les triminos sont posés.

"""

On travaille avec un  échiquier 2^n sur 2^n.

Exemple d'échiquier 2^3 sur 2^3 avec les couples de coordonnées de chaque case :

|(lb, cb)  | (lb, cb+1) | (lb, cb+2) | (lb, cb+3) | (lb, cb+4) | (lb, cb+5) | (lb, cb+6) | (lb, cb+7) |
|(lb+1, cb)|(lb+1, cb+1)|(lb+1, cb+2)|(lb+1, cb+3)|(lb+1, cb+4)|(lb+1, cb+5)|(lb+1, cb+6)|(lb+1, cb+7)|
|(lb+2, cb)|(lb+2, cb+1)|(lb+2, cb+2)|(lb+2, cb+3)|(lb+2, cb+4)|(lb+2, cb+5)|(lb+2, cb+6)|(lb+2, cb+7)|
|(lb+3, cb)|(lb+3, cb+1)|(lb+3, cb+2)|(lb+3, cb+3)|(lb+3, cb+4)|(lb+3, cb+5)|(lb+3, cb+6)|(lb+3, cb+7)|
|(lb+4, cb)|(lb+4, cb+1)|(lb+4, cb+2)|(lb+4, cb+3)|(lb+4, cb+4)|(lb+4, cb+5)|(lb+4, cb+6)|(lb+4, cb+7)|
|(lb+5, cb)|(lb+5, cb+1)|(lb+5, cb+2)|(lb+5, cb+3)|(lb+5, cb+4)|(lb+5, cb+5)|(lb+5, cb+6)|(lb+5, cb+7)|
|(lb+6, cb)|(lb+6, cb+1)|(lb+6, cb+2)|(lb+6, cb+3)|(lb+6, cb+4)|(lb+6, cb+5)|(lb+6, cb+6)|(lb+6, cb+7)|
|(lb+7, cb)|(lb+7, cb+1)|(lb+7, cb+2)|(lb+7, cb+3)|(lb+7, cb+4)|(lb+7, cb+5)|(lb+7, cb+6)|(lb+7, cb+7)|


On note cote = 2^n

Les quatres cases centrales de l'échiquier 2^n sur 2^n ont pour coordonnées :

(lb + cote//2 - 1, cb + cote//2 -1 )  |  (lb + cote//2 - 1, cb + cote//2 + 0 )
-------------------------------------------------------------------------------
(lb + cote//2 + 0, cb + cote//2 -1 )  |  (lb + cote//2 + 0 , cb + cote//2 + 0 )



Au départ toutes les cases de l'échiquier sont à 0 sauf la case trouée.
Ensuite, une case porte le numéro du trimino placé dessus.

"""





from random import randint
import turtle as tl

# pour définir les couleurs tortue en rgb :
tl.colormode(255)
# on cache la tortue :
tl.hideturtle()
 

# on définit une unité pour les dessins :
unite = 20



def definir_echiquier(k) :
	"""
	définit un échiquier de taille 2^k sur 2^k
	avec un trou tiré au hasard
	"""
	n = 2**k
	echikier =  [[0 for j in range(n)] for i in range(n)]
	# on troue une case au hasard :
	echikier[randint(0,n-1)][randint(0,n-1)] = -1
	return echikier


def affiche_echiquier(echikier) :
	"""
	Fonction d'affichage de l'échiquier
	"""
	nbLignes = len(echikier)
	nbColonnes = len(echikier[0])
	for i in range(nbLignes) :
		for j in range(nbColonnes) :
			print(echikier[i][j], end="\t")
		print()




def reperetrou(echikier, lb, cb, cote):
	"""
	Dans le sous-echiquier de echikier
	de première case (en haut à gauche) de coordonnées (lb, cb) et de côté cote,
	on considère qu'il n'y a qu'une seule case non nulle,
	cette case peut alors être considérée comme un trou.

	On découpe ce sous-échiquer en 4 quarts et
	on retourne (-1,-1) pour un trou dans le quart haut gauche
	(-1, 0) pour un trou dans le quart haut droit
	(0,-1) pour un trou dans le quart bas gauche
	(0,0) pour un trou dans le quart bas droit
	"""
	lm = lb + cote//2
	cm = cb + cote//2
	for i in range(lb, lb+cote):
		for j in range(cb, cb+cote):
			if echikier[i][j] != 0 : return(-(i < lm),-(j < cm))


def triminoAuCentre(echikier, lb, cb, cote, numero) :
	"""
	Dans le sous-echiquier de echikier
	de première case  (en haut à gauche) de coordonnées  (lb, cb) et de côté cote,
	supposé n'avoir qu'un seul trou,  on place un trimino au centre.
	Ce trimino est placé de telle façon qu'il couvre une case exactement
	de chacun des quarts ne contenant pas le trou.

	Le trimino est représenté par un numéro (les trois cases recouvertes par ce
	trimino seront donc recouvertes par ce même numéro)
	"""
	
	nbLignes = len(echikier)
	lm = lb + cote//2
	cm = cb + cote//2
	(troux,trouy) = reperetrou(echikier, lb, cb, cote)

	for (x,y) in [(-1,-1), (-1,0), (0,0), (0,-1)] :
		if (x,y) != (troux,trouy) : echikier[lm+x][cm+y] = numero

	# on lance le dessin du trimino et on marque le numéro dans 
	# la grille echikier :

	if (troux,trouy) == (-1,-1) : 
		echikier[lm][cm] = str(echikier[lm][cm])
		dessine_trimino('bd', cm, nbLignes -1 - lm)
	if (troux,trouy) == (0,0) : 
		echikier[lm-1][cm-1] = str(echikier[lm-1][cm-1])
		dessine_trimino('hg', cm-1, nbLignes -1 - (lm-1))
	if (troux,trouy) == (-1,0) : 
		echikier[lm][cm-1] = str(echikier[lm][cm-1])
		dessine_trimino('bg', cm-1, nbLignes -1 - lm)
	if (troux,trouy) == (0,-1) : 
		echikier[lm-1][cm] = str(echikier[lm-1][cm])
		dessine_trimino('hd', cm, nbLignes -1 - (lm-1))
	
	


def pavons(echikier) :

	n = len(echikier)
	numero = 1

	def pave(lb=0, cb=0, cote=n) :
		nonlocal numero
		if cote > 1:
            # on place un trimino au centre :
			triminoAuCentre(echikier, lb, cb, cote, numero)
			numero += 1

			# couverture par appels récursifs des 4 quarts :
			demicote = cote//2
			for (x,y) in [(0,0),(0,demicote),(demicote,0),(demicote,demicote)]:
				pave(lb+x, cb+y, demicote)


	pave()







def dessine_trimino(orientation, coinx, coiny, cote = unite) :
	""" orientation : bg, bd, hg ou hd. """


	tl.penup()
	tl.pensize(2)

	tl.pencolor(255, 255, 255)
	tl.fillcolor(randint(0,255), randint(0,255), randint(0,255))



	if orientation == "bg" :
		tl.setheading(90)
		tl.setposition(coinx * unite, coiny *unite)
	elif orientation == "hg" :
		tl.setheading(0)
		tl.setposition(coinx * unite, (coiny+1) *unite)
	elif orientation == "bd" :
		tl.setheading(180)
		tl.setposition((coinx+1) * unite, coiny *unite)
	else :
		tl.setheading(-90)
		tl.setposition( (coinx+1) * unite, (coiny+1) *unite)

	tl.pendown()
	tl.begin_fill()
	tl.forward(cote)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.left(90)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.right(90)
	tl.forward(cote)
	tl.forward(cote)
	tl.end_fill()




def dessine_grille(n, cote = unite) :
	tl.pensize(1)
	tl.pencolor(100,100,100)

	tl.setheading(0)
	for i in range(n+1) :
		tl.penup()
		tl.setposition(0,i * cote)
		tl.pendown()
		for k in range(n) : tl.forward(cote)

	tl.setheading(90)
	for i in range(n+1) :
		tl.penup()
		tl.setposition(i * cote, 0)
		tl.pendown()
		for k in range(n) : tl.forward(cote)







# échiquier :
k = 3
n = 2**k
# on dessine une grille :
dessine_grille(n, cote = unite)
# on définit un échiquier :
echiquier = definir_echiquier(k)
# on lance le calcul de son pavage par triminos :
pavons(echiquier)
# on affiche le résultat :
affiche_echiquier(echiquier)
# fermeture de la fenêtre tortue par clic :
tl.exitonclick()