Le problème des huit dames

Tout est dans le code, bien expliqué et documenté.
C'est à vous de commenter.

Code:: rem ============================================================================
rem Le problème des huit dames
rem Par Papydall
rem ============================================================================
rem Ref : le livre "Mathématiques et informatique" de Arthur Engel
rem adapté de l’allemand par Daniel REISZ.
rem ============================================================================
rem Sur un échiquier 8 X 8, placer 8 dames telles qu’aucune ne puisse être prise
rem par l’une des 7 autres c.à.d. telle qu’il y ait au plus une dame dans chaque
rem ligne, dans chaque colonne et dans chaque diagonale.
rem ============================================================================
rem Les solutions sont affichées comme suit : 15863724
rem Cette façon doit être interprétée ainsi :
rem Colonne i ..... 1 2 3 4 5 6 7 8
rem -----------------
rem Ligne dame(i)... 1 5 8 6 3 7 2 4
rem
rem une dame en ligne 1, colonne 1;
rem une dame en ligne 5, colonne 2;
rem une dame en ligne 8, colonne 3;
rem une dame en ligne,6 colonne 4; etc..
rem ============================================================================
rem Pour comprendre l’algorithme utilisé :
rem Comment peut-on exprimer que les dames des colonnes i et j ne se menacent pas?
rem Deux dames sont dans la même ligne si dame(i) = dame(j).
rem Elles sont sur la même diagonale si la droite qui les joint a pour coefficient
rem directeur +1 ou -1, c.a.d :
rem _____________________________________
rem | |
rem | (dame(i) - dame(j)) / (i-j) = ± 1 |
rem |_____________________________________|

rem C’est-à-dire, comme i > j,
rem _____________________________________
rem | |
rem | abs(dame(i) - dame(j)) = i - j |
rem |_____________________________________|

rem Ces 2 constatations simples mais géniales, donne le programme ultra bref qui
rem règle un problème que même Gauss n’a pas su maîtriser entièrement!
rem ============================================================================
rem Le programme montre qu’il y a 92 solutions distinctes.
rem Deux solutions sont équivalentes si elles se déduisent l’une de l’autre par
rem rotation ou par symétrie.
rem Le groupe des isométries du carré ayant 8 éléments, il en résulte que les
rem solutions se regroupent en pricipe par familles de 8 solutions équivalentes.
rem Ainsi les 8 solutions suivantes sont équivalentes :
rem __________________________________________
rem | |
rem | 15863724 82417536 57263148 36428571 |
rem | 42736851 63571428 84136275 17582463 |
rem |__________________________________________|
rem
rem On passe de la première à la seconde par une rotation de 90°.
rem Dans chaque colonne les deux solutions se déduisent l’une de l’autre par la
rem symétrie orthogonale d’axe vertical.
rem Il y a ainsi 12 familles de solutions, mais 12 * 8 = 96 et non 92 !!!
rem Cela résulte de la solution suivante qui n’a que 4 solutions équivalentes.
rem __________________________________________
rem | |
rem | 35281746 64718253 64718253 75281746 |
rem |__________________________________________|
rem
rem ============================================================================
rem Voici le code (ultra bref) en Basic du livre cité en réference :
rem __________________________________________________________________________________________________
rem | |
rem | 10 FOR I = 1 TO 8 |
rem | 20 D(I) = I |
rem | 30 FOR J = 1 TO I - 1 |
rem | 40 IF D(I) = D(J) OR ABS(D(I) - D(J)) = I - J THEN 90 |
rem | 50 NEXT J |
rem | 60 NEXT I |
rem | 70 PRINT D(1)*10^7 + D(2)*10^6 + D(3)*10^5 + D(4)*10^4 + D(5)*10^3 + D(6)*10^2 + D(7)*10 + D(8) |
rem | 80 I = I - 1 |
rem | 90 D(I) = D(I) + 1 |
rem | 100 IF D(I) <= 8 THEN 30 |
rem | 110 I = I - 1 |
rem | 120 IF I <> 0 THEN 90 |
rem | 130 END |
rem |__________________________________________________________________________________________________|

rem ============================================================================

Init()
Determiner_Les_Solutions()

end
rem ============================================================================
SUB Init()
   label clic
   dim dame(8), solution$, NbSolution, i, j, k
   width 0,900 : height 0, 700 : color 0,150,100,150
   left 0,(screen_x - width(0))/2 : top 0,(screen_y - height(0))/2
   caption 0 , string$(20," ") + "LE PROBLEME DES HUIT DAMES" + string$(50," ") + "PAR PAPYDALL"
   application_title string$(50," ") + "LE PROBLEME DE HUIT DAMES"
   shape 102 : shape_rectangle_rounded 102 : top 102, 10 : left 102,50
   width 102,200 : height 102,50
   alpha 103 : top 103,top(102) + 15 : left 103,left(102) + 4 : font_bold 103 : font_size 103,12
   font_name 103,"arial" : font_color 103,255,255,255 : caption 103,"Le problème de 8 Dames"
   shape 104 : shape_rectangle_rounded 104 : top 104, top(102) + 60 : left 104,left(102)
   width 104,200 : height 104,50
   alpha 105 : top 105,top(104) + 15 : left 105,left(104) + 20 : font_bold 105 : font_size 105,12
   font_name 105,"arial" : font_color 105,255,255,255 : caption 105," Nb Solutions : "
   shape 106 : shape_rectangle_rounded 106 : top 106, 150 : left 106,50
   width 106,200 : height 106,500
   shape 107 : shape_rectangle_rounded 107 : top 107, 50 : left 107,270
   width 107,600 : height 107,600 : display
   list 110 : top 110,top(106) + 20 : left 110,left(106) + 40 : width 110,120
   height 110, height(106)-50 : font_bold 110 : font_color 110,0,0,255 : font_size 110,12
   font_name 110,"arial" : on_click 110,clic
   check 120 : top 120,height(107)-20 : left 120,left(107)+50 : font_bold 120
   font_name 120,"arial" : font_color 120,255,255,0 : font_size 120,12 : width 120,300
   hide 120 : on_click 120,clic
   button 130 : top 130,height(107)-25 : left 130,left(107)+width(120)+80 : font_bold 130
   caption 130,"&Infos" : inactive 130 : on_click 130,clic
   button 140 : top 140,top(130) : left 140,left(130) + 100 : font_bold 140
   caption 140,"&Quitter" : inactive 140 : on_click 140,clic
   2d_flood 400,200,150,100,50
   Dessiner_Echiquier(50)

END_SUB
rem ============================================================================
Clic:
   select number_click
   case 110 : if checked(120) = 1 then Afficher_Solution()
   caption 120," Afficher cette solution : " + item_index$(110)
   case 120 : if checked(120) = 1 then Afficher_Solution() : else : Nettoyer_Echiquier()
   case 130 : Afficher_Les_Infos()
   case 140 : terminate
   end_select
return
rem ============================================================================
SUB Nettoyer_Echiquier()
   dim_local i,j,n
   for i = 1 to 8
   for j = 1 to 8
   n = (i-1) * 8 + j
   if odd(i) = 1
   if odd(j) = 1
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   else
   if odd(j) = 0
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   end_if
   next j
   next i
END_SUB
rem ============================================================================
SUB Afficher_Solution()
   dim_local ligne, colonne, numero, solution$, i
   Nettoyer_Echiquier()
   solution$ = trim$(item_index$(110)) : ' Rétirer les blancs
   for i = 1 to 8
   ligne = val(mid$(solution$,i,1)) : colonne = i
   numero = 8*(ligne-1) + colonne
   file_load numero,"dame.jpg" : stretch_on numero
   next i
END_SUB
rem ============================================================================
SUB Dessiner_Echiquier(cote)
   dim_local i,j,n
   for i = 1 to 8
   for j = 1 to 8
   n = (i-1) * 8 + j
   picture n : width n,cote : height n,cote
   top n,115 + (i-1) * (cote+2)
   left n,375 + (j-1) * (cote+2)
   if odd(i) = 1
   if odd(j) = 1
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   else
   if odd(j) = 0
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   end_if
   next j
   next i

END_SUB
rem ============================================================================
SUB Determiner_Les_Solutions()
   label deplacer_dame
   for i = 1 to 8 : ' placer les dames
   dame(i) = 1 : ' placer la ième dame dans la ligne 1
   while dame(i) <= 8 : ' placer_dame
   if i > 1
   for j = 1 to i-1 : ' vérifier si cette dame est libre de toute menace
   ' si elle est menacée, on va à deplacer_dame et
   ' la dame monte d'une case
   if dame(i) = dame(j) or abs(dame(i)-dame(j)) = (i-j) then goto deplacer_dame
   next j
   end_if
   next i
   solution$ = string$(3," ")
   for k = 1 to 8 : solution$ = solution$ + str$(dame(k)) : next k
   item_add 110,solution$
   NbSolution = NbSolution + 1 : caption 105,"Nb Solutions : " + str$(NbSolution)
   i = i-1
   deplacer_dame:
   repeat
   dame(i) = dame(i)+1 : ' la dame monte d'une case
   end_while : ' la dame est encore sur l'échiquier? si oui on revient à placer_dame
   i = i-1 : ' si non vérifier si une dame précédente existe
   ' si oui la faire avancer d'une case vers le haut
   until i = 0

   item_select 110,1
   caption 120," Afficher cette solution : " + item_index$(110)
   show 120 : active 130 : active 140
END_SUB
rem ============================================================================
SUB Afficher_Les_Infos()
   dim_local t$
   t$ = chr$(13)
   t$ = t$ + "Comment placer 8 reines sur un échiquier sans qu'aucune reine n'en menace une autre ?" + chr$(13)
   t$ = t$ + "Une reine menace toutes les pièces de l'échiquier qui sont situées :" + chr$(13)
   t$ = t$ + "sur la même ligne, sur la même colonne ou sur la même diagonale." + chr$(13)+chr$(13)
   t$ = t$ + string$(50," ") +"Interprétation de la solution" + chr$(13) + chr$(13)
   t$ = t$ + " Par exemple la solution 15863724 est représentée par la permutation (1,5,8,6,3,7,2,4) "+chr$(13)
   t$ = t$ + " Cette façon d'afficher les résultats doit être interprétée comme suit :" + chr$(13)
   t$ = t$ + " Chaque élement de la permutation représente la ligne où une dame se trouve." + chr$(13)
   t$ = t$ + " Le rang de chaque élement représente la colonne." + chr$(13)
   t$ = t$ + " Dans l'exemple ci-haut, on a donc:" + chr$(13)
   t$ = t$ + " une dame dans la 1ère colonne, 1ère ligne" + chr$(13)
   t$ = t$ + " une dame dans la 2ème colonne, 5ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 3ème colonne, 8ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 4ème colonne, 6ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 5ème colonne, 3ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 6ème colonne, 7ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 7ème colonne, 2ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 8ème colonne, 4ème ligne" + chr$(13)
   message t$
END_SUB
rem ============================================================================

Le programme utilise une image dame.jpg qui doit se trouver dans le même dossier que le programme.

Voici l'image en question

Click-droit sur l'image puis enregistrer l'image sous ...
Enregistrez-la sous dame.jpg

Pour afficher l'une des solutions, choisissez-la dans la LIST à gauche et cliquez sur le CHECK à la gauche de Infos.

Bon divertissement avec les dames !

Bravo Papydall !

Je sens qu'à un moment tu vas nous faire une compilation "Casses-tête en échecs" avec une série de casses tête avec des cavalières, des folles et autres dames Wink

En tous cas, tu tiens un bon filons et c'est toujours aussi bien programmé. (Je n'ai pas encore essayé celui là car je suis au boulot mais le source est propre comme toujours)

Merci les amis Yannick et Jicehel.
De tels retours, c’est bon pour le moral. Wink

Pour ceux qui n'ont pas encore testé, voila ce que vous risquer d'obtenir :

Spoiler:

Nombre de messages : 7095 Localisation : 77 Date d'inscription : 29/11/2007

8 dames ! quelle idée ! j'ai déjà bien assez de problèmes avec une seule !

C' est même plus du courage, c' est de la témérité !
lol!

J’ai modifié mon code : il est possible de choisir le nombre D des dames à placer sur un échiquier D x D.
Avec 4 <= D <=9
C’est dans SUB Init() en ligne 93.

Pour une, deux ou trois dames, il n’y a ni problème ni solution. Evil or Very Mad

