		Programmer un Casse-tte
		************************

	On est souvent bte face  un casse-tte pour lequel on ne trouve
pas de stratgie menant  la solution. Votre Atari est l dans un coin
avec toute sa puissance, il n'y a qu' lui demander!

Le fameux problme des huit reines
----------------------------------

	Comment placer huit reines sur un chiquier sans qu'aucune ne
puisse prendre l'autre? Un petit rappel n'est pas inutile: une reine peut
prendre en ligne, en colonne et en diagonale, ce  n'importe quelle
distance.  Pour finir, un chiquier comporte 8 lignes de 8 cases, ce qui
nous en donne 64.
	On peut toujours essayer sur un papier quadrill, et vas-y que je
gomme chaque fois que je veux dplacer une croix. Sur un vritable
chiquier, c'est le confort mais c'est encombrant. Le summun c'est un
Atari qui peut vous lister toutes les solutions. Car en fait, plus que de
rpondre au casse-tte, n'est-il pas tout aussi intressant de dcouvrir
qu'il n'y a qu'une seule solution? Ou que leur nombre est 64 (autant que
de cases!) ou qu'elles sont toutes symtriques?
	Fermez dfinitivement le clapet  celui qui a os vous dfier en
lui amenant plus que ce qu'il vous demandait.

Des structures de donnes
-------------------------
	La manire dont vous allez organiser vos donnes est primordiale.
Une bonne structure de donnes vous amne  un bon programme, facile 
modifier, facile  "penser".
	Quels types de variables choisir? Comment les organiser? Voici la
meilleure question  se poser ds le debut de votre criture. Si vous etes
capable de "penser" les actions du programme avec votre choix de donnees,
vous serez capable de programmer les instructions sans aucun problme.
	Alors, allons-y...

On dgrossit
------------
	Avec huit lignes et huit reines, on voit qu'il ne pourra y avoir
qu'une seule reine par ligne. Je n'ai pas besoin, dans ce cas, de
conserver la position en ligne de chaque reine: la reine 1 en ligne 1, la
reine 2 en ligne 2, etc...
	On conservera alors la position en colonne dans un tableau allant
de col(1)  col(8). Par exemple, si col(3)=7, c'est que la reine 3 se
trouve en troisime ligne et septime colonne. Il va de soi que si
col(n)=col(m) c'est que les deux reines sont sur la mme colonne et qu'il
me faut en dplacer une!

Les diagonales
--------------
	Les diagonales demandent un soupon de rflexion en plus. Un petit
souvenir de la classe de troisme avec ses quations de droites vous
rappelera que sur ce type de droite, soit la somme soit la diffrence des
coordonnes est constante. Par exemple, sur la grande diagonale ou les
cases ont le mme numero de ligne que de colonne (1;1 ou 2;2, etc...) on
remarque que la diffrence des deux donne toujours 0 (fatalement).
	Reportez vous aux figures 1 et 2 pour d'autres exemples.
	En bref, je peux associer  chaque diagonale une valeur unique, ce
qui me permet de les distinguer entre elles.
	Je cre alors deux tableaux supplmentaires diag1() et diag2()
allant de 1  8 et conservant, pour chaque reine, les identificateurs de
ses digonales additives et soustractives.

Le principe de recherche
------------------------
	Je vais placer la premire reine, puis la seconde  une position
o elle ne prend pas la premire. Ensuite, je place la troisime sur une
colonne o elle ne prend ni la premire, ni la seconde. Ainsi de suite.
	Il se peut qu'il n'y ait plus de place pour une reine, il faut
donc que je modifie la position des reines prcdentes. pour repartir d'un
meilleur pied.
	Des que huit sont places j'affiche la solution. Ds que le
programme me dit qu'il n'y a plus de place pour la reine 1 c'est qu'il a
explor toutes les possibilits.

Le programme principal
----------------------

	Aprs les dclarations des tableaux, je cre la variable sol qui
comptera le nombre de solutions trouves. La valeur n repre le numro de
la reine en cours de placement. Au dbut, elle vaut 1. Je mets galement 
zro son indice de colonne pour commencer en dbut de ligne.

DIM col(8)
DIM diag1(8)
DIM diag2(8)
sol=0
n=1
col(1)=0

	La procdure "place_reine" se charge de placer la reine numro n.
Si une place lui est trouve, ok=1. Sinon c'est un chec et il faut
dplacer l'une des reines prcdentes car la position actuelle mne  une
impasse.

autre:
GOSUB place_reine
IF ok=1		' c'est bon!
  IF n=8        ' et en plus j'en ai 8, on affiche
    INC sol
    PRINT "Solution ";sol
    FOR i=1 TO 8
      PRINT CHR$(i+64);col(i)
    NEXT i
    REPEAT
    UNTIL MOUSEK  ' et on attend un clic pour continuer
  ELSE
    n=n+1       ' c'est bon, mais pas encore huit, reine suivante
    col(n)=0    ' au dbut de sa ligne
  ENDIF
ELSE
  n=n-1         ' ok=0, plus de place, revenir  la reine prcdente
  IF n=0
    GOTO sortir ' arriv  0, tout est explor
  ENDIF
ENDIF
GOTO autre
sortir:
END

La procdure de placement
-------------------------

	Tout est bas sur la recherche de la colonne. Ds le dbut on
incrmente la position actuelle, c'est pour cette raison que j'initialise
les colonnes  zro, ainsi on commence bien  1.
	Si ma colonne passe  9, je dborde de l'chiquier et je renvoie
ok=0: plus de place. Sinon, je calcule les identificateurs de diagonales
et je m'assure que ma reine n'est ni si la mme colonne ni sur les memes
diagonales que les reines dj places. Si il s'agit de la premire reine,
ce test est bien sur saut.

PROCEDURE place_reine
  c=col(n)       ' colonne actuelle, ou zro
cherche:
  INC c          ' nouvelle colonne (on avance d'un cran)
  IF c=9         ' on dborde=plus de place.
    ok=0
    GOTO fin
  ELSE
    d1=c+n       ' sinon, on calcule les identifiants des colonnes
    d2=c-n
    ok=1         ' on suppose que a va marcher...
    IF n>1       ' si a n'est pas la premire reine...
      FOR i=1 TO n-1   ' on compare avec les positions prcdentes
        IF c=col(i) OR d1=diag1(i) OR d2=diag2(i)
          ok=0   ' zut!, on se fait prendre
        ENDIF
      NEXT i
    ENDIF
  ENDIF
  IF ok=0        ' apres les tests, OK vaut zero, il faut encore bouger
    GOTO cherche
  ENDIF
  col(n)=c       ' sinon, ma reine est bien place, on conserve
  diag1(n)=d1    ' ses valeurs de position
  diag2(n)=d2
fin:
RETURN

Amliorations possibles
-----------------------
	Il est vident que je ne manipule que des entiers de 1  8. Pour
des questions de vitesse, passer toutes les variables en entiers sera
apprciable.
	De mme, la valeur Ok n'est qu'un drapeau valant 0 ou 1. Une
valeur boolenne est aussi largement suffisante (en liaison avec TRUE et
FALSE).
	Au lieu d'afficher les solutions sous forme de coordonnes, vous
pouvez dessiner un joli chiquier.
	Finalement, une sortie sur imprimante ou dans un fichier viterait
d'attendre devant sa machine pour cliquer  chaque solution.

Conclusion
----------

	Il ne vous reste plus qu' taper et amliorer ce petit programme
pour connaitre la ou les solutions du problme des huit reines. J'espre
que ce sera un petit dpart vers d'autres applications d'intelligence
artificielle. Je vous livre ici quelques ides pour poursuivre:
	- le problme rciproque: combien suffit-il de reines pour bloquer
	tout un chiquier? (c'est moins de 8!).
	- un cheval sur un chiquier peut il atteindre les 64 cases sans
	jamais passer deux fois sur une case? Le point de dpart est
	laiss au choix.

	Sur ces bonnes choses, bons casse-ttes  tous,

	Guillaume Tello
	gtello@wanadoo.fr
