algorithm - 八皇后回溯解决方案是否需要任何排序？

Question

嗨，我刚刚参加了最后一年的编程考试，有人问我这个问题: 用什么排序和搜索算法来解决 8 皇后问题。

如果我错了请纠正我，但根本没有排序...... 我知道在放置女王和回溯期间需要进行基本级别的搜索，但是排序从何而来？如果有的话？

下面是我一直在看但看不到的内容。

public class Queens
{
int[] positions;
int counter = 0;
boolean isFinished = false;

public Queens()
{
  positions = new int[8];
  placeQueens(0);
}

public boolean canPlaceQueen(int row, int column)
{
  for (int i = 0; i < row; i++)
  {
     if (positions[i] == column || (i - row)== (positions[i]-column) || (i-row)== (column - positions[i]))
     {
        return false;
     }
  }
  return true;
}

public void placeQueens(int row)
{
  counter++;
  printQueens();
  for (int column = 0; column < 8; column++)
  {
     if (canPlaceQueen(row, column))
     {
        positions[row] = column;
        if (row == 8-1)
        {
           System.out.println("FINAL " +counter);
           isFinished = true;
           printQueens();
        }
        else if(!isFinished)
        {
           placeQueens(row+1);
        }
     }
  }
}


public void printQueens()
{
  for (int i = 0; i < 8; i++)
  {
      for (int j = 0; j< 8; j++)
      {
         if (positions[i] == j)
         {
            System.out.print("Q ");
         }
         else
         {
            System.out.print("* ");
         }
      }
      System.out.println();
  }
  System.out.println();
}
}

Answer 1

我认为在这种情况下，您误解了“排序”的含义。为了使回溯起作用，您需要以某种可预测的顺序分析头寸。如果您的算法没有按设定顺序分析头寸，那么当您“修剪”一组头寸时，您可能已经修剪了一个有效头寸。没有这种“排序”或树状结构的位置回溯不起作用。但是，您不需要预先对一组位置或类似的东西进行排序。事实上，这会破坏回溯的目的。

这个想法是，甚至不需要建立一些职位组合。一旦发现冲突，就不再考虑涉及该组合的所有迭代。问题在于构建这些组合的顺序，而不是提前对它们进行排序。所有组合都必须按正确的顺序构建和考虑。这让你知道当我们放弃一个“分支”时，建立在这个分支上的所有组合与我们刚刚拒绝的选项一样(甚至更糟)不正确，否则你可以“过度修剪”你的结果集，并且错过一个合适的组合。但不需要 NlogN 排序算法。至少在 n 皇后问题的例子中不是。事实上，如果您预先构建所有位置并对其进行排序，您将完全忽略允许我们大大加快此问题计算速度的动态编程元素。

http://en.wikipedia.org/wiki/Backtracking