Thread: Chess problem Horse

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    37

    Question Chess problem Horse

    Does anyone has an idea how to do this one or is there a website where i can get info on how this can be done.

    I need to write a program that can do this:

    A classical chess problem: is it possible to make the horse visit every square once using its
    usual chess moves?

    Actually, to accomplish this task, there is a nice heuristic that states that player can start from
    any square and should move the horse to the next legal but not-yet-visited square according
    to the following rule: consider all the legal but not-yet-visited squares and pick the one that
    would have the maximum number of legal moves next.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Have you tried the "internets". Maybe you could perform a search at a search engine?


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Wikipedia - knights tour

    There is a trick to doing this, iirc it was to always have the knight move to the square that has the fewest possible connecting knight moves. Turns the whole problem into the realm of networking and communication.

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    41
    Quote Originally Posted by Cyberman86 View Post
    Does anyone has an idea how to do this one or is there a website where i can get info on how this can be done.

    I need to write a program that can do this:

    A classical chess problem: is it possible to make the horse visit every square once using its
    usual chess moves?

    Actually, to accomplish this task, there is a nice heuristic that states that player can start from
    any square and should move the horse to the next legal but not-yet-visited square according
    to the following rule: consider all the legal but not-yet-visited squares and pick the one that
    would have the maximum number of legal moves next.
    Sounds like a 2 d array and changing all the contents to something in a specific way.

    Does it sound hard to you?

    Know how to declare a 2 d array?(the size of a chess board and wouldnt hurt to start all positions of the array to 0, except one of them (where the knight is starting))
    perhaps after you post that code I'll try and help some more.

  5. #5
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by Cyberman86 View Post
    A classical chess problem: is it possible to make the horse visit every square once using its usual chess moves?
    A classical solution: yes!

    Actually, to accomplish this task, there is a nice heuristic that states that player can start from
    any square and should move the horse to the next legal but not-yet-visited square according
    to the following rule: consider all the legal but not-yet-visited squares and pick the one that
    would have the maximum number of legal moves next.
    That's a nice way of saying "when using brute force, always pick the most promising move" (known as the Minimax Algorithm), which implies that your algorithm knows a correct solution before making the first move.

    If you actually want to compute a solution, I suggest using brute force.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is not a brute force algorithm.

    In this approach, you count the connections to the possible squares the knight could move to, from it's current square.

    Then you move to the square with the fewest connections that has not yet been visited. It is not required that you calculate the whole tour (although it becomes easy to do so). You can just calculate the knight's (one), next move.

    I did this by hand, rather than by the computer, so I'm not ENTIRELY sure that no look-ahead was used, but certainly I didn't pre-plan the whole tour.

  7. #7
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by Adak View Post
    This is not a brute force algorithm.
    I was talking about Cyberman's approach, not yours. Your approach looks promising, although there might be cases with complications (starting near the corner), but I'll have to do some examples first.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    It's called Warndorff's Algorithm.

  9. #9
    Registered User
    Join Date
    Sep 2008
    Posts
    37

    Post

    Quote Originally Posted by strickyc View Post
    Sounds like a 2 d array and changing all the contents to something in a specific way.

    Does it sound hard to you?

    Know how to declare a 2 d array?(the size of a chess board and wouldnt hurt to start all positions of the array to 0, except one of them (where the knight is starting))
    perhaps after you post that code I'll try and help some more.

    Chess Problem:
    Code:
    In the main() function:
    1. Declare a 8x8 two dimensional array (int chess[8][8];) to represent a chess
    board and set all its elements to -1 (i.e., no cells (squares) are visited, yet).
    
    2. Ask user to enter i and j as the row and column numbers of the initial cell. (Since
    you are using C, make sure that user enters a number between 0 and 7 (inclusive)
    for row and column numbers).
    
    3. Set chess[i][j] to 1 means that the horse visited that cell first.
    
    4. Implement and call a function to determine in which order the horse visits the legal
    squares once according to our random selection strategy described below and
    returns the number of squares visited
    numofsquares = random_horse(chess, i, j);
    print(“Number of squares visited = %d\n”, numofsquares);
    
    5. Implement and call a function print_board(chess); to print the values in chess
    board showing in which order the cells are visited
    
    In the int random_horse(int chess[][8], int i, int j) function:
    while(1) {
    a. Identify the legal but not-yet-visited squares
    b. If there is no such squares return chess[i][j];
    c. Pick one of these cells randomly (say you picked chess[x][y])
    d. Update order number (chess[x][y] = chess[i][j] + 1;)
    e. Move the horse to the selected cell (i=x; j=y;)
    } /* end of while */

  10. #10
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    I think Warndorff's Algorithm can't work all of the time, but I'm not sure whether my argument works:

    Visiting every square exactly once is known to be NP-complete (Hamiltonian path), hence the optimal algorithm will have a runtime >= O(2^n) where n*n is the size of the board. In Warndorff's Algorithm, the knight visits every square exactly once (i.e. there are n*n iterations) and for each square, the knight checks at most 8 other squares (the maximum possible number of different knight moves). Hence, the overall runtime is O(n*n*8) = O(n^2). If Warndorff's algorithm always works, then we have discovered a polynomial time algorithm which solves a NP-complete problem, hence P=NP.

    So there are three possible scenarios:
    - I'm wrong
    - P=NP
    - Warndorff occasionally fails

    Right now, I'd choose the last one. Ideas anyone?

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  11. #11
    Registered User
    Join Date
    Sep 2008
    Posts
    37
    This is what i have so far, Not sure if it makes sense but i tried my best.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    int main()
    {
        
        int random_horse(int chess[8][8], int i, int j)
        
        for (i=0; i<7; i++)
          for(j=0; j<7; j++)
           random_horse[i][j] = i+j;
           
            i=2;
            j=2;
        
        numofsquares = random_horse(chess, i, j);
    print(“Number of squares visited = %d\n”, numofsquares);
        
        
        while(1) i-1>=0 && j-2>=0 && chess [i-1][j-2]== -1) 
        {
               pm[k][0] = i-1;
               pm[k][1] = j-2;
               k++;
               
        }
        
        
        {
                 
                   
        
               if(k==0) return chess[1][j];
               rc = rand_int (0,k-1);
               x = pm[rc][0];
               y = pm[rc][1];
               
               chess[x][y] = chess[i][j] + 1;
               
               i=x;
               j=y;
               
         }
              
              
        
        
         return 0; 
         }

  12. #12
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Have you tried to compile your code? If you do, make sure you get rid of all the compiler errors. Do you have a specific question?

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  13. #13
    Registered User
    Join Date
    Sep 2008
    Posts
    37
    Quote Originally Posted by Snafuist View Post
    Have you tried to compile your code? If you do, make sure you get rid of all the compiler errors. Do you have a specific question?

    Greets,
    Philip
    i just want to know if the whole code makes sense according to the problem instructions, I'm a beginner and sometimes i can't tell if the code is following the problem.


    Code:
    In the main() function:
    1. Declare a 8x8 two dimensional array (int chess[8][8];) to represent a chess
    board and set all its elements to -1 (i.e., no cells (squares) are visited, yet).
    
    2. Ask user to enter i and j as the row and column numbers of the initial cell. (Since
    you are using C, make sure that user enters a number between 0 and 7 (inclusive)
    for row and column numbers).
    
    3. Set chess[i][j] to 1 means that the horse visited that cell first.
    
    4. Implement and call a function to determine in which order the horse visits the legal
    squares once according to our random selection strategy described below and
    returns the number of squares visited
    numofsquares = random_horse(chess, i, j);
    print(“Number of squares visited = %d\n”, numofsquares);
    
    5. Implement and call a function print_board(chess); to print the values in chess
    board showing in which order the cells are visited
    
    In the int random_horse(int chess[][8], int i, int j) function:
    while(1) {
    a. Identify the legal but not-yet-visited squares
    b. If there is no such squares return chess[i][j];
    c. Pick one of these cells randomly (say you picked chess[x][y])
    d. Update order number (chess[x][y] = chess[i][j] + 1;)
    e. Move the horse to the selected cell (i=x; j=y;)
    } /* end of while */

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    @Snafuist: I've used Warndorff's algorithm by hand, and it worked fine. Can you give an example where it fails?

    Solving the knights tour can be done without using Warndorff's algo, it's just that it's more difficult.

    @Cyberman: You can't make a knights tour succeed very often, simply by choosing a random square for the knight to move to next.

    That wouldn't be much of a puzzle would it?

    Of course, you have to stick with the assignment you were given, just be aware that very few attempted tours by your program, will succeed.

    The way to tell if your program meets the assignment requirements is to simply run it, and see if it does what the assignment requires, step by step. We can't check that any better than you can, and I'm certainly not going to try.

    If you have a question about C (and not about your assignment), ask it.

  15. #15
    Registered User
    Join Date
    Apr 2009
    Posts
    41
    Quote Originally Posted by Cyberman86 View Post
    i just want to know if the whole code makes sense according to the problem instructions, I'm a beginner and sometimes i can't tell if the code is following the problem.


    Code:
    In the main() function:
    1. Declare a 8x8 two dimensional array (int chess[8][8];) to represent a chess
    board and set all its elements to -1 (i.e., no cells (squares) are visited, yet).
    
    2. Ask user to enter i and j as the row and column numbers of the initial cell. (Since
    you are using C, make sure that user enters a number between 0 and 7 (inclusive)
    for row and column numbers).
    
    3. Set chess[i][j] to 1 means that the horse visited that cell first.
    
    4. Implement and call a function to determine in which order the horse visits the legal
    squares once according to our random selection strategy described below and
    returns the number of squares visited
    numofsquares = random_horse(chess, i, j);
    print(“Number of squares visited = %d\n”, numofsquares);
    
    5. Implement and call a function print_board(chess); to print the values in chess
    board showing in which order the cells are visited
    
    In the int random_horse(int chess[][8], int i, int j) function:
    while(1) {
    a. Identify the legal but not-yet-visited squares
    b. If there is no such squares return chess[i][j];
    c. Pick one of these cells randomly (say you picked chess[x][y])
    d. Update order number (chess[x][y] = chess[i][j] + 1;)
    e. Move the horse to the selected cell (i=x; j=y;)
    } /* end of while */
    No it doesnt make since. Just think of your problem once sentence at a time.
    so for starts

    Code:
    int main()
    {
          //step 2:  int xcoord;
                          int ycoord;
    
      step 1: int chessBoard[8][8] = {{-1,-1,-1,-1,-1,-1,-1,-1},
                                              {-1,-1,-1,-1,-1,-1,-1,-1},
                                              {-1,-1,-1,-1,-1,-1,-1,-1},
                                              {-1,-1,-1,-1,-1,-1,-1,-1},
                                              {-1,-1,-1,-1,-1,-1,-1,-1},
                                              {-1,-1,-1,-1,-1,-1,-1,-1},
                                              {-1,-1,-1,-1,-1,-1,-1,-1},
                                              {-1,-1,-1,-1,-1,-1,-1,-1}};
    step 2:  printf("Enter the  x coord for the peice to be set\n");
                 scanf("%d", &xcoord);
                 printf("Enter the  y coord for the peice to be set\n");
                 scanf("%d", &ycoord);
    
                 /* since your didn't plan your program out ahead of time you need to go back and add the variables as your create them.*/
    
    step 3:  chessBoard[xcoord-1][ycoord-1] = 1;  
                
    }
    have fun.

    Programming is problem solveing.
    btw I know its easier to use for to set all the elements to -1; he can do that :P
    Last edited by strickyc; 05-01-2009 at 09:52 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM