有人可以在这个8皇后算法中反混淆递归

Question

int placement[] = new int[8];
int placeQueen(int row)
{
   if(row == 8)
   {
      printBoard();
      return;
   }

   for(int i = 0; i<8; i++)
   {
      placement[row] = i;
      if(check(row))
      {
         placeQueen(row + 1);  \\This step
      }
   }
}

boolean check(int row)
{
   for(int i = 0; i<row; i++)
   {
      int diff = Math.abs(placement[row] - placement[i]);
      if(diff == 0 || (diff == row - i))
      {
         return false;
      }
   }
return true;
}

我完全没有得到的是递归在for循环中的工作原理.

Answer 1

该算法对行进行递归.它尝试在行r中的每个位置添加一个女王.尝试这个就足够了,因为如果两个皇后被放置在同一行上,你就会违反没有两个皇后可以相互攻击的条件.

由于一次放置一个女王,所以该check功能仅足以检查新放置的女王是否能够攻击任何先前放置的女王.diff == 0确保新女王与以前任何一个女王的位置不同.diff == row - i确保新女王不会沿着任何对角线的移动攻击另一个.(由于前一行中的Math.abs(),这会捕获两个对角线移动.)

所以,再次:尝试一次放置一个女王,看看它是否不能攻击任何其他人.如果可以的话,立即返回 - 否则尝试以可能的方式在下一行添加一个女王.