Scala中for-yield结构内递归调用的执行逻辑疑问（N皇后问题）

咱们一步步拆解你提出的三个问题，把这段递归代码的逻辑讲透：

1. 从k=0到k=n的递归执行逻辑 #

这段代码用的是回溯递归的思路，placeQueens(k)的作用是生成前k行所有合法的皇后放置方案（每个方案是一个列表，列表里的元素代表对应行的皇后所在列，注意列表的头是第k行的列，尾是第1行的列）。

咱们以n=4为例，一步步看执行流程：

• k=0：这是递归的终止条件，返回Set(List())——表示0行的时候，只有一种“空方案”。
• k=1：调用placeQueens(0)拿到空方案集合，然后遍历列0到3。因为没有已放置的皇后，所有列都合法，所以生成Set(List(0), List(1), List(2), List(3))，每个列表代表第1行皇后在对应列的方案。
• k=2：先调用placeQueens(1)拿到4种1行的方案，对每个方案（比如List(0)），遍历列0到3，用isSafe判断是否和已有的皇后（第1行的列0）冲突：
  • 不能同列（col≠0），不能同对角线（列差≠行差，这里行差是1，所以col≠0±1→col≠1）
  • 所以合法列是2、3，生成List(2,0)和List(3,0)两个方案
  • 对其他1行的方案做同样判断，最终k=2的结果是所有2行合法方案的集合
• k=3：重复上述逻辑，基于k=2的合法方案，尝试在第3行放置皇后，过滤掉冲突的列，生成所有3行的合法方案集合
• k=4：基于k=3的合法方案，尝试在第4行放置皇后，最终得到4行的所有合法解，也就是你看到的Set(List(1,3,0,2), List(2,0,3,1))

简单说，递归是从k=n往k=0“探底”，然后从k=0开始一步步往上构建所有合法的放置方案，每一步都通过isSafe过滤掉无效的选择。

2. yield col::queens行中是否存在递归调用？ #

这里没有递归调用。递归调用只发生在for推导式的第一行：queens <- placeQueens(k-1)——这一行会触发对placeQueens(k-1)的调用，拿到前k-1行的所有合法方案。

而yield col::queens只是做了一个列表拼接操作：把当前行合法的列col，加到前k-1行的方案列表queens的头部（因为queens是前k-1行的列集合，头是第k-1行的列，所以col::queens就变成了前k行的方案，头是第k行的列）。这一步只是数据拼接，没有触发新的递归。

3. 为何最终结果是列表的Set？ #

原因有两点：

• 函数返回类型定义：placeQueens的返回类型是Set[List[Int]]，初始终止条件k=0返回的就是Set(List())，后续的for推导式是在Set上进行操作的——Scala的for推导式会根据输入集合的类型生成对应类型的输出，所以每次yield的元素会被自动收集到Set中。
• 业务需求适配：N皇后的解是一组互不重复的放置方案，Set的特性是元素唯一，正好用来存储这些不重复的解，避免出现重复的方案（虽然回溯逻辑本身不会生成重复解，但用Set来存储解集合是更合理的选择）。

内容的提问来源于stack exchange，提问作者Hillary