Knights Tour

Go down

Knights Tour

Post by Unchained on Mon Dec 07, 2009 12:15 pm

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.
avatar
Unchained
Mod

Posts : 448

Back to top Go down

Re: Knights Tour

Post by Paul on Mon Dec 07, 2009 10:03 pm

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()
}
avatar
Paul
Pickaxe

Posts : 611

Back to top Go down

Re: Knights Tour

Post by Unchained on Tue Dec 08, 2009 12:44 am

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.
avatar
Unchained
Mod

Posts : 448

Back to top Go down

Re: Knights Tour

Post by Paul on Tue Dec 08, 2009 5:23 am

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.
avatar
Paul
Pickaxe

Posts : 611

Back to top Go down

Re: Knights Tour

Post by Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum