Probleme des huit dames

Soyez le premier à donner votre avis sur cette source.

Vue 6 364 fois - Téléchargée 232 fois

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/

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

Codes Sources

A voir également

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.