Probleme des huit dames
Description
consiste à placer 8 dames dans un échiquier de 8x8 cases de telle façon que jamais deux dames ne doivent avoir la même ligne , la même colonne ou appartient à la même diagonale
Pour plus d'informations sur l'algorithme utilisé : http://mehdi.cherti.name/algofacile/2010/01/06/probleme-des-huits-dames/
Pour plus d'informations sur l'algorithme utilisé : http://mehdi.cherti.name/algofacile/2010/01/06/probleme-des-huits-dames/
Source / Exemple :
import sys
# renvoie true si mettre une dame dans une case peut etre fait
def possible (N,choix,col , lig):
if col <= 1 : return True
coll = 1
for lastlig in choix:
if lastlig == lig : return False
if col + lig == lastlig + coll : return False
if col >= lig and coll >= lastlig and col - lig == coll - lastlig : return False
if col <= lig and coll <= lastlig and lig - col== lastlig- coll : return False
coll = coll + 1
return True
# affiche une chaine
def W(string):
sys.stdout.write (string)
# affiche l'echiquier
def show (choix):
N = len(choix)
for C in range(1,N+1):
for L in range(1,N+1):
if L == choix[C-1]:
W ('X')
else : W('#')
W(' ')
print
print
# retourne un tableau contenant tous les combinaisons possibles pour resoudre ce probleme pour N dames dans un echiquier de N*N
def dames(N,choix=[],col=1,num=0):
if col == N+1:
show(choix)
return 1
for lig in range(1,N+1):
if possible (N,choix,col , lig):
choix.append (lig)
num = num + dames (N , choix , col + 1)
choix.pop ()
return num
num=dames(8)
print num
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.