Python en mathématiques - Défis

Rallye 2010 - Exercice 5

Boule lyonnaise

Énoncé original

Dix-huit personnes se sont inscrites à un concours de boule lyonnaise. Un numéro différent, compris entre 1 et 18 a été attribué à chacune d’entre elles.

Neuf équipes de deux se sont formées et, chose extraordinaire, pour chaque équipe, la somme des deux numéros est le carré d’un nombre entier.

Reconstituer les neuf équipes.

Exercice

Résoudre ce problème avec un programme python.

  • Un code possible
  • Avec 24 personnes

"""
Dans les matrices utilisées ci-dessous (liste de listes)
les éléments d'indice 0 ne sont pas utilisés afin
que les numéros de lignes et colonnes 
correspondent aux numéros des boules (de 1 à 18).
"""

from copy import deepcopy
N = 18 # nombre de boules


def estCarre(n):
	""" 
	n est un entier naturel.
	La fonction retourne True si n est le carré d'un entier 
	et False sinon.
	"""
	for i in range(n+1):
		if i*i == n : return True
	return False
	
	
def raz_ligne(matrice, lig):
	"""
	Remet à 0 tous les coefficients dans la ligne numéro lig 
	de matrice.
	"""
	for j in range(1,N+1):
		matrice[lig][j] = 0

	
def afficher(matrice):
	"""
	Affiche la matrice, ligne par ligne
	"""
	for i in range(1,N+1):
		for j  in range(1,N+1):
			print(matrice[i][j], end=' ')
		print()
	print()
	
	
def sommeLigne(matrice, lig):
	"""
	La fonction renvoie la somme des éléments de la ligne lig de matrice
	"""
	s = 0
	for col in range(1,N+1):
		s += matrice[lig][col]
	return s
	
def sommeColonne(matrice, col):
	"""
	La fonction renvoie la somme des éléments de la colonne col de matrice
	"""
	s = 0
	for lig in range(1,N+1):
		s += matrice[lig][col]
	return s	
 
 

			
 
 



def calculDesSolutions():
	
	# On définit la matrice des couples possibles a priori
	# il s'agit d'un tableau à double entrées.
	# On initialise avec des 0 partout.
	# Puis on pose des 1 :
	# si i+j est un carré alors le coefficient (i,j)
	# et le coefficient (j,i) ont pour valeur 1.
	# (les coefficients (i,i) restent nuls)
	matriceCouplesPossibles = [ [0 for j in range(N+1)] for i in range(N+1) ]
	for i in range(1,N+1):
		for j  in range(1,N+1):
			if estCarre( i+j ) and i != j :
				matriceCouplesPossibles[i][j] = 1
				
				
	# pour enregistrer les couplages possibles :
	Solutions = []	



	def couplage( matrice, ligne = 1):
		"""
		détermine les couplages possibles par backtrack.
		Pour cela, place un 1 en ligne 1.
		Puis en ligne 2 place un 1 dans une autre colonne.
		Puis en ligne 3 place un 1 dans une colonne non occupée...
		"""
		M = deepcopy(matrice)
		if ligne == N+1:
			Solutions.append(M)
		else :
			for col in range(1,N+1):
				raz_ligne(M, ligne)
				if matriceCouplesPossibles[ligne][col] == 1 and sommeColonne(M, col) < 1 and sommeLigne(M, ligne) < 1:
					M[ligne][col] = 1
					M[col][ligne] = 1
					couplage( M, ligne + 1)
		
	couplage([ [0 for j in range(N+1)] for i in range(N+1) ])
	return Solutions
		
		
		
Sol = calculDesSolutions()
print("Nombre de solutions : ", len(Sol) )
# Affichage  d'une solution : 
if len(Sol) > 0 : 
	couples = Sol[0]
	for lig in range(1,N//2+1):
		for col in range(1,N+1):
			if couples[lig][col] == 1:
				print( lig, col)

On obtient :

Nombre de solutions :  1
1 15
2 14
3 13
4 12
5 11
6 10
7 18
8 17
9 16

On peut essayer d'autres valeurs pour le nombre N de personnes.

Par exemple avec N = 24, on obtient une solution, toutes les sommes sont égales à 25 :

Nombre de solutions :  1
1 24
2 23
3 22
4 21
5 20
6 19
7 18
8 17
9 16
10 15
11 14
12 13