Knights Tour

Has anybody solved it? Or another question, has Blattner even asked you to? I hated that crap and never figured out the method to solving it, had I figured out that, I could have done it. I even have the rest of the program ready to go.

I'm pretty sure it involves checking all possibilities at each step. I had to do a Queens program for an instructor at a camp once.

Code:


public class Queens
{
   public static void main(String[] args)
   {
      int[] a = new int[8];
      enumerate(a, 0);
   }

   /***********************************************************************
   * Try all permutations using backtracking
   ***********************************************************************/
   public static void enumerate(int[] q, int n)
   {
      int N = q.length;
      if (n == N)
      {
         printQueens(q);
      }
      else
      {
         for (int i = 0; i < N; i++)
         {
            q[n] = i;
            if (isConsistent(q, n))
            {
               enumerate(q, n+1);
            }
         }
      }
   }//end enumerate()

   /***********************************************************************
    * Return true if queen placement q[n] does not conflict with
    * other queens q[0] through q[n-1]
    ***********************************************************************/
   public static boolean isConsistent(int[] q, int n)
   {
      for (int i = 0; i < n; i++)
      {
         if (q[i] == q[n]) return false; // same column
         if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal
         if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal
      }
      return true;
   }//end isConsistent()

   /***********************************************************************
    * Print out N-by-N placement of queens from permutation q in ASCII.
    ***********************************************************************/
   public static void printQueens(int[] q)
   {
      int N = q.length;
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            if (q[i] == j) System.out.print("Q ");
            else System.out.print("* ");
         }
         System.out.println();
      }
      System.out.println();
   }//end printQueens()
}


Well the way Blattner wanted us to do it was to assign a value to each space depending on how early on the space should be filled. (ie a corner sooner than the center)

Pretty sure your way would work as well though.

Well then the idea is that you would choose the starting position, then you evaluate each possible move and pick the square that should be filled earliest and move there. If it doesn't work you go back and try the square that is ranked next for should be used earliest square.