Le problème des 8 dames

' ******************************************************************************
'
'                Le problème des huit dames
'
' ******************************************************************************

' Sur un échiquier 8 X 8, placer 8 dames telles qu'aucune ne puisse être prise
' par l'une des 7 autes c.a.d. telle qu'il y ait au plus une dame dans chaque
' ligne, dans chaque colonne et dans chaque diagonale.

' ******************************************************************************

' Les solutions sont affichées comme suit: 15863724
' Cette façon doit être interprétée ainsi

' Colonne i ..... 1 2 3 4 5 6 7 8
'                ---------------
' Ligne dame(i).. 1 5 8 6 3 7 2 4
'
' C.A.D une dame en ligne 1,colonne 1; une dame en ligne 5, colonne 2;
' une dame en ligne 8, colonne 3; une dame en ligne, 6 colonne 4; etc..

' ******************************************************************************
' Pour comprendre l'algorithme utilisé:

' Comment peut-on exprimer que les dames des colonnes i et j ne se menacent pas?
' Deux dames sont dans la même ligne si dame(i) = dame(j).
' Elles sont sur la même diagonale si la droite qui les joint a pour coefficient
' directeur +1 ou -1 c.a.d : (dame(i) - dame(j)) / (i-j) = + ou - 1
' c.a.d, comme i > j, abs(dame(i) - dame(j)) = i - j

' Ces 2 constatations simples mais géniales, donne le programme ultra bref qui
' règle un problème que même Gauss n'a pas su maîtriser entièrement!

' ******************************************************************************

dim i,j,k,dame(8),solution$
label deplacer_dame
memo 1  : full_space 1 : print_target_is 1
caption 0 , "        LE PROBLEME DES HUIT DAMES"+string$(50," ")+"PAR PAPYDALL"
width 0,900 : height 0, 600
top 1,10:left 1, 150 :width 1,612 : height 1, 500
font_bold 1 : font_color 1,255,0,0
print : print :print
print string$(35," ") + "!!!      VEUILLEZ PATIENTER,  JE CALCULE    !!!"

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  : ' verifier 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

    for k = 1 to 8 : solution$ = solution$ + str$(dame(k)) : next k
    solution$ = solution$ + string$(5," ")
    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
' **************** AFFICHAGE DE LA SOLUTION  **********************************
clear 1 : print : print
print "                                              Voici les solutions : " : print
print "        Par exemple la solution 15863724 est représentée par la permutation (1,5,8,6,3,7,2,4)"
print "        Cette façon d'afficher les résultats doit être interprétée comme suit :" : print
print "        Chaque élement de la permutation représente la ligne où une dame se trouve."
print "        Le rang de chaque élement représente la colonne." : print
print "        Dans l'exemple ci-haut, on a donc:" : print
print "            une  dame  dans  la  1ère  colonne,  1ère  ligne"
print "            une  dame  dans  la  2ème  colonne,  5ème  ligne"
print "            une  dame  dans  la  3ème  colonne,  8ème  ligne"
print "            une  dame  dans  la  4ème  colonne,  6ème  ligne"
print "            une  dame  dans  la  5ème  colonne,  3ème  ligne"
print "            une  dame  dans  la  6ème  colonne,  7ème  ligne"
print "            une  dame  dans  la  7ème  colonne,  2ème  ligne"
print "            une  dame  dans  la  8ème  colonne,  4ème  ligne" : print

font_color 1, 0,0,255

solution$ = string$(2, " ") + solution$

print : print : print solution$
print
print "              !!!  I L  Y  A    E  N    T  O  U  T    9 2    S  O  L  U  T  I  O  N  S  !!!"
end
' **********************************************************************

print "        est représentée par la permutation (1,5,8,6,3,7,2,4)" : print