Pour 4 dames : 2 solutions
Pour 5 dames : 10 solutions
Pour 6 dames : 4 solutions
Pour 7 dames : 40 solutions
Pour 8 dames : 92 solutions
Pour 9 dames : 352 solutions

Mon programme s’arrête à cette dimension.
Pour des valeurs supérieures, le temps de calcul explose très vite !
Pour 10 dames : 724 solutions
Pour 11 dames : 2680 solutions
Pour 12 dames : 14200 solutions

Voici le code modifié:

Code:: rem ============================================================================
rem Le problème des huit dames
rem Par Papydall
rem ============================================================================
rem Ref : le livre "Mathématiques et informatique" de Arthur Engel
rem adapté de l’allemand par Daniel REISZ.
rem ============================================================================
rem Sur un échiquier 8 X 8, placer 8 dames telles qu’aucune ne puisse être prise
rem par l’une des 7 autres c.à.d. telle qu’il y ait au plus une dame dans chaque
rem ligne, dans chaque colonne et dans chaque diagonale.
rem ============================================================================
rem Les solutions sont affichées comme suit : 15863724
rem Cette façon doit être interprétée ainsi :
rem Colonne i ..... 1 2 3 4 5 6 7 8
rem -----------------
rem Ligne dame(i)... 1 5 8 6 3 7 2 4
rem
rem une dame en ligne 1, colonne 1;
rem une dame en ligne 5, colonne 2;
rem une dame en ligne 8, colonne 3;
rem une dame en ligne,6 colonne 4; etc..
rem ============================================================================
rem Pour comprendre l’algorithme utilisé :
rem Comment peut-on exprimer que les dames des colonnes i et j ne se menacent pas?
rem Deux dames sont dans la même ligne si dame(i) = dame(j).
rem Elles sont sur la même diagonale si la droite qui les joint a pour coefficient
rem directeur +1 ou -1, c.a.d :
rem _____________________________________
rem | |
rem | (dame(i) - dame(j)) / (i-j) = ± 1 |
rem |_____________________________________|

rem C’est-à-dire, comme i > j,
rem _____________________________________
rem | |
rem | abs(dame(i) - dame(j)) = i - j |
rem |_____________________________________|

rem Ces 2 constatations simples mais géniales, donne le programme ultra bref qui
rem règle un problème que même Gauss n’a pas su maîtriser entièrement!
rem ============================================================================
rem Le programme montre qu’il y a 92 solutions distinctes.
rem Deux solutions sont équivalentes si elles se déduisent l’une de l’autre par
rem rotation ou par symétrie.
rem Le groupe des isométries du carré ayant 8 éléments, il en résulte que les
rem solutions se regroupent en pricipe par familles de 8 solutions équivalentes.
rem Ainsi les 8 solutions suivantes sont équivalentes :
rem __________________________________________
rem | |
rem | 15863724 82417536 57263148 36428571 |
rem | 42736851 63571428 84136275 17582463 |
rem |__________________________________________|
rem
rem On passe de la première à la seconde par une rotation de 90°.
rem Dans chaque colonne les deux solutions se déduisent l’une de l’autre par la
rem symétrie orthogonale d’axe vertical.
rem Il y a ainsi 12 familles de solutions, mais 12 * 8 = 96 et non 92 !!!
rem Cela résulte de la solution suivante qui n’a que 4 solutions équivalentes.
rem __________________________________________
rem | |
rem | 35281746 64718253 64718253 75281746 |
rem |__________________________________________|
rem
rem ============================================================================
rem Voici le code (ultra bref) en Basic du livre cité en réference :
rem __________________________________________________________________________________________________
rem | |
rem | 10 FOR I = 1 TO 8 |
rem | 20 D(I) = I |
rem | 30 FOR J = 1 TO I - 1 |
rem | 40 IF D(I) = D(J) OR ABS(D(I) - D(J)) = I - J THEN 90 |
rem | 50 NEXT J |
rem | 60 NEXT I |
rem | 70 PRINT D(1)*10^7 + D(2)*10^6 + D(3)*10^5 + D(4)*10^4 + D(5)*10^3 + D(6)*10^2 + D(7)*10 + D(8) |
rem | 80 I = I - 1 |
rem | 90 D(I) = D(I) + 1 |
rem | 100 IF D(I) <= 8 THEN 30 |
rem | 110 I = I - 1 |
rem | 120 IF I <> 0 THEN 90 |
rem | 130 END |
rem |__________________________________________________________________________________________________|

rem ============================================================================

Init()
Determiner_Les_Solutions()

end
rem ============================================================================
SUB Init()
   label clic
   dim d : d = 9 : ' 4 <= D <=9
   dim dame(d), solution$, NbSolution, i, j, k
   width 0,900 : height 0, 700 : color 0,150,100,150
   left 0,(screen_x - width(0))/2 : top 0,(screen_y - height(0))/2
   caption 0 , string$(20," ") + "LE PROBLEME DES " + str$(d) + " DAMES" + string$(50," ") + "PAR PAPYDALL"
   application_title string$(50," ") + "LE PROBLEME DES " + str$(d) + " DAMES"
   shape 102 : shape_rectangle_rounded 102 : top 102, 10 : left 102,50
   width 102,200 : height 102,50
   alpha 103 : top 103,top(102) + 15 : left 103,left(102) + 4 : font_bold 103 : font_size 103,12
   font_name 103,"arial" : font_color 103,255,255,255 : caption 103,"Le problème des " + str$(d) + " Dames"
   shape 104 : shape_rectangle_rounded 104 : top 104, top(102) + 60 : left 104,left(102)
   width 104,200 : height 104,50
   alpha 105 : top 105,top(104) + 15 : left 105,left(104) + 20 : font_bold 105 : font_size 105,12
   font_name 105,"arial" : font_color 105,255,255,255 : caption 105," Nb Solutions : "
   shape 106 : shape_rectangle_rounded 106 : top 106, 150 : left 106,50
   width 106,200 : height 106,500
   shape 107 : shape_rectangle_rounded 107 : top 107, 50 : left 107,270
   width 107,600 : height 107,600 : display
   list 110 : top 110,top(106) + 20 : left 110,left(106) + 40 : width 110,120
   height 110, height(106)-50 : font_bold 110 : font_color 110,0,0,255 : font_size 110,12
   font_name 110,"arial" : on_click 110,clic
   check 120 : top 120,height(107)-20 : left 120,left(107)+50 : font_bold 120
   font_name 120,"arial" : font_color 120,255,255,0 : font_size 120,12 : width 120,300
   hide 120 : on_click 120,clic
   button 130 : top 130,height(107)-25 : left 130,left(107)+width(120)+80 : font_bold 130
   caption 130,"&Infos" : inactive 130 : on_click 130,clic
   button 140 : top 140,top(130) : left 140,left(130) + 100 : font_bold 140
   caption 140,"&Quitter" : inactive 140 : on_click 140,clic
   2d_flood 400,200,150,100,50
   Dessiner_Echiquier(400/d)

END_SUB
rem ============================================================================
Clic:
   select number_click
   case 110 : if checked(120) = 1 then Afficher_Solution()
   caption 120," Afficher cette solution : " + item_index$(110)
   case 120 : if checked(120) = 1 then Afficher_Solution() : else : Nettoyer_Echiquier()
   case 130 : Afficher_Les_Infos()
   case 140 : terminate
   end_select
return
rem ============================================================================
SUB Nettoyer_Echiquier()
   dim_local i,j,n
   for i = 1 to d
   for j = 1 to d
   n = (i-1) * d + j
   if odd(i) = 1
   if odd(j) = 1
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   else
   if odd(j) = 0
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   end_if
   next j
   next i
END_SUB
rem ============================================================================
SUB Afficher_Solution()
   dim_local ligne, colonne, numero, solution$, i
   Nettoyer_Echiquier()
   solution$ = trim$(item_index$(110)) : ' Rétirer les blancs
   for i = 1 to d
   ligne = val(mid$(solution$,i,1)) : colonne = i
   numero = d*(ligne-1) + colonne
   file_load numero,"dame.jpg" : stretch_on numero
   next i
