does eight queens backtracking solution require any sorting at all?

Question

Hi I have just sat my final year programming exam, I was asked the question: what sorting and searching algorithms are used to solve the 8 queens problem.

Correct me if I am wrong but there is no sorting at all... I understand that there is a basic level of searching needed when placing the queen and during backtracking, but where does sorting come into this? if at all?

Below is what I have been looking at and just cant see it.

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

I think in this case you're misinterpreting what "sorting" means. In order for backtracking to work you need to be analyzing positions in some sort of predictable ordering. If your algorithm is not analyzing positions in a set order, then when you "prune" a set of positions, you may have pruned a valid position. Without this "ordering" or tree like structure of positions backtracking does not work. You do not, however, need to pre-sort a set of positions or anything like that. This would, in fact, defeat the purpose of backtracking.

The idea is that, some combination of positions never even have to be built. Once a conflict is found ALL iterations involving that combination are no longer even considered. It is the ordering in which these combinations are built that is a concern, not sorting them ahead of time. All combinations must be built and considered in proper oder. This allows u to know when we give up on a "branch" that all combinations built on this branch would have been equally(or even worse) incorrect as the option we just rejected, otherwise you can "over prune" your result set, and miss a proper combination. But no NlogN sorting algorithms are required. At least not in the example of the n-queens problem. In fact, if you pre-built all positions and sorted them, you are completely ignoring the dynamic programming elements that allow us to speed up the computation of this problem considerably.

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