FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC

Développement d'applications avec le langage Panoramic
 
AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  GroupesGroupes  Connexion  
Derniers sujets
» TourD Version 2
par Minibug Aujourd'hui à 1:50

» La métamatière et le peuple
par JL35 Hier à 21:18

» Capture d'une zone de l'écran total
par JL35 Hier à 18:41

» Logiciel de soutien scolaire en langues.
par Pedro Alvarez Hier à 11:49

» qui peut résoudre mon prb
par pascal10000 Jeu 16 Nov 2017 - 17:30

» évènements et objets système : listage automatique
par Jean Claude Jeu 16 Nov 2017 - 11:15

» Panoramic et la reconnaissance vocale.
par papydall Jeu 16 Nov 2017 - 3:45

» Bizzarerie dans Edge
par Marc 37 Mer 15 Nov 2017 - 17:45

» KGF_dll - nouvelles versions
par Klaus Mer 15 Nov 2017 - 2:08

» Analyser un code Panoramic
par JL35 Lun 13 Nov 2017 - 18:38

» Un bonjour en passant...
par Minibug Dim 12 Nov 2017 - 19:57

» mise a jour calculatrice
par joeeee2017 Dim 12 Nov 2017 - 4:20

» comment accèder à l'heure et à la date d'un fichier
par Klaus Sam 11 Nov 2017 - 0:53

» Compilateur FBPano
par Jicehel Mer 8 Nov 2017 - 15:22

» Mon adresse e-mail
par treehouse Mer 8 Nov 2017 - 14:36

Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Novembre 2017
LunMarMerJeuVenSamDim
  12345
6789101112
13141516171819
20212223242526
27282930   
CalendrierCalendrier

Partagez | 
 

  Le problème des huit dames

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet:  Le problème des huit dames   Ven 28 Juil 2017 - 14:05

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 !
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
Yannick

avatar

Nombre de messages : 7997
Age : 46
Localisation : Bretagne
Date d'inscription : 15/02/2010

MessageSujet: re   Ven 28 Juil 2017 - 15:56

cheers Bravo Papydall !
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Jicehel

avatar

Nombre de messages : 5859
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re:  Le problème des huit dames   Ven 28 Juil 2017 - 16:06

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)
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re:  Le problème des huit dames   Ven 28 Juil 2017 - 16:24

Merci les amis Yannick et Jicehel.
De tels retours, c’est bon pour le moral. Wink
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re:  Le problème des huit dames   Ven 28 Juil 2017 - 16:31

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

Spoiler:
 
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
JL35



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

MessageSujet: Re:  Le problème des huit dames   Ven 28 Juil 2017 - 16:54

8 dames ! quelle idée ! j'ai déjà bien assez de problèmes avec une seule !
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Yannick

avatar

Nombre de messages : 7997
Age : 46
Localisation : Bretagne
Date d'inscription : 15/02/2010

MessageSujet: re   Ven 28 Juil 2017 - 22:43

C' est même plus du courage, c' est de la témérité !
lol! lol! lol!
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re:  Le problème des huit dames   Sam 29 Juil 2017 - 3:44

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
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
jean_debord

avatar

Nombre de messages : 759
Age : 63
Localisation : Limoges
Date d'inscription : 21/09/2008

MessageSujet: Re:  Le problème des huit dames   Sam 29 Juil 2017 - 10:36

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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://www.unilim.fr/pages_perso/jean.debord/index.htm
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re:  Le problème des huit dames   Sam 29 Juil 2017 - 12:39

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 ============================================================================
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
Froggy One

avatar

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

MessageSujet: Re:   Lun 31 Juil 2017 - 11:10

Et en plus il y a la réf du bouquin ! Miam miam !! merci Papydall !!!
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://gaeldwest.wordpress.com
Contenu sponsorisé




MessageSujet: Re:  Le problème des huit dames   

Revenir en haut Aller en bas
 
 Le problème des huit dames
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC :: PANORAMIC :: Vos sources, vos utilitaires à partager-
Sauter vers: