[classic algorithm question-09] two color and three color Hanoi Tower

Welcome to the official account [the front end of Pinellia], reply [algorithm], get all kinds of algorithm information.

explain

The two-color Hanoi Tower and the three-color Hanoi tower are derived from the Hanoi Tower rules introduced earlier. The purpose of the two-color Hanoi tower is to move the ring position at the top left of the figure below to the ring position at the bottom right:

The three color Hanoi Tower moves the ring on the upper left of the figure below to the ring on the upper right:

solution

Whether it is the two-color Hanoi tower or the three-color Hanoi Tower, its solution concept is similar to that of the Hanoi Tower introduced before. It also uses recursive solution. However, the purpose of this recursive solution is different. Let's first look at the case of only two disks. This is very simple. Just move the yellow of the first column to the second column, and then the blue of the first column to the third column.
Next, in the case of four disks, you must first complete the movement from top left to bottom right in the figure below with recursion:

Next, don't worry about them at the bottom, because they are already positioned. Just deal with the upper two plates of the first column. What about the six disks? Same! First, you must complete the movement from top left to bottom right in the figure below with recursion:

Next, don't worry about them at the bottom, because they are already positioned. Just deal with the four plates on the first column, which is the same as the previous situation of only four plates. Next, you will know how to solve the problem. Whether it is eight plates or more than ten plates, you use this concept to solve the problem.
What about the three color Hanoi Tower? Similarly, to directly look at the nine disks, you must first complete the moving results in the figure below:

Next, the bottom two layers don't care about them, because they are already positioned. Just deal with the three plates on the first column.

Two color Hanoi Tower

```#include <stdio.h>

void hanoi(int disks, char source, char temp, char target) {
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks-1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks-1, temp, source, target);
}
}

void hanoi2colors(int disks) {
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
for(i = disks / 2; i > 1; i--) {
hanoi(i-1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
hanoi(i-1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
}
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
}

int main() {
int n;
printf("Please enter the number of disks:");
scanf("%d", &n);

hanoi2colors(n);

return 0;
}

```

Three color Hanoi Tower

```#include <stdio.h>

void hanoi(int disks, char source, char temp, char target) {
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks-1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks-1, temp, source, target);
}
}

void hanoi3colors(int disks) {
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
if(disks == 3) {
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, source);
printf("move disk from %c to %c\n", target, temp);;
}
else {
hanoi(disks/3-1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);

hanoi(disks/3-1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);

hanoi(disks/3-1, source, target, temp);
printf("move disk from %c to %c\n", target, source);
printf("move disk from %c to %c\n", target, source);

hanoi(disks/3-1, temp, source, target);
printf("move disk from %c to %c\n", source, temp);

for (i = disks / 3 - 1; i > 0; i--) {
if (i>1) {
hanoi(i-1, target, source, temp);
}
printf("move disk from %c to %c\n",target, source);
printf("move disk from %c to %c\n",target, source);
if (i>1) {
hanoi(i-1, temp, source, target);
}
printf("move disk from %c to %c\n", source, temp);
}
}
}

int main() {
int n;
printf("Please enter the number of disks:");
scanf("%d", &n);

hanoi3colors(n);
return 0;
}

```

Welcome to follow the column and keep updating!
Welcome to the official account below, [reply] [algorithm], get all kinds of algorithm.

Keywords: C Algorithm

Added by Carlo Gambino on Tue, 08 Mar 2022 02:26:36 +0200