0

嗨，我刚刚参加了最后一年的编程考试，有人问我一个问题：使用什么排序和搜索算法来解决 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();
}
}
4

1 回答 1

1

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

这个想法是，甚至不必建立一些职位组合。一旦发现冲突，甚至不再考虑涉及该组合的所有迭代。值得关注的是构建这些组合的顺序，而不是提前对它们进行排序。所有组合都必须按正确的顺序构建和考虑。这使您可以知道当我们放弃“分支”时，在该分支上构建的所有组合与我们刚刚拒绝的选项一样（或更糟）不正确，否则您可以“过度修剪”您的结果集，并且错过适当的组合。但是不需要 NlogN 排序算法。至少在 n-queens 问题的例子中不是这样。事实上，如果你预先构建了所有位置并对其进行排序，

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

于 2013-05-21T16:57:00.987 回答