Sur un échiquier n sur n, une dame peut prendre les pions se trouvant sur sa ligne, sur sa colonne, sur ses diagonales.
La question : peut-on placer n dames sur un échiquier de façon à ce qu'aucune ne puisse être prise par une autre ?
Écrire une fonction python récursive pour la recherche des solutions.
- principe
- un code
Raisonnons sur un échiquier 8*8. Plaçons déjà la dame de la colonne 1. Elle peut être placée sur n'importe quelle ligne. Notons ['1', '2', '3', '4', '5', '6', '7', '8'] la liste des lignes sur lesquelles elle peut être placée.
Cherchons maintenant à placer une dame en colonne 2. Pour chaque emplacement possible de la dame de la colonne 1, on dresse la liste des emplacements possibles pour la dame de la colonne 2. Par exemple pour l'emplacement dame colonne 1 en ligne 1, la dame de la colonne 2 peut occuper toute ligne sauf les lignes 1 et 2.
| colonne 1 | colonne 2 | |
|---|---|---|
| ligne 1 | dame | non |
| ligne 2 | non | |
| ligne 3 | possible | |
| ligne 4 | possible | |
| ligne 5 | possible | |
| ligne 6 | possible | |
| ligne 7 | possible | |
| ligne 8 | possible |
Dans la liste des 'solutions' pour deux reines, nous aurons donc déjà '13', '14', '15', '16', '17', '18'.
Illustration pour le cas '13' (colonne 1 : dame en ligne 1; colonne 2 : dame en ligne 3) :
Lorsque la reine de la colonne 1 est en ligne 2, la reine de la colonne 2 peut se placer partout sauf sur les lignes 1, 2 ou 3.
| non | |
| R | non |
| non | |
| ok | |
| ok | |
| ok | |
| ok | |
| ok |
A la liste des solutions pour deux reines, on peut donc ajouter '24', '25', '26', '27', '28'. On poursuit ainsi pour chacune des positions possibles de la reine 1. On obtient la liste complète suivante : ['13', '14', '15', '16', '17', '18', '24', '25', '26', '27', '28', '31', '35', '36', '37', '38', '41', '42', '46', '47', '48', '51', '52', '53', '57', '58', '61', '62', '63', '64', '68', '71', '72', '73', '74', '75', '81', '82', '83', '84', '85', '86'].
Ayant obtenu la liste complète des solutions possibles pour les deux premières reines,
comment construire la liste pour les trois premières reines ?
Pour chacune des solutions pour les deux premières,
on teste chacune des lignes pour la reine de la colonne 3
et on ne retient que les positions telles que cette reine colonne 3
ne soit pas en prise avec les deux premières reines.
On obtient la liste suivante :
['135', '136', '137', '138', '142', '146', '147', '148', '152', '157', '158',
'162', '164', '168', '172', '174', '175', '182', '184', '185', '186', '241',
'246', '247', '248', '251', '253', '257', '258', '261', '263', '268', '271',
'273', '275', '281', '283', '285', '286', '314', '316', '317', '318', '352',
'357', '358', '362', '364', '368', '372', '374', '382', '384', '386', '413',
'415', '417', '418', '425', '427', '428', '461', '463', '468', '471', '473',
'475', '481', '483', '485', '514', '516', '518', '524', '526', '528', '531',
'536', '538', '571', '572', '574', '581', '582', '584', '586', '613', '615',
'617', '625', '627', '631', '635', '637', '641', '642', '647', '681', '682',
'683', '685', '713', '714', '716', '718', '724', '726', '728', '731', '736',
'738', '741', '742', '746', '748', '751', '752', '753', '758', '813', '814',
'815', '817', '824', '825', '827', '831', '835', '837', '841', '842', '847',
'851', '852', '853', '857', '861', '862', '863', '864'].
On a ainsi défini notre processus récursif.
Illustration du cas '752' :
# l'échiquier sera de taille au plus 9 sur 9 avec les choix faits ci-dessous.
# Remplacer les chaînes par des listes pour des tailles supérieures.
def validite(configuration) :
"""
configuration = '*254' signifie
dame colonne 1, ligne 2;
dame colonne 2, ligne 5;
dame colonne 3, ligne 4.
Retourne True si dames non en prise.
On teste seulement la dernière dame
par rapport aux précédentes.
L'étoile placée en début de configuration ne sert qu'à avoir
des indices de 1 à n correspondant à une
numérotation 'naturelle' des colonnes de 1 à n.
"""
# nb de dames dans la configuration testée :
n = len(configuration)-1
# ligne de la dame à tester, c'est à dire de la dernière dans la configuration :
ligneDame = int(configuration[-1])
# boucle vérifiant que la dernière dame de la configuration
# n'est pas en prise avec les précédentes :
for colonne, ligne in enumerate(configuration) :
if 0 < colonne < n :
ligne = int(ligne)
if ligne == ligneDame : return False
elif colonne + ligne == n + ligneDame : return False
elif colonne - ligne == n - ligneDame : return False
return True
def calculDesSolutions(n) :
""" Retourne la liste des solutions
pour un échiquier n*n."""
def resolution(n, colonne) :
"""
n : echiquier n*n.
colonne : numéro de la colonne où l'on cherche à placer une dame.
retourne la liste des emplacements possibles dans la
colonne colonne.
"""
if colonne == 1 :
return [str(i) for i in range(1,n+1)]
else :
S = []
for j in resolution(n, colonne-1) :
for k in range(1,n+1) :
if validite('*' + j + str(k)) : S.append(j + str(k))
return S
return resolution(n,n)
def afficher(une_solution, n) :
"""
Affichage d'une solution
pour un échiquier n*n.
La solution une_solution donnée en argument est sous la forme '*235...'
"""
print(' ',end=' ')
for k in range(1,n+1) : print(k,end='|')
print()
for l in range(1,n+1) :
print(l,end='|')
for c in range(1,n+1) :
if une_solution[c] == str(l) : print('R',end='|')
else : print(' ',end='|')
print()
# taille de l échiquier (maximum 9 avec nos choix) :
n = 8
# calcul de la liste des solutions :
S = calculDesSolutions(n)
# On affiche le nombre de solutions trouvées :
print("Le nombre de solutions : ", len(S), "\n")
# On affiche les solutions sous la forme de chaînes :
print(S,"\n")
# affichage du premier élément de la liste des solutions
# sous une forme plus visuelle :
afficher('*' + S[0], n)
On obtient :
Le nombre de solutions : 92 ['15863724', '16837425', '17468253', '17582463', '24683175', '25713864', '25741863', '26174835', '26831475', '27368514', '27581463', '28613574', '31758246', '35281746', '35286471', '35714286', '35841726', '36258174', '36271485', '36275184', '36418572', '36428571', '36814752', '36815724', '36824175', '37285146', '37286415', '38471625', '41582736', '41586372', '42586137', '42736815', '42736851', '42751863', '42857136', '42861357', '46152837', '46827135', '46831752', '47185263', '47382516', '47526138', '47531682', '48136275', '48157263', '48531726', '51468273', '51842736', '51863724', '52468317', '52473861', '52617483', '52814736', '53168247', '53172864', '53847162', '57138642', '57142863', '57248136', '57263148', '57263184', '57413862', '58413627', '58417263', '61528374', '62713584', '62714853', '63175824', '63184275', '63185247', '63571428', '63581427', '63724815', '63728514', '63741825', '64158273', '64285713', '64713528', '64718253', '68241753', '71386425', '72418536', '72631485', '73168524', '73825164', '74258136', '74286135', '75316824', '82417536', '82531746', '83162574', '84136275']
Affichage de la première solution obtenue (15863724) :
1|2|3|4|5|6|7|8| 1|R| | | | | | | | 2| | | | | | |R| | 3| | | | |R| | | | 4| | | | | | | |R| 5| |R| | | | | | | 6| | | |R| | | | | 7| | | | | |R| | | 8| | |R| | | | | |