You have not yet told your ultimate goal
This is not an easy path.. AI .. tough..
This is a discussion on Knight's Tour within the C Programming forums, part of the General Programming Boards category; You have not yet told your ultimate goal This is not an easy path.. AI .. tough.....
You have not yet told your ultimate goal
This is not an easy path.. AI .. tough..
[ Never code before desk work ]
-------------------------------------:-->
A man who fears Nothing is the man who Loves Nothing
If you Love Nothing, what joy is there in your life.
=------------------------------------------------------= - I may be wrong.
my ultimate goal is to write a program that move the knight around the chess board and touch as many squares as possible while not re-visiting any one of the squares. I've posted my codes but they do not work and i really want to know why.
thnx very much
here is the code ( changed some minor things ):
Here are the compile errors i get:Code:/* Knight's Tour ( recursive version ) */ #include <stdio.h> /* 'col' = column */ int knights_tour( int startingRow, int startingCol, int moveNumber, int board[][ 8 ] ); /* returns the number of moves made */ int out_of_bounds( int nextRow, int nextCol ); /* check if next move is off the board */ int visited( int nextRow, int nextCol, int board[][ 8 ] ); /* check if next square is visited already */ int main() { int board[ 8 ][ 8 ] = { 0 }; printf( "***Knight's Tour***" ); printf( "Number of moves made: %d \n\n", knights_tour( 0, 0, 0 , board)); return 0; ) int out_of_bounds( int nextRow, int nextCol ) { /* Returns 1 if out of bounds. Returns 0 if O.K. */ if ( nextRow < 0 || nextRow > 7 ) return 1; if ( nextCol < 0 || nextCol > 7 ) return 1; /* O.K. */ return 0; } int visited( int nextRow, int nextCol, int board[][ 8 ] ) { /* Returns 1 if visited. Returns 0 if not visited. */ if ( board[ nextRow ][ nextCol ] == 1 ) return 1; return 0; } int knights_tour( int startingRow, int startingCol, int moveNumber, int board[][ 8 ] ) { /* moveNumbers: 0 1 2 3 4 5 6 7 */ int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 }; int temp1, temp2; int currentRow, currentCol; int totalMoves = 0; if ( moveNumber > 7 ) return 0; ++moveNumber temp1 = currentRow + vertical[ moveNumber ]; temp2 = currentCol + horizontal[ moveNumber ]; if ( out_of_bounds( temp1, temp2 ) != 1 || visited( temp1, temp2, board ) != 1 ) { board[ currentRow ][ currentCol ] = 1; currentRow += vertical[ moveNumber ]; currentCol += horizontal[ moveNumber ]; ++totalMoves; return knights_tour( currentRow, currentCol, moveNumber , board) + totalMoves; } }
Line 22: parse error before `)'
Line 32: `nextCol' undeclared (first use in this function)
Line 32: (Each undeclared identifier is reported only once
for each function it appears in)
Last edited by Nutshell; 01-08-2002 at 06:26 AM.
Here's basically what needs to happen when you make a move...
You have a variable, totalMoves. You select which of the 8 possible moves gives you the highest return (and you use the function knights_tour to find this value).
Your function just doesn't do this. Also, there really isn't any reason to pass the function the number of moves. All that the function really needs to be passed are the coordinates of the piece on the board (assuming that the board array is global, which it probably should be for this).
Also, your current function makes no use of the coordinates passed to it. It seems you forgot to use the startingRow and startingCol variables.
Following is a small code snippet. Don't worry, it isn't complete enough to give you the answer itself, but I think that this is reveals a bit about what your code needs to do...This isn't complete, I mean, the function will have to handle setting/unsetting board flags, and testing for legal board positions.Code:totalMoves = 0; // This may have to change. for (moveNumber = 0; moveNumber < 8; moveNumber++) { totalMoves = max(totalMoves, knights_tour(startingRow + horizontal[i], startingCol + vertical[i]) }
Also, it seems your code doesn't actually return any value when it gets to an illegal board position. You definately want to return a value for this. In general, you want to return a value, such that you don't have to really do any vodoo on the callee side of the function. For this problem, if the function detects that it is in an illegal board position (which should be the first thing it checks for), then it either needs to return a 0, or a -1, depending on how you are handling the function.
Callou collei we'll code the way
Of prime numbers and pings!
Hi,
I give up recursion. If possible provide maybe a link or two involving some simple recursion exercise to start me off pls. Here is my edited code. However i still get the 3 compile errors i got before:
my current code:Line 22: parse error before `)'
Line 32: `nextCol' undeclared (first use in this function)
Line 32: (Each undeclared identifier is reported only once
for each function it appears in)
Code:/* Knight's Tour ( recursive version ) */ #include <stdio.h> /* 'col' = column */ int knights_tour( int startingRow, int startingCol, int board[][ 8 ] ); /* returns the number of moves made */ int out_of_bounds( int nextRow, int nextCol ); /* check if next move is off the board */ int visited( int nextRow, int nextCol, int board[][ 8 ] ); /* check if next square is visited already */ int main() { int board[ 8 ][ 8 ] = { 0 }; printf( "***Knight's Tour***" ); printf( "Number of moves made: %d \n\n", knights_tour( 0, 0, board)); return 0; ) int out_of_bounds( int nextRow, int nextCol ) { /* Returns 1 if out of bounds. Returns 0 if O.K. */ if ( nextRow < 0 || nextRow > 7 ) return 1; if ( nextCol < 0 || nextCol > 7 ) return 1; /* O.K. */ return 0; } int visited( int nextRow, int nextCol, int board[][ 8 ] ) { /* Returns 1 if visited. Returns 0 if not visited. */ if ( board[ nextRow ][ nextCol ] == 1 ) return 1; return 0; } int knights_tour( int startingRow, int startingCol, int board[][ 8 ] ) { /* moveNumbers: 0 1 2 3 4 5 6 7 */ int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 }; int temp1, temp2; int currentRow = startingRow; int currentCol = startingCol; int totalMoves = 0; int end = 0; int moveNumber; while ( end != 1 ) { for ( moveNumber = 0; moveNumber <= 7; moveNumber++ ) { temp1 = currentRow + vertical[ moveNumber ]; temp2 = currentCol + horizontal[ moveNumber ]; if ( out_of_bounds( temp1, temp2 ) != 1 && visited( temp1, temp2, board ) != 1 ) { board[ currentRow ][ currentCol ] = 1; currentRow += vertical[ moveNumber ]; currentCol += horizontal[ moveNumber ]; ++totalMoves; break; } else { /* Next move not possible */ if ( moveNumber == 7 ) end = 1; /* No more possible moves... */ continue; } } } return totalMoves; }
Your main function ends with a parenthesis, not a chicken lip...
-Govtcheez
govtcheez03@hotmail.com
HI,
I think i've made it! Here is the code and pls tell me if it really works!!!!!!!! special thnx to Govtcheez for catchin the little bug and all others who've posted!
Code:/* Knight's Tour ( recursive version ) */ #include <stdio.h> /* 'col' = column */ int knights_tour( int startingRow, int startingCol, int board[][ 8 ] ); /* returns the number of moves made */ int out_of_bounds( int nextRow, int nextCol ); /* check if next move is off the board */ int visited( int nextRow, int nextCol, int board[][ 8 ] ); /* check if next square is visited already */ int main() { int board[ 8 ][ 8 ] = { 0 }; printf( "***Knight's Tour***\n\n" ); printf( "Number of moves made: %d \n\n", knights_tour( 0, 0, board)); getch(); return 0; } int out_of_bounds( int nextRow, int nextCol ) { /* Returns 1 if out of bounds. Returns 0 if O.K. */ if ( nextRow < 0 || nextRow > 7 ) return 1; if ( nextCol < 0 || nextCol > 7 ) return 1; /* O.K. */ return 0; } int visited( int nextRow, int nextCol, int board[][ 8 ] ) { /* Returns 1 if visited. Returns 0 if not visited. */ if ( board[ nextRow ][ nextCol ] == 1 ) return 1; return 0; } int knights_tour( int startingRow, int startingCol, int board[][ 8 ] ) { /* moveNumbers: 0 1 2 3 4 5 6 7 */ int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 }; int temp1, temp2; int currentRow = startingRow; int currentCol = startingCol; int totalMoves = 0; int end = 0; int moveNumber; while ( end != 1 ) { for ( moveNumber = 0; moveNumber <= 7; moveNumber++ ) { temp1 = currentRow + vertical[ moveNumber ]; temp2 = currentCol + horizontal[ moveNumber ]; if ( out_of_bounds( temp1, temp2 ) != 1 && visited( temp1, temp2, board ) != 1 ) { board[ currentRow ][ currentCol ] = 1; currentRow += vertical[ moveNumber ]; currentCol += horizontal[ moveNumber ]; ++totalMoves; break; } else { /* Next move not possible */ if ( moveNumber == 7 ) end = 1; /* No more possible moves... */ continue; } } } return totalMoves; }
It compiled, ran, and said 41 moves... Is that what you wanted?
-Govtcheez
govtcheez03@hotmail.com
Recursion is the easier way to do this problem, but this is a difficult sort of problem to start off with. I suggest you try solving the following (not as difficult) problem instead:
For an NxN square, divided into NxN cells, find the number of paths from the bottom left cell to the top right cell.It's not quite the same type of recursive problem as the Knight's Tour, but it is also a game state search, so it's somewhat similar.Code:#include <stdio.h> #define ASPECT 3 // Creates an ASPECTxASPECT array of 0s // Having this as global, and using a define as our aspect saves // a lot of trouble, although it makes our progam less versatile. int cell[ASPECT][ASPECT] = {}; // Gives the number of legal paths from x,y to ASPECT-1, ASPECT-1 // On array cell[][] // paths (ASPECT - 1, ASPECT - 1) returns 1 int paths (int x, int y); // Returns 0 if the x, y is out of bounds or a marked spot. // Else, returns 1 int isPosLegal(int x, int y); // Returns 1 if (x, y) == (ASPECT - 1, ASPECT - 1) // Else, returns 0 int isPosEnd (int x, int y); int main (void) { int i = paths (0, 0); printf ("The number of paths is %d.\n", i); return 0; } paths (int x, int y) { // } int isPosEnd (int x, int y) { // } int isPosLegal (int x, int y) { // }
Callou collei we'll code the way
Of prime numbers and pings!
thnx thnx thnx
to govtcheez:
the output results are getting to where they should be, you can
read my previous post if you'[re unsure what my program's
suppose to do. thnx a lot
Yes i know many people say that recursion is easier and simpler. But i am a real newbie and really need to understand recursion. And i simply can't do such 'hard-for-me-at-the-moment' recursion stuff......
Last edited by Nutshell; 01-08-2002 at 09:46 AM.
Your program gives up at this point whenCode:else { /* Next move not possible */ if ( moveNumber == 7 ) end = 1; /* No more possible moves... */ continue; }
it should go back in the tree of moves and
try another combination. As I understand it
you want the knight to touch every square on
the chess board without touching a square twice.
To come up with a recursive solution notice
that the number of knight paths from a given
position is the number of knight paths after
a move + the number of knight paths after another move ... + the number of knight paths after the 8 move. Once you get this all that is required is writing a base case which determines if a move is successful or the number of moves == 63. The actual code for this is simple.
sorry but i dont fully really get your idea.
Do you mean the no. of possible knight paths is the number of 'possible' knight paths the first move + the no. of possible knight paths after another move + the 8th move ?
Can you maybe post a sample recursion example for me to study pls?
thank you
Last edited by Nutshell; 01-08-2002 at 10:51 AM.
He means that just because the knight doesn't have any moves left, it doesn't mean he couldn't have taken a different path earlier in the series and gotten different results.
-Govtcheez
govtcheez03@hotmail.com
oh, do u mean that the bit he posted only talks about the bit in my program when there're no moves left for the knight?
I don't really understand what he meant anyway? What will i get if i add all the possible moves for each move? Anyway how do i do it? WHich next move do i make to make another move if you know what i mean?
thnx
This is a bit long ...
If you study the fibonacci sequence you will
notice that
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
As a function
int fib(int n)
{
if (n == 0 || n == 1)
return n; /* base case */
return fib(n-1) + fib(n-2);
}
If you look at the tree generated by this
function you will notice that the number of terminal nodes (or just end values in the tree)
is equivalent to
nodes_req(n) = nodes_req(n-1) + nodes_req(n-2)
Now all that is required to finish this is
the knowlege that the nodes required to compute
fib(0) is nodes_req(0) which is equal to 1.
What we have is
nodes_req(0) = 1
nodes_req(n) = nodes_req(n-1) + nodes_req(n-2)
This looks similar to fibnoccie sequence and it's
possible to show that
nodes_req(n) = fib(n+1)
With our problem we arn't really intrested in the
number of nodes, but we are interested
in a procedure which goes through all the nodes
until a certain condition is met.
You will also probaly want to create a function genmoves so that you can sort the moves so that the knight moves into the corners first as it's much faster.
To do this I did something like
Which measures the difference from the center.Code:void gen_point_value() { int i, j; int center_row = NR_ROWS/2; int center_col = NR_COLS/2; for (i = 0; i < NR_ROWS; ++i) for (j = 0; j < NR_ROWS; ++j) point_value[i][j] = abs(i-center_row) + abs(j-center_col); }
And then I sorted on point_value[row][col]. Though
your best off not sorting until you are finished with the rest of the program.
For the structure of your recursive function
will something like
Code:knight_tour(row, col, count, final_path) make square dirty check base case n = genmoves(movelist, row, col) for i := 0; i < n; ++i check to see if knight_tour(movelist[i].row, movelist[i].col) == SUCCESS; if success update final_path and return SUCCESS; if loop finishes with no success then clean square and return FAILURE
You only passed two arguments but in the function declaration you specified 4 parameters. Also, Where in the function evaluates if it's success or not. And what does the operator ':=' mean?knight_tour(movelist[i].row,
movelist[i].col)
i know i don't know much but pls give a hand.
thnx