5 dames

On 24-12-2007, cf29 wrote

Le problème des 5 dames :

Il s'agit de contrôler toutes les case d'un échiquier avec 5 dames qui
ne s'attaquent pas entre elles. J'en ai réalisé un petit programme en
JavaScript à :
http://www.cf29.com/design/dame5.php

(il est différent du célèbre problème des 8 dames pour lequel j'ai
trouvé des solutions)

Je voudrais trouver toutes les solutions possibles. J'ai déjà fait une
grosse partie du travail en Python mais je n'arrive pas à finaliser.

Comment vous y prendriez-vous ?

Récursivement, pose de la première dame sur toutes les positions, puis
la seconde etc... Si la 5eme peut se poser ça fait une solution.

Tien ça me plait ça, je vais le faire on comparera

Voulez-vous voir le code

où ?

(bien commenté) que j'ai déjà réalisé et me
dire ce que je dois ajouter pour générer toutes les positions sous les
conditions définies ? Je suis bloqué après avoir obtenu la première
solution et ne sais pas comment lancer la fonction pour trouver la
suivante.

--
William Dodé - http://flibuste.net
Informaticien indépendant

On Dec 25, 7:28 pm, William Dode <w...@flibuste.net> wrote:

On 24-12-2007, cf29 wrote

Récursivement, pose de la première dame sur toutes les positions, puis
la seconde etc... Si la 5eme peut se poser ça fait une solution.

J'ai un peu honte de mon code car je crois que je m'y suis mal pris
dès le départ.
J'arrive en effet à générer la première solution de 5 dames mais ne
sais pas comment passer à la deuxième.
Je génère les positions des 5 dames d'un coup :-) Il faudrait donc
ajouter les dames une par une et non les 5 d'un coup., n'est-ce pas ?

Ce que je n'arrive pas à faire c'est ce problème de récursion, je ne
vois comment écrire la fonction.
Comment poser la 1e dame sur toutes les cases ?
Comment poser la 2e en pouvant inclure des conditions (rang, colonne,
diagonales différentes), j'ai déjà une fonction pour ça.
Etc...
En fait ça s'arrête quand il n'y a plus de place pour en mettre une
6e, c'est à dire que toutes les cases sont contrôlées et ça fait une
solution valide.

Je suis débutant en Python et je manque certainement de bases solides
mais je trouve ça très intéressant. J'ai peut-être choisi un probl ème
trop difficile à mon niveau.

Donc William si tu as trouvé un moyen de le faire, je suis très
intéressé.

On 25-12-2007, cf29 wrote:

On Dec 25, 7:28 pm, William Dode <w...@flibuste.net> wrote:

On 24-12-2007, cf29 wrote

Récursivement, pose de la première dame sur toutes les positions, puis
la seconde etc... Si la 5eme peut se poser ça fait une solution.

J'avais pas vu le fait que les dames doivent controler tout le damier.
Donc ce que j'ai fait c'est qu'une fois une solution trouvée où elles
sont posées et ne s'attaquent pas (place), je vérifie si elles
controlent tout (get_board). Si c'est le cas ça fait une solution.
Mais comme ça y a pas mal de solutions en double, donc je compare aux
solutions précédentes pour voir si elle n'a pas déjà été trouvée.

nb_cols = 8
nb_rows = 8
nb_dames = 5

dames = {}

import sets
soluces = sets.Set()

def get_board():
ch = []
for r in range(nb_rows):
for c in range(nb_rows):
dame = False
for d, (x,y) in dames.items():
if x == r and y == c:
ch.append(' O ')
dame = True
break
elif x == r or y ==c or abs(x-r) == abs(y-c):
ch.append(' * ')
dame = True
break
if not dame:
return None
ch.append('n')
ch = ''.join(ch)
return ch

def go():
for r in range(nb_rows):
for c in range(nb_cols):
place(0, r, c)

def place(num, row, col):
for d,(r,c) in dames.items():
if (r == row) or
(c == col) or
(abs(r-row) == abs(c-col)):
return
dames[num] = (row, col)
if num == nb_dames-1:
ch = get_board()
if ch and ch not in soluces:
soluces.add(ch)
print ch
print len(soluces)
# raw_input()
del dames[num]
return

