Циклическая (однонаправленная) Ханойская башня Предложения?

Question

Вот код Python, который я написал для задачи о Ханойской башне, где башня должна быть перенесена с левого колышка на средний, используя правый колышек в качестве запасного:

def hanoi(n, origin = "1", destination = "2", spare = "3"):

    if n == 1:
        print ("Move disk from", origin, "to", destination)

    else:
        hanoi(n-1, origin, spare, destination)
        hanoi(1, origin, destination, spare)
        hanoi(n-1, spare, destination, origin)

hanoi(3)

Теперь мой профессор хочет, чтобы я реализовал его так, чтобы законные перемещения были только с башни 1 к 2, башни 2 к 3 и башни 3 к 1. Все остальные правила одинаковы.

Answer 1

Как всегда с этой проблемой, нужно мыслить индуктивно. Начните с наименьшей из возможных башен для перемещения, затем спросите себя: если я могу это сделать, как я могу переместить большую башню?

Поскольку перемещение башни первого размера тривиально, начнем с башни второго размера:

Базовый вариант

Перемещение башни размера два на один колышек вправо:

|  -  |     |     |
| --- |     |     |
-------------------
Step 1:

|     |     |     |   
| --- |  -  |     |
-------------------
Step 2:

|     |     |     |
| --- |     |  -  |
-------------------
Step 3:

|     |     |     |
|     | --- |  -  |
-------------------
Step 4:

|     |     |     |
|  -  | --- |     |
-------------------
Step 5:

|     |  -  |     |
|     | --- |     |
-------------------

Это демонстрирует, как вы можете переместить башню на один колышек вправо. Конечно, это также может быть использовано для перемещения башни со второго на третий или с третьего на первый колышек.

шаг

Допустим, вы знаете, как переместить башню размером n на один колышек вправо, вот как вы делаете это для n + 1 дисков:

|    -    |         |         | Move the small tower one peg to the right
|   ---   |         |         |
|  -----  |         |         |
| ------- |         |         |
-------------------------------
Step 1:

|         |         |         | Move it another step to the right
|         |    -    |         |
|         |   ---   |         |
| ------- |  -----  |         |
-------------------------------
Step 2:

|         |         |         | Let's move the n+1 disk one peg to the right
|         |         |    -    |
|         |         |   ---   |
| ------- |         |  -----  |
-------------------------------
Step 3:

|         |         |         | Move the small tower to the right
|         |         |    -    |
|         |         |   ---   |
|         | ------- |  -----  |
-------------------------------
Step 4: 

|         |         |         | Move the small tower another peg to the right
|    -    |         |         |
|   ---   |         |         |
|  -----  | ------- |         |
-------------------------------
Final step:

|         |    -    |         | 
|         |   ---   |         |
|         |  -----  |         |
|         | ------- |         |
-------------------------------