Tour de Hanoi

La Tour de Hanoï est l'un des casse-têtes les plus célèbres jamais imaginés. Créé à la fin du XIXe siècle par le mathématicien français Édouard Lucas, peut-être inspiré d'une légende ancienne, son principe est simple :

une pile de disques, l'un plus grand que l'autre, repose sur une tige. L'objectif est de déplacer tous les disques d'une tige à une autre (il y a trois tiges au total). On ne peut déplacer qu'un seul disque à la fois, seuls les disques du haut d'une pile peuvent être déplacés, et seuls les disques plus petits que le disque le plus haut d'une pile peuvent être placés au sommet de cette pile.

Avec un seul disque, le jeu est simple : il suffit de le placer sur une autre tige en un seul coup. Avec deux disques, il faut au moins trois coups pour terminer la partie, tandis qu'avec trois disques, il faut au moins sept coups.

En général, le nombre minimum de coups requis pour gagner est de 2ⁿ — 1, où n est le nombre de disques de départ.

Le jeu TOWER.BAS vous permet de jouer avec jusqu'à huit disques. Vous serez confronté à la disposition des disques et des réglettes à l'écran et serez interrogé sur votre prochain coup, jusqu'à ce que, avec persévérance, stratégie et peut-être un peu de chance, vous parveniez à déplacer tous les disques sur une autre réglette.

Des tableaux multiples permettent de suivre la taille des disques – initialisés sur les lignes 50 à 70 et dessinés, selon leur taille, sur les lignes 150 à 210 (ce qui ajuste également leur position relative) – ainsi que leur position dans les piles au-dessus des trois réglettes.

De plus, plusieurs calculs – par exemple pour vérifier si les réglettes ne contiennent pas de disques ou si le joueur a gagné la partie – assurent le bon fonctionnement du jeu.

Graphiquement, le jeu n'est pas très intéressant. On ne voit qu'une perspective latérale, les disques étant dessinés comme de simples lignes.

Et lorsqu'un disque est déplacé, il est simplement « transporté » vers une autre pile (bien sûr, le plateau de jeu doit être entièrement redessiné à chaque déplacement). Ne serait-il pas plus intéressant de voir le disque déplacé se déplacer réellement, directement de la baguette vers une autre pile ?

De plus, il serait intéressant pour l'utilisateur de disposer d'une option de « jeu complet », où l'ordinateur effectuerait le nombre minimum de coups nécessaires pour gagner la partie avec n'importe quel nombre de disques de départ, en affichant le résultat de chaque coup à l'écran.

Et serait-il trop compliqué que l'algorithme soit récursif ?

Cela peut être beaucoup plus clair et plus court en utilisant des tableaux bidimensionnels au lieu de tout répéter trois fois avec 1, 2, 3 dans les noms de variables.

La première dimension est le numéro de la tige, la seconde est sa position sur la tige.

TOWER.BAS

