起因

我在老家書房裏面隨便翻, 結果就翻出了一個九連環, 然後就玩了一下午…

思考問題

游戲講解

九連環的游戲目標是將九個環都從橫杠上取下, 由於其結構的特殊性, 只有第一個環可以自由地取下或放上, 其他所有的環都服從一個規律: 若要取下或放上第nn號, 則第n−1n-1號必須在橫杠上, 且n−1n-1號前面沒有在橫杠上的環.

那麽取下所有的環最少要幾步, 要怎麽取呢?

尋找規律 & 抽象建模

Step-1 枚舉

首先, 我先嘗試枚舉簡單的情況尋找規律. 根據直覺, 這種前後相關的問題一般都是遞歸問題, 所以我們先假設取下前nn環需要f(n)f(n)步.

接下來我們開始枚舉,

f(1)=1f(2)=2=1+f(1)f(3)=5=f(1)+1+f(1)+f(2)f(4)=10=f(2)+1+f(2)+f(3)...\begin{aligned} & f(1) = 1 \\ & f(2) = 2 = 1 + f(1) \\ & f(3) = 5 = f(1) + 1 + f(1) + f(2) \\ & f(4) = 10 = f(2) + 1 + f(2) + f(3) \\ & ... \end{aligned}

那麽似乎遞歸公式很明顯了, 就是:

f(n)=2f(n−2)+f(n−1)+1  (n>2)f(n) = 2f(n-2) + f(n-1) + 1\space\space (n > 2)

Step-2 求解遞歸問題

那麽我們的方程就是:

{f(1)=1f(2)=2f(n)=2f(n−2)+f(n−1)+1  (n>2)\begin{cases} f(1) = 1 \\ f(2) = 2 \\ f(n) = 2f(n-2) + f(n-1) + 1\space\space (n > 2) \end{cases}

對於這個遞歸方程的求解, 我們可以考慮構造等比. 例如:

f(n)=2f(n−2)+f(n−1)+1f(n)+f(n−1)+1=2[f(n−2)+f(n−1)+1]∴f(n)+f(n−1)+1f(n−1)+f(n−2)+1=2根據f(3)+f(2)+1=8即可確定公式:f(n)+f(n−1)+1=2n  (n>2)經驗證,n=2也符合.\begin{aligned} f(n) & = 2f(n-2) + f(n-1) + 1 \\ f(n) + f(n-1) + 1 & = 2[f(n-2) + f(n-1) + 1] \\ \therefore \frac{f(n) + f(n-1) + 1}{f(n-1) + f(n-2) + 1} & = 2 \\ \end{aligned} \\ 根據f(3)+f(2)+1 = 8 即可確定公式: \\ f(n) + f(n-1) + 1 = 2^n \space\space(n > 2) \\ 經驗證, n=2也符合.

Step-3 繼續求解

依據公式f(n)=2n−1−f(n−1)  (n≥2)f(n) = 2^n - 1 - f(n-1) \space\space(n \ge 2)可得:

f(n)=2n−1−[2n−1−1−f(n−2)]=(2n−2n−1)−1+1+[2n−2−1−f(n−3)]=(2n−2n−1+2n−2)−(1−1+1)−f(n−3)…=Sn−1−Tn−1+(−1)n−1f(1)\begin{aligned} f(n) & = 2^n - 1 - [2^{n-1} - 1 - f(n-2)] \\ & = (2^n - 2^{n-1}) - 1 + 1 + [2^{n-2} - 1 - f(n-3)] \\ & = (2^n - 2^{n-1} + 2^{n-2}) - (1 - 1 + 1) - f(n-3) \\ & \dots \\ & = S_{n-1} - T_{n-1} + (-1)^{n-1} f(1) \end{aligned}

其中, SnS_n是數列ai=(−12)i−12na_i = \left(-\frac{1}{2}\right)^{i-1} 2^n的前nn項和, TnT_n是數列bn=(−1)n−1b_n = (-1)^{n-1}的前nn項和.

不難求得:

Si=2n+1+(−1)i+1⋅2n−i+13Tn=1−(−1)n2f(1)=1\begin{aligned} & S_i = \frac{2^{n+1} + (-1)^{i+1} \cdot 2^{n-i+1}}{3} \\ & T_n = \frac{1-(-1)^n}{2} \\ & f(1) = 1 \end{aligned}

從而可得到最終的答案:

f(n)=2n+2−(−1)n−36f(n) = \frac{2^{n+2} - (-1)^n - 3}{6}

解決問題

那麽, 我們帶入公式得到九連環的解法次數:

f(9)=211+1−36=241f(9) = \frac{2^{11}+1-3}{6} = 241

演示程式

由於編寫倉促, 目前只寫了一個非常簡陋的demo, 放在倉庫

game.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import asyncio
from components import Stick, Ring, ScreenManager
import pygame

async def solve(manager: ScreenManager, stick: Stick, n):
    if manager.status.pause:
        return 
    if n == 0:
        manager.status.step += manager.status.sign
        if stick[0].on_stick:
            await stick[0].move_down(manager)
        else:
            await stick[0].move_up(manager)
        return 
    
    if not stick[n-1].on_stick:
        await solve(manager, stick, n-1)
    
    for i in range(n-2, -1, -1):
        if stick[i].on_stick:
            await solve(manager, stick, i)
    
    if stick[n].on_stick:
        await stick[n].move_down(manager)
    else:
        await stick[n].move_up(manager)

    manager.status.step += manager.status.sign
    manager.update()


async def main():
    screen = pygame.display.set_mode((800, 600), pygame.RESIZABLE)
    stick = Stick(300, 250)
    manager = ScreenManager(screen, stick, *stick.rings)


    # Enter the main loop
    running = True
    while running:
        # Handle the events
        for event in pygame.event.get():
            # If the user clicks the close button, exit the program
            if event.type == pygame.QUIT:
                running = False
            # If the user resizes the window, adjust the screen size
            elif event.type == pygame.VIDEORESIZE:
                screen = pygame.display.set_mode((event.w, event.h), pygame.RESIZABLE) 
        
        # Get the mouse button state and position
        mouse_pressed = pygame.mouse.get_pressed()
        mouse_pos = pygame.mouse.get_pos()
        # If the left mouse button is pressed and the mouse is over the ring
        if mouse_pressed[0]:
            manager.status.pause = False
        # If the right mouse button is pressed and the mouse is over the ring
        elif mouse_pressed[2]:
            manager.status.pause = True
        
        for i in range(8, 0, -1):
            async with asyncio.Lock() as lock:
                await solve(manager, stick, i)
                await asyncio.sleep(0.1)

        # Update and draw the screen
        manager.update()

asyncio.run(main())

# Quit pygame
pygame.quit()