algorithm - does eight queens backtracking solution require any sorting at all? -

hi have sat final year programming exam, asked question: sorting , searching algorithms used solve 8 queens problem.

correct me if wrong there no sorting @ all... understand there basic level of searching needed when placing queen , during backtracking, sorting come this? if @ all?

below have been looking @ , 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) {   (int = 0; < 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();   (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() {   (int = 0; < 8; i++)   {       (int j = 0; j< 8; j++)       {          if (positions[i] == j)          {             system.out.print("q ");          }          else          {             system.out.print("* ");          }       }       system.out.println();   }   system.out.println(); } } 

i think in case you're misinterpreting "sorting" means. in order backtracking work need analyzing positions in sort of predictable ordering. if algorithm not analyzing positions in set order, when "prune" set of positions, may have pruned valid position. without "ordering" or tree structure of positions backtracking not work. not, however, need pre-sort set of positions or that. would, in fact, defeat purpose of backtracking.

the idea that, combination of positions never have built. once conflict found iterations involving combination no longer considered. ordering in these combinations built concern, not sorting them ahead of time. combinations must built , considered in proper oder. allows u know when give on "branch" combinations built on branch have been equally(or worse) incorrect option rejected, otherwise can "over prune" result set, , miss proper combination. no nlogn sorting algorithms required. @ least not in example of n-queens problem. in fact, if pre-built positions , sorted them, ignoring dynamic programming elements allow speed computation of problem considerably.

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