END_SUB
rem ============================================================================
SUB Dessiner_Echiquier(cote)
   dim_local i,j,n
   if d < 4 or d > 9
   message "La dimension de l'échiquier doit être comprise entre 4 et 9 inclus"
   terminate
   end_if
   for i = 1 to d
   for j = 1 to d
   n = (i-1) * d + j
   picture n : width n,cote : height n,cote
   top n,115 + (i-1) * (cote+2)
   left n,375 + (j-1) * (cote+2)
   if odd(i) = 1
   if odd(j) = 1
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   else
   if odd(j) = 0
   color n,200,100,50
   else
   color n,0,0,0
   end_if
   end_if
   next j
   next i

END_SUB
rem ============================================================================
SUB Determiner_Les_Solutions()
   label deplacer_dame
   for i = 1 to d : ' placer les dames
   dame(i) = 1 : ' placer la ième dame dans la ligne 1
   while dame(i) <= d : ' placer_dame
   if i > 1
   for j = 1 to i-1 : ' vérifier si cette dame est libre de toute menace
   ' si elle est menacée, on va à deplacer_dame et
   ' la dame monte d'une case
   if dame(i) = dame(j) or abs(dame(i)-dame(j)) = (i-j) then goto deplacer_dame
   next j
   end_if
   next i
   solution$ = string$(3," ")
   for k = 1 to d : solution$ = solution$ + str$(dame(k)) : next k
   item_add 110,solution$
   NbSolution = NbSolution + 1 : caption 105,"Nb Solutions : " + str$(NbSolution)
   i = i-1
   deplacer_dame:
   repeat
   dame(i) = dame(i)+1 : ' la dame monte d'une case
   end_while : ' la dame est encore sur l'échiquier? si oui on revient à placer_dame
   i = i-1 : ' si non vérifier si une dame précédente existe
   ' si oui la faire avancer d'une case vers le haut
   until i = 0

   item_select 110,1
   caption 120," Afficher cette solution : " + item_index$(110)
   show 120 : active 130 : active 140
END_SUB
rem ============================================================================
SUB Afficher_Les_Infos()
   dim_local t$
   t$ = chr$(13)
   t$ = t$ + "Comment placer d reines sur un échiquier sans qu'aucune reine n'en menace une autre ?" + chr$(13)
   t$ = t$ + "Une reine menace toutes les pièces de l'échiquier qui sont situées :" + chr$(13)
   t$ = t$ + "sur la même ligne, sur la même colonne ou sur la même diagonale." + chr$(13)+chr$(13)
   t$ = t$ + string$(50," ") +"Interprétation de la solution" + chr$(13) + chr$(13)
   t$ = t$ + " Par exemple la solution 15863724 est représentée par la permutation (1,5,8,6,3,7,2,4) "+chr$(13)
   t$ = t$ + " Cette façon d'afficher les résultats doit être interprétée comme suit :" + chr$(13)
   t$ = t$ + " Chaque élement de la permutation représente la ligne où une dame se trouve." + chr$(13)
   t$ = t$ + " Le rang de chaque élement représente la colonne." + chr$(13)
   t$ = t$ + " Dans l'exemple ci-haut, on a donc:" + chr$(13)
   t$ = t$ + " une dame dans la 1ère colonne, 1ère ligne" + chr$(13)
   t$ = t$ + " une dame dans la 2ème colonne, 5ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 3ème colonne, 8ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 4ème colonne, 6ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 5ème colonne, 3ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 6ème colonne, 7ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 7ème colonne, 2ème ligne" + chr$(13)
   t$ = t$ + " une dame dans la 8ème colonne, 4ème ligne" + chr$(13)
   message t$
END_SUB
rem ============================================================================

Avec 9 dames,

on obtient:

Morale de l'histoire : plus on a de queen

, plus on a des solutions cheers

Merci Papydall !

Encore une bonne idée d'adaptation pour FBPano Smile

J'ai commencé une version de l'échange de cavalières, en utilisant seulement les fonctions graphiques de FreeBASIC, comme je l'avais fait pour le jeu de la vie. Elle devrait figurer dans la prochaine mise à jour.

