汉诺塔（Tower of Hanoi），别名河内塔，是起源于印度古老传说的益智玩具。传说在世界中心瓦拉纳西（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界时，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。
玩家可以将汉诺塔的三根柱子设置为编号A、B、C，每次只能移动一个积木，并且在移动的过程中三根柱子上始终保持最大的积木在最下面，最小的积木在最上面。在操作过程中可以将积木置于A、B、C任意一根柱子上，最后通过反复移动将积木从一根柱子移动到另一个柱子上。
汉诺塔这一玩具是认知心理学研究人类高级认知功能所广泛采用的一种方式。研究表明，计划能力和空间记忆能力是完成汉诺塔所必需的能力。汉诺塔的完成成绩通常是用来分析人类执行功能的一个重要指标。
传说起源
汉诺塔起源于印度的一则古老传说。法国数学家爱德华·卢卡斯曾编写过一个印度的传说。在世界中心贝拿勒斯（传说在印度北部）的圣庙里，有一块插着三根宝石针的黄铜板。印度教的主神梵天在创造世界时，从下到上地在一根宝石针上串上了由大到小的64片金片，这就是汉诺塔的雏形。不论何时，圣庙里总有一名僧侣在按照一次只能移动一片金片，每根宝石针上大的金片一定在小的金片下面这些规则移动金片。僧侣们预言，当所有的金片从梵天一开始串着的宝石针移动到另一根宝石针上时，世界将在一声霹雳中毁灭。
数学家们根据传说进行计算，发现如果按照僧侣的规则移动金片，一共需要移动2^64-1次，即18446744073709551615次。假如每秒钟移动1次金片，则需要5845.42亿年才能完成。
关于汉诺塔的来源还有另外一则传说。相传国际象棋的发明者是古印度舍罕王的宰相西萨·班·达依尔。舍罕王很喜欢国际象棋，便让达依尔自己决定想要什么奖赏。达依尔指着8*8共64格的国际象棋棋盘说，请舍罕王赏赐他一些麦子，就在棋盘第1格中放1粒，第2格中放2粒，第3格中放4粒，后面每一格放的麦子都要比前一格的麦子多一倍，就这样放满64格。舍罕王听后便让人扛来一袋麦子准备实现达依尔的愿望，可放到第20格时，一袋麦子就空了。随着一袋又一袋的麦子被放空，而棋盘上的格子还剩着许多，舍罕王终于明白，即使拿来全印度的小麦，他也不能实现达依尔的愿望。
按照达依尔宰相的愿望，他希望得到的赏赐是18446744073709511615粒麦子。经过计算，这是全世界在2000年内所生产的所有小麦。
玩法规则
游戏规则
将汉诺塔的三根柱子设置为编号A、B、C，每次只能移动一个积木，并且在移动的过程中三根柱子上始终保持最大的积木在最下面，最小的积木在最上面。在操作过程中可以将积木置于A、B、C任意一根柱子上，最后通过反复移动将积木从一根柱子移动到另一个柱子上。
在移动积木的时候也要遵守两个原则：（1）不能将大积木叠放在小积木上；（2）不能同时移动多个积木。
玩具变体
在三柱汉诺塔的基础上，通过增加一根柱子使其变为四柱，即为四柱汉诺塔。虽然四柱汉诺塔只比三柱汉诺塔多一根柱子，但是其难度远大于三柱汉诺塔。
数学解读
令三根柱子分别为A、B、C。一开始盘子在A柱上，且令盘子数为1到n=64（n是问题空间大小）
如果只有一个盘子，那么仅需一步就可以移动到另一根柱子上。令T(n)为将n个盘子从柱子A移动到另一根柱子所需的单个盘子移动（步数）的（最小）数量。那么T(1)=1。
如果有两个盘子，那么第一步必须将盘子1从柱子A移动到柱子B，然后将盘子2从柱子A移动到柱子C，最后将盘子1从柱子B移动到柱子C。所以，T(2)=3。
如果柱子A上有k个盘子。移动盘子k时，必须先把盘子k上面的（k-1）个盘子从柱子A移动到另一个柱子（该柱子上没有小盘子）。因此，将k个盘子从柱子A移出，必须：1.将上面（k-1）个盘子从柱子A移动到柱子B（或柱子C）；2.将盘子k从柱子A移动到柱子C(或柱子B）；3.将（k-1）个盘子从柱子B（或柱子C）移动到柱子C(或柱子A）。如果移动足够高效，则T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1。当n≥1且初始值T(1)=1时，可得所有情况下T(n)=2^n-1。
程序算法
Python算法
令三根柱子分别为a、b、c，a是起始柱，b是中转柱，c是目标柱。当n=1时（n是金盘数），只需将大盘从a柱移动到c柱；当n=2时，需要将小盘先移动到b柱上，再将大盘移动到c柱上，最后将b柱上的小盘移动到c柱的大盘上；当n=3时，需要将前两个小盘移动到b柱上，然后将大盘移动到c柱上，最后把b柱的小盘都移动到c柱的大盘上。因此当存在n个金盘时，只需要将n-1个小盘从a柱移动到b柱上，然后将大盘从a柱移动到c柱上，最后把b柱上的n-1个小盘都移动到c柱上。按照这个步骤，就可以移动n-2个小盘，再移动n-3个小盘，再移动n-4个小盘，一直到n-(n-1)个小盘，即递归思想。
代码参考资料：
C语言算法
令三根柱子分别为a、b、c，n是圆盘数量。采用数学归纳法来分析，将上面的n-1个圆盘看成一个整体，即将n个圆盘分为两个部分：上面的n-1个圆盘和最下面的第n号圆盘。因此可将移动n个圆盘的汉诺塔问题简化为：先将前n-1个圆盘从a柱移动到c柱上，再将第n号圆盘从a柱移动到b柱上，最后将前n-1个圆盘从c柱移动到b柱上。
代码参考资料：
C++语言算法
令三根柱子分别为x、y、z。Towers Of Hanoi(n)是递归函数Hanoi::Towers Of Hanoi的预处理程序，预处理程序创建三个堆栈S[1:3]用来储存3座塔的状态。所有的盘子从1（最小盘子）到n（最大盘子）编号，因此每个堆栈的类型都是int。如果没有足够的空间来创建三个堆栈，堆栈构造函数将引发一个类型为NoMem的异常，预处理程序将终止。如果留有足够的空间，预处理程序将调用Hanoi::Towers Of Hanoi。
代码参考资料：
Java语言算法
令三根柱子分别为A、B、C，n为圆盘数量，定义初始塔为fromTower，辅助塔为auxTower，目标塔为toTower。此方法借助于辅助塔auxTower将n个盘子从初始塔fromTower移动到目标塔toTower上：void moveDisks(int n，char fromTower，char toTower，char auxTower)。
代码参考资料：
非递归算法
解决汉诺塔问题时，也可以改变传统的圆盘编码从上到下、由小到大的顺序为逆序，通过找出圆盘移动的数学规律，提出一种新的简洁高效的非递归算法。
定义n层汉诺塔的数据类型HanoiType，N表示汉诺塔圆盘的层数。定义圆盘搬运的数据类型Result，first、last分别表示被搬运圆盘disk起始柱、目标柱位置。
代码参考资料：
应用领域
汉诺塔这一玩具是认知心理学研究人类高级认知功能所广泛采用的一种方式。许多研究表明，计划能力和空间记忆能力是完成汉诺塔所必需的能力。汉诺塔的完成成绩通常是用来分析人类执行功能的一个重要指标。此外汉诺塔玩具衍生的问题作为递归算法的一个重要范例在计算机软件设计等课程中也得到了广泛研究。
世界纪录
2021年5月9日，中国的蒋振雄在厦门市举办的世界纪录认证官方挑战中以17.012秒的成绩完成5层汉诺塔。经世界纪录认证(WRCA)官方审核，他创造了“最快时间完成5层汉诺塔”世界纪录。同日，中国的陈明泽在同一场挑战中以1分14.933秒的成绩完成7层汉诺塔，经世界纪录认证(WRCA)官方审核，他创造了“最快时间完成7层汉诺塔”世界纪录。
2022年12月7日，10岁的厦门市开禾小学四年级学生蔡松钦，以11.141秒的成绩打破了“最快时间完成5层汉诺塔（单手）”的世界纪录。
2023年1月3日，马来西亚的林凯毅（Lim Kai Yi）以23.27秒的成绩完成6层汉诺塔，创造了“最快时间完成6层汉诺塔”的吉尼斯世界纪录。同一天，林凯毅（Lim Kai Yi）以32.37秒的成绩完成6层汉诺塔（蒙眼），创造了“最快时间完成6层汉诺塔（蒙眼）”的吉尼斯世界纪录
2023年2月10日，中国的张玉芳以6.352秒的成绩打破“最快时间完成4层汉诺塔（单手）”的世界纪录。
2023年2月22日，中国厦门市的8岁男孩郭弘奕以4.305秒的成绩完成4层汉诺塔（单手）。经世界纪录认证（WRCA）官方审核，他创造了“最快时间完成4层汉诺塔（单手）”世界纪录。
参考资料 >
最快时间完成5层汉诺塔.世界记录认证.2023-11-16
最快时间完成7层汉诺塔.世界记录认证.2023-11-16
11.141秒单手移完5层汉诺塔 厦门10岁男孩刷新世界纪录.光明网.2023-11-16
Fastest time to solve a 6 level Tower of Hanoi.吉尼斯世界纪录.2023-11-16
Fastest time to solve a 6 level Tower of Hanoi blindfolded.吉尼斯世界记录.2023-11-16
世界最快单手完成四层汉诺塔—张玉芳.SSZ国际联赛.2023-11-16
厦门8岁男孩打破汉诺塔世界纪录 成为新的世界纪录保持者.中华网.2023-11-16