Thread: How to write a recursion program of this..

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    7

    How to write a recursion program of this..

    Hello, I'm trying to write a little program to move a knight around a 8x8 chess board...
    The user can type in a place to start and a place to stop, the computer should try to find the way to go to the stop place with least steps...I wish that I can write it in a recursion form...
    Can anyone help me with this? I'm a newbie and I can't think of a way to do this..^^"

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Aug 2005
    Posts
    7
    It's not a knights tour problem....
    I don't need it to walk around the whole board..
    I just need it to walk from a starting place to a ending place..
    ^^"

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So the shortest number of moves between start(x,y) and end(x,y) then?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Aug 2005
    Posts
    7
    I then need to output the coordinate of every move in the path that the knight traveled through from the start point to the goal...
    I also need to tell the user how many steps it took least...
    thanks for helping me!

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So it's like the knights tour, but you stop when you reach a point, rather then when you've visited all 64 positions.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Aug 2005
    Posts
    7
    okay~~ let me think it over...@@"...

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Flood fill!


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

  9. #9
    Registered User
    Join Date
    Aug 2005
    Posts
    7
    what is flood fill @@"?

  10. #10
    Registered User
    Join Date
    Nov 2002
    Posts
    491

  11. #11
    Registered User
    Join Date
    Aug 2005
    Posts
    7
    this is what i have written so far...
    I'm stuck at the place where I have to keep on moving the knight into different places....
    Can anyone write me the code to let me study it with?
    I can learn a lot that way>"<...
    thanks !
    I looked at the flood fill..I'm new to it...I need some time to understand it lol....
    Code:
    #include <stdio.h> 
    #include <stdlib.h>
    int chessBoardArray[9][9] = { 0 }; 
    
    void startBoard(); 
    void printBoard(); 
    void move(); 
    void moveknight( const int startx, const int starty ); 
    int check( int m, int n );
    
    struct Move{ 
      int X; 
      int Y; 
    }
    
    
    const Move[8] = { {+1,+2}, {+1, -2}, {+2,+1}, {+2,-1}, {-1,+2}, {-1,-2}, {-2,+1}, {-2,-1} }; 
    
    
    main() 
    { 
      int startColumn, startRow; 
      int endColumn, endRow; 
      int x, y; 
      
      startBoard(); 
      printBoard(); 
      printf( "Select a starting point:\n" ); 
      printf( "Enter x coordinate of starting point:" ); 
      scanf( "%d", &startColumn );     
      printf( "Enter y coordinate of starting point:" ); 
      scanf( "%d", &startRow ); 
      printf( "Enter x coordinate of ending point:" ); 
      scanf( "%d", &endColumn );     
      printf( "Enter y coordinate of ending point:" ); 
      scanf( "%d", &endRow ); 
      printf( " -1 means the starting point\n" ); 
      printf( " -2 means the ending point\n" ); 
      chessBoardArray[ startRow ][ startColumn ] = (-1); 
      chessBoardArray[ endRow ][ endColumn ] = (-2); 
      printBoard(); 
      printf( "Start:(%d,%d)\n", startRow, startColumn ); 
      printf( "End:(%d,%d)\n\n", endRow, endColumn );     
      printf( "Calculationg least steps.....\n" ); 
      moveknight( startRow, startColumn ); 
      printBoard(); 
      system( "pause" );
        return 0;   
    } 
    
    void startBoard() 
    { 
      int i, j; 
        for( i = 0; i <= 8; i++ ) 
         chessBoardArray[i][0] = i; 
      for( j = 0; j <= 8; j++ ) 
         chessBoardArray[0][j] = j; 
    } 
    
    void printBoard() 
    { 
      int i, j, k; 
        printf("%35s\n", "Chess Board" ); 
      printf( "     -------------------------------------------------\n" ); 
      for( i = 8; i >= 1; i-- ){ 
         for( j = 0; j <= 8; j++ ){ 
         printf( "%3d  |", chessBoardArray[i][j]); 
      } 
         printf( "\n" ); 
         printf( "     -------------------------------------------------" ); 
      printf( "\n" ); 
      } 
      printf( "\n" ); 
      for( i = 0, j = 0; j<= 8; j++ ) 
         printf( "%3d   ", chessBoardArray[i][j]); 
      printf( "\n\n" ); 
      } 
    
    
    void moveknight( const int x, const int y) {
       int i, checkans;
       for( i = 0; i < 8; i++ ){
          checkans = check( x+Move[i].X, y+Move[i].Y );
          if( checkans == 1 ){
              chessBoardArray[x+Move[i].X][y+Move[i].Y]++;
         } /* End If */
         }/* End For */
     }
    
    int check( int m, int n) 
    { 
       if( m > 9 || m < 1 || n > 9 || n < 1 )
          return 0;      
       else return 1;
    }

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    1. Chess boards are 8x8
    In some places, your code is 8x8, and in others, its 9x9

    2. You need a way of making copies of the board, so you can go back to an old position later on.
    So something like this perhaps
    Code:
    void tryPosition ( int x, int y ) {
      if ( isInvalidPosition(x,y) || isOccupiedPosition(x,y) ) return;  // can go no further here
      board[x][y] = occupied;
      // evaluate this position
      // also run your loop 8 times using your Move array to check all possible positions from here
      // eg.  tryPosition(x+Move[0].x, y+Move[0].y);
      // only in a loop
      board[x][y] = free;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Registered User
    Join Date
    Aug 2005
    Posts
    7
    I had some places 9x9 because I need to let the user see which row and which place the board is located at..^^"

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by chillwater
    I had some places 9x9 because I need to let the user see which row and which place the board is located at..^^"
    That doesn't make any sense. I'll assume you meant "see which row and which colum he piece is located it", but it still doesn't make any sense.

    All you need is the board itself, and a set of coordinates to keep track of where the piece is. Nothing more is needed.
    Code:
    for( y = 0; y < boardy; y++ )
        for( x = 0; x < boardx; x++ )
        {
            if( piecey == y && piecex == x )
                drawknight(  );
            else
                drawsquare( );
        }
    I can't see how adding another row and colum does anything useful here.


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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  2. how could i write this program: cat < apa | wc | wc > bepa
    By strugglingman in forum C Programming
    Replies: 2
    Last Post: 04-26-2006, 04:40 PM
  3. Hints to write a program
    By Bnchs400 in forum C++ Programming
    Replies: 28
    Last Post: 04-05-2006, 05:35 AM
  4. Challenge to write a program
    By Twisted.alice in forum A Brief History of Cprogramming.com
    Replies: 40
    Last Post: 05-15-2003, 12:00 PM
  5. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 12:39 PM