汉诺塔

汉诺塔是一个经典的数学游戏和递归算法的完美例子。你需要实现一个算法来自动解决汉诺塔问题。

游戏规则

• 有多根柱子（至少3根），所有圆盘最初都堆叠在第一根柱子上
• 圆盘按照从大到小的顺序堆叠，大的在下面，小的在上面
• 每次只能移动一个圆盘，且只能移动柱子顶部的圆盘
• 不能将大圆盘放在小圆盘上面
• 目标是将所有圆盘移动到最后一根柱子上，保持相同的大小顺序

算法分析

经典的三柱汉诺塔的递归解法是：

1. 将前 n-1 个圆盘从起始柱移动到辅助柱
2. 将最大的圆盘从起始柱移动到目标柱
3. 将 n-1 个圆盘从辅助柱移动到目标柱

这个解法能够解决三柱汉诺塔问题，同时也是移动步数最少的最优解。

游戏可以自定义柱子和圆盘的数量，如果设置柱子的数量 > 3，可以仅使用其中的三根柱子，转化为三柱汉诺塔问题求解。但是这样没有充分利用所有柱子，不是最优解。你可以探索一下，对于柱子数量 > 3 的情况如何得到步数最少的最优解。

你的任务

实现一个 solveHanoi 函数，通过操作 gameController 来自动解决汉诺塔问题。

输入

gameController 提供以下接口：

• getState(): 获取当前游戏状态

  • 返回一个二维数组，每个子数组代表一根柱子上的圆盘
  • 数组中的数字代表圆盘大小，1是最小的圆盘
  • 数组的最后一个元素是柱子顶部的圆盘

• move(from, to): 移动圆盘

  • from: 源柱子的索引 (0-based)
  • to: 目标柱子的索引 (0-based)
  • 将源柱子顶部的圆盘移动到目标柱子顶部
  • 如果移动无效（如将大盘放到小盘上），会抛出错误

示例

假设有3根柱子，3个圆盘：

// 初始状态：所有圆盘在第0根柱子上
gameController.getState() // [[3, 2, 1], [], []]

// 移动最小圆盘到第2根柱子
gameController.move(0, 2);
gameController.getState() // [[3, 2], [], [1]]

// 移动中等圆盘到第1根柱子
gameController.move(0, 1);
gameController.getState() // [[3], [2], [1]]

祝你好运！