for r in range(nb_rows):
for c in range(nb_cols):
place(num+1, r, c)

del dames[num]


if __name__ == '__main__':
go()

J'ai un peu honte de mon code car je crois que je m'y suis mal pris
dès le départ.

T'inquiète pas, les raisons d'avoir honte de son code sont tellement
nombreuses qu'il est rare d'y échaper !

la mon code est vraiment pas optimisé... est-il correct d'ailleur ? je
trouve 728 solutions.

J'arrive en effet à générer la première solution de 5 dames mais ne
sais pas comment passer à la deuxième.
Je génère les positions des 5 dames d'un coup :-) Il faudrait donc
ajouter les dames une par une et non les 5 d'un coup., n'est-ce pas ?

Ce que je n'arrive pas à faire c'est ce problème de récursion, je ne
vois comment écrire la fonction.

Le problème de la récursion c'est surtout de ne pas oublier de nettoyer
quand on sort si on utilise une variable globale (ici le dico dames)

Comment poser la 1e dame sur toutes les cases ?
Comment poser la 2e en pouvant inclure des conditions (rang, colonne,
diagonales différentes), j'ai déjà une fonction pour ça.
Etc...
En fait ça s'arrête quand il n'y a plus de place pour en mettre une
6e, c'est à dire que toutes les cases sont contrôlées et ça fait une
solution valide.

Je suis débutant en Python et je manque certainement de bases solides
mais je trouve ça très intéressant. J'ai peut-être choisi un problème
trop difficile à mon niveau.

C'est un bon exercice je trouve. Mais y a sûrement plusieurs moyens de
le résoudre, donc c'est pas parceque tu n'auras pas fait comme moi que
ce n'était pas une bonne solution.

Donc William si tu as trouvé un moyen de le faire, je suis très
intéressé.

Après, dans le genre, peut-être un poil plus simple y a le déplacement
des cavaliers pour remplir un damier

01 10 19 14 03
18 05 02 09 20
11 22 13 04 15
06 17 24 21 08
23 12 07 16 25

Et si tu veux vraiment persévérer j'ai un jeu de course de voiture
vectoriel du même genre que je n'arrive pas a optimiser...


--
William Dodé - http://flibuste.net
Informaticien indépendant

William Dode wrote:

la mon code est vraiment pas optimisé... est-il correct d'ailleur ? j e
trouve 728 solutions.

