尽管我很好地理解了回溯的概念，但我面前有一个我无法理解的问题。我一直找不到关于这个具体问题的任何信息，而且我不知道它是不是换了一个名字。问题是构造一个回溯算法，它将打印出n个“总统”可以坐在圆桌上而不必两次坐在同一个人旁边的座位组合列表。例如，你给它输入8，它给你输出，
1 2 3 4 5 6 7 8
1 3 5 2 6 8 4 7
1 4 2 7 5 8 3 6
现在，我已经为简单的游戏（跳棋、n皇后、tic tac toe）构建了自己的回溯算法，但是我所使用的这些算法都是从一个空白画布开始的，不需要这种实现我需要的是一点指导和洞察力，或者链接到这个问题的更多信息，因为所有给出的都是一页半的内容，主要是讨论在这个特定的问题上，组合1 2 3 4和1 4 3 2是如何有效地相同的这需要使用回溯方法来完成，这让我感到困惑。如果我们能自由地寻找解决办法，我就能轻而易举地做到如有任何帮助，我们将不胜感激。
谢谢！
最佳答案
我想你必须把谁坐在谁旁边的信息添加到回溯算法状态：
首先，说1。你坐在他旁边，把这个“配对”记录在当前的部分解中（实际上只是一对杂乱无章的总统身份证实现无序数字对的一个简单方法是让类的构造函数将较小的id存储在该对的第一个元素中，将较大的id存储在第二个元素中。）因此您有一个部分解决方案2，其中有对1 2 …。
当你找到一个完整的解决方案时，你把它的所有对添加到一个“全局”对列表中这将在以后的搜索中使用。也就是说，如果得到解决方案1-2，则保存对1 2 3 4 5 6 7 8，1-2，2-3，3-4，4-5，5-6，6-7，7-8，1-8，x y z …。
现在，在进行搜索时，您有一个部分解决方案z——到目前为止就任的最后一位总统是x-y，这个部分解决方案中的配对是y-z和z为了让下一任总统就座，你需要看看每一位总统：
还没坐下呢。（因此不包含在部分解的对中。）
在全局配对中不与配对。
如果没有这样的总统，你就放弃部分的解决方案，走回头路。
这就是说，我正在从头开始工作，所以建议您通过使用简单的暴力实现和比较结果来仔细检查是否遗漏了任何边缘情况。
关于java - 总统座位回溯，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20508819/