C’est bien Jean_Debord.
Pour une éventuelle adaptation pour FBPano, tu trouveras ci-dessous le code minimal qui affichera les solutions dans un objet LIST.
Les dimensions de l’échiquier (et par conséquent le nombre de dames à placer) peuvent être choisies entre 4 et … N
Attention :
Lorsque N augmente, le temps de calcul devient excessif.
Mais si on se contente d’une ou quelques solutions (pas toutes), on peut choisir N grand (mais pas trop), quitte à arrêter le programme par <ESC>.

A titre d’exemple, voici les premières solutions pour 16 dames, obtenues après plusieurs minutes de calcul, le programme ayant été arrêté par <ESC>:

Premières solutions pour 16 dames:

Code:: rem ============================================================================
rem Le problème de N dames sur un échiquier N x N ; N >= 4
rem ============================================================================
rem Ref : MATHEMATIQUE ET INFORMATIQUE par Arthur Engel
rem Algorithme d’Arthur Engel:
rem Au départ, on place une dame en (1,1) puis on tente d’en placer une dans la
rem colonne suivante en évitant de la mettre sur la même ligne et en utilisant
rem cette astuce superbe pour éviter la prise en diagonale :
rem la pente de la droite définie par d(i) et d(j) ne doit pas être 1 ou -1.
rem D’où le très court programme ci-dessous.
rem ============================================================================
' Pour 4 dames : 2 solutions
' Pour 5 dames : 10 solutions
' Pour 6 dames : 4 solutions
' Pour 7 dames : 40 solutions
' Pour 8 dames : 92 solutions
' Pour 9 dames : 352 solutions
' Pour 10 dames : 724 solutions
' Pour 11 dames : 2680 solutions
' Pour 12 dames : 14200 solutions
rem Lorsque N augmente, le temps de calcule explose rapidement !
rem ============================================================================
rem Les solutions sont représentées par des permutations.
rem Chaque élement de la permutation (représenté sur deux chiffres pour manipuler
rem les échiquiers dont la dimension est > 9) représente
rem la ligne où une dame se trouve.
rem Le rang de chaque élement représente la colonne.
rem Exemple :
rem La solution (01 05 08 06 03 07 02 04), est interprétée ainsi :
rem Une dame dans la 1ère colonne, 1ère ligne
rem Une dame dans la 2ème colonne, 5ème ligne
rem Une dame dans la 3ème colonne, 8ème ligne
rem Une dame dans la 4ème colonne, 6ème ligne
rem Une dame dans la 5ème colonne, 3ème ligne
rem Une dame dans la 6ème colonne, 7ème ligne
rem Une dame dans la 7ème colonne, 2ème ligne
rem Une dame dans la 8ème colonne, 4ème ligne"
rem ============================================================================
rem &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
rem ============================================================================
label cherche, decale
dim n : n = 8 : ' Essayer avec d'autres valeur >= 4
dim d(n),i,j,k,sol$,NbSol,zero$
list 10 : top 10,10 : left 10,100 : height 10,400 : width 10,300 : font_bold 10
caption 0,"Veuillez patienter ...."
FOR i = 1 TO n
   d(i) = 1
   cherche:
   if i > 1
   FOR j = 1 TO i - 1
   IF d(i) = d(j) OR ABS(d(i) - d(j)) = i - j then GOTO decale
   NEXT j
   end_if
   if scancode = 27 then end
NEXT i
for k = 1 to n : ' Formater la solution
   if d(k) < 10 then zero$ = "0" : else : zero$ = ""
   sol$ = sol$ + zero$ + str$(d(k)) + " "
next k
NbSol = NbSol + 1
caption 0,"Pour " + str$(n) + " dames : Nombre de solutions : " + str$(Nbsol)
item_add 10, sol$ : ' Ajouter la solution à la liste
sol$ = "" : display
i = i - 1
decale:
   d(i) = d(i) + 1
   IF d(i) <= n then GOTO cherche
   i = i - 1
   IF i <> 0 then GOTO decale
caption 0,caption$(0) + " ... Terminé"
END
rem ============================================================================

Nombre de messages : 586 Date d'inscription : 06/01/2012

Et en plus il y a la réf du bouquin ! Miam miam !! merci Papydall !!!

» Le problème des 8 dames
» Jeu de dames
» Le source d'un jeu de dames internationnales si ça interesse
» Les dames françaises - la table d'exercices
» Problème avec select case Probleme réglé merci