Je trouve aussi 728 solutions (si donc l'on compte comme distinctes des
solutions qui ne diffèrent que par une rotation ou une réflexion) ave c le code
suivant (bon, tiré par les cheveux pour le plaisir notamment d'écrire "for
placees[-1] in placees[-1] :":)

miss = lambda (r,c) : lambda (R,C) : R!=r and C!=c and R+C!=r+c a nd R-C!=r-c

def augmente(placees,positions) :
if len(placees)<5 :
placees.append(filter(placees[-1].__lt__,positions)
if placees else positions)
for placees[-1] in placees[-1] :
augmente(placees,filter(miss(placees[-1]),positions))
placees.pop()
elif not positions :
solutions.append(placees[:])

solutions = []
augmente([],[(R,C) for R in range(8) for C in range(8)])

Je trouve aussi 728 solutions (si donc l'on compte comme distinctes des
solutions qui ne diffèrent que par une rotation ou une réflexion) a vec
le code suivant

Et 91 solutions en ne retenant qu'une solution parmi toutes solutions
équivalentes par rotation ou réflexion, avec le code modifié ainsi :

miss = lambda (r,c) : lambda (R,C) : R!=r and C!=c and R+C!=r+c a nd R-C!=r-c

def augmente(placees,positions) :
if len(placees)<5 :
placees.append(filter(placees[-1].__lt__,positions)
if placees else positions)
for placees[-1] in placees[-1] :
augmente(placees,filter(miss(placees[-1]),positions))
placees.pop()
elif not positions :
solutions.add(tuple(min(symetries(placees))))

def reflexions(solution) :
yield sorted(solution)
yield sorted((C,R) for (R,C) in solution)

rot90 = lambda solution : sorted((7-C,R) for (R,C) in solution)

def symetries(solution) :
for S in reflexions(solution) :
yield S
S = rot90(S)
yield S
S = rot90(S)
yield S
yield rot90(S)

solutions = set()
augmente([],[(R,C) for R in range(8) for C in range(8)])

On Dec 26, 5:56 pm, Boris Borcic <bbor...@gmail.com> wrote:

         placees.append(filter(placees[-1].__lt__,positions)
                        if placees else positions)

Merci, ça a l'air intéressant mais Python n'est pas d'accord avec la
syntaxe !?

Il y a vraiment 728 solutions distinctes et 91 solutions uniques.
Vous pouvez les voir en avec le bouton "exemples" (la première
solution est choisie au hazard et une boucle les montre toutes.)
http://www.cf29.com/design/dame5.php

J'ai vu la solution des 8 dames (qui est un problème différent) en
Python à :
http://en.wikipedia.org/wiki/Eight_queens_puzzle_solutions

Elle est très courte et rapide, je me demande s'il n'est pas possible
de la modifier pour avoir un nombre de dames différent du nombre de
rangées et de s'arrêter à la sixième dame. Si il n'y a plus de cases
libres pour la sixième, ça signifie que les 5 d'avant constituent une
solution valide.

Dans un autre genre, j'ai commencé à écrire ce code et me demande si
j'ai pris la bonne piste. Je suis coincé au "générateur de positions".
C'est un brouillon mais j'apprécierais des commentaires.
-------
# put a queen q1 on every square of the first 4 rows (32 squares)

# r0: 0 1 2 3 4 5 6 7
# r1: 8 9 10 11 12 13 14 15
# r2: 16 17 18 19 20 21 22 23
# r3: 24 25 26 27 28 29 30 31
# r4: 32 33 34 35 36 37 38 39
# r5: 40 41 42 43 44 45 46 47
# r6: 48 49 50 51 52 53 54 55
# r7: 56 57 58 59 60 61 62 63

# for each q1 add a second queen q2
# on a safe square on the next 3 rows range(8,32)

# starting

board = [] # squares list
nbRows = 8 # number of rows
nbCols = 8 # number of columns

# create 64 squares defined by their row, column
# ie the 1st square board[0] is [0,0], the last one board[63] is [7,7]
for r in range(nbRows):
for c in range(nbCols):
board.append([r,c])

# returns the row of a square board[sq]
def sqRow(sq):
return board[sq][0]

# returns the col of a square board[sq]
def sqCol(sq):
return board[sq][1]

# returns the diag1 of a square board[sq]
def sqDiag1(sq):
return sqRow(sq) + sqCol(sq)

# returns the diag2 of a square board[sq]
def sqDiag2(sq):
return sqRow(sq) - sqCol(sq)


# safe queen
def safeQueen(new,old):
if (sqRow(new) == sqRow(old) or
sqCol(new) == sqCol(old) or
sqDiag1(new) == sqDiag1(old) or
sqDiag2(new) == sqDiag2(old)):
return 0
else:
return 1
#
#
#
# testing (en travaux)
# loop
solutions = []
sol = []

# queen 1
for i1 in range(32):
sol.append([i1])
solutions.append([sol[i1]])
# queen 2
# for i2 in range(len(solutions)):
# solutions[i2].append("a")


for jj in solutions:
print jj

#
#
#
# this may be usefull
M = 3 # 3 numbers
N = 4 # in a list of 4 [0,1,2,3]
LST = range(N)

def process(data, elements):
if elements == 1:
return [[d] for d in data]
else:
results = []
for pos, itm in enumerate(data):
nest = data[:pos] + data[pos + 1:]
tmp = process(nest, elements - 1)
for part in tmp:
candidate = [itm]
candidate.extend(part)
candidate.sort()
if candidate not in results:
results.append(candidate)
return results

import pprint
pprint.pprint(process(LST, M))
-------------
------

cf29 wrote:

On Dec 26, 5:56 pm, Boris Borcic <bbor...@gmail.com> wrote:

placees.append(filter(placees[-1].__lt__,positions)
if placees else positions)

Merci, ça a l'air intéressant mais Python n'est pas d'accord avec l a
syntaxe !?

Je sais que c'est tardif, mais la réponse est que c'est du python 2.5 q ui admet
qu'une expression prenne la forme

(<expression-si-vrai> if <expression-test> else <expression-si-faux>)

ça ne marche pas avec les versions antérieures

B

Oui.