10 KEY OFF:SCREEN 9:COLOR 15,1:CLS
20 PRINT,,"--- TOWER OF HANOI ---"
22 INPUT"How many disks (max - 8)";MAXDISKS
23 IF MAXDISKS<X OR MAXDISKS>8 THEN 22
30 DIM ROD1(MAXDISKS):DIM ROD2(MAXDISKS):DIM ROD3(MAXDISKS)
35 DIM TOPROD(2):DIM MOVEDISK(2):CURRMOVE=1
40 'Set up initial rod with MAXOISKS--smallest to largest disks --> first element to last element of ROD1 array
50 FOR A=1 TO MAXDISKS
60 ROD1(A)=10*A
70 NEXT A
100 'Set up game board
102 CLS
103 PRINT,,"--- TOWER OF HANOI ---"
105 PRINT,," Current Move: ";CURRMOVE
110 LINE (0,200)-(645,200),7:LINE (0,210)-(645, 210),7:PAINT(0,205),7,7
120 LINE (150,200)-(150,50),7:LINE (160,200)-(160,50),7:LINE (150,50)-(160,50),7:PAINT(155,100),7
130 LINE (300,200)-(300,50),7:LINE (310,200)-(310,50),7:LINE (300,50)-(310,50),7:PAINT(305,100),7
140 LINE (450,200)-(450,50),7:LINE (460,200)-(460,50),7:LINE (450,50)-(460,50),7:PAINT(455,100),7
150 'Place disks in current positions
155 INCREMENT=(200-50)/MAXDISKS:LEVEL=190
160 FOR A=MAXDISKS TO 1 STEP -1
170 IF ROD1(A)<>0 THEN LINE (155,LEVEL)-(155-ROD1(A),LEVEL),4:LINE (155,LEVEL)-(155+ROD1(A),LEVEL),4
180 IF ROD2(A)<>0 THEN LINE (305,LEVEL)-(305-ROD2(A),LEVEL),4:LINE (305,LEVEL)-(305+ROD2(A),LEVEL),4
190 IF ROD3(A)<>0 THEN LINE (455,LEVEL)-(455-ROD3(A),LEVEL),4:LINE (455,LEVEL)-(455+ROD3(A),LEVEL),4
200 LEVEL=LEVEL-INCREMENT
210 NEXT A
220 'Check to see if you win the game--will only need to check rod2 and rod3, since rodl is where all disks started at originally
225 WINSUM2=0:WINSUM3=0
230 FOR T=1 TO MAXDISKS
240 IF ROD2(T)<>0 THEN WINSUM2=WINSUM2+1
250 IF ROD3(T)<>0 THEN WTNSUM3=WINSUM3+1
260 NEXT T
270 IF WINSUM2=MAXDISKS OR WINSUM3=MAXDISKS THEN LOCATE 17,30:PRINT"YOU ARE A WINNER!!!!" ELSE GOTO 300
280 END
300 'Inputs for user moves
310 LOCATE 18,1:INPUT"Move top disk from which rod (1, 2, or 3)";MOVE
320 IF MOVE <1 OR MOVE >3 THEN 310
330 'Check to see if there are any disks on the rod that user wishes to take disks from
335 TEMPSUM=0
340 FOR B=1 TO MAXDISKS
350 IF MOVE=1 THEN TEMPSUM=TEMPSUM+ROD1(B)
360 IF MOVE=2 THEN TEMPSUM=TEMPSUM+ROD2(B)
370 IF MOVE=3 THEN TEMPSUM=TEMPSUM+ROD3(B)
380 NEXT B
390 IF TEMPSUM=0 THEN 310
400 LOCATE 19,1:INPUT"Which rod do you want to move this top disk to (1, 2, or 3)";NROD
405 IF NROD<1 OR NROD>3 THEN 400
410 IF NROD=MOVE THEN 400
420 'Check to see if move places a bigger disk on top of a smaller one, which is not permitted
430 'First, check the size of the top disk of each rod (if there are disks on the rod)
440 TOPROD(1)=0:TOPROD(2)=0
450 FOR T=1 TO MAXDISKS
460 IF NROD=1 AND ROD1(T)<>0 THEN TOPROD(1)=ROD1(T):TOPROD(2)=T:GOTO 500
470 IF NROD=2 AND ROD2(T)<>0 THEN TOPROD(1)=ROD2(T):TOPROD(2)=T:GOTO 500
480 IF NROD=3 AND ROD3(T)<>0 THEN TOPROD(1)=ROD3(T):TOPROD(2)=T:GOTO 500
490 NEXT T
495 TOPROD(2)=MAXDISKS+1 'Accounts for disk-to-rod with no elements
500 'Now, see if the disk the user wants to move is smaller than the top disk on the rod the user wishes to transfer the disk to
510 MOVEDISK(1)=0:MOVEDISK(2)=0
520 FOR T=1 TO MAXDISKS
530 IF MOVE=1 AND ROD1(T)<>0 THEN MOVEDISK(1)=ROD1(T):MOVEDISK(2)=T:GOTO 560
540 IF MOVE=2 AND ROD2(T)<>0 THEN MOVEDISK(1)=ROD2(T):MOVEDISK(2)=T:GOTO 560
550 IF MOVE=3 AND ROD3(T)<>0 THEN MOVEDISK(1)=ROD3(T):MOVEDISK(2)=T:GOTO 560
555 NEXT T
560 IF MOVEDISK(1)>=TOPROD(1) AND TOPROD(1)<>0 THEN 400
600 'Proceed to actually shift the disk to the new rod
605 'First, remove the disk to be moved from the ROD array
610 IF MOVE=1 THEN ROD1(MOVEDISK(2))=0
620 IF MOVE=2 THEN ROD2(MOVEDISK(2))=0
630 IF MOVE=3 THEN ROD3(MOVEDISK(2))=0
640 'Next, place the disk on top of the new rod
650 IF NROD=1 THEN ROD1(TOPROD(2)-1)=MOVEDISK(1)
660 IF NROD=2 THEN ROD2(TOPROD(2)-1)=MOVEDISK(1)
670 IF NROD=3 THEN ROD3(TOPROD(2)-1)=MOVEDISK(1)
800 CURRMOVE=CURRMOVE+1
900 GOTO 100