1. You have not yet told your ultimate goal

This is not an easy path.. AI .. tough..

2. 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 ):

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;
}
}```
Here are the compile errors i get:

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)

3. 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...
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])
}```
This isn't complete, I mean, the function will have to handle setting/unsetting board flags, and testing for legal board positions.

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.

4. 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:

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)
my current code:

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;
}
}
}

}```

5. Your main function ends with a parenthesis, not a chicken lip...

6. 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;
}
}
}

}```

7. It compiled, ran, and said 41 moves... Is that what you wanted?

8. 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.
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)
{
//
}```
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.

9. 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......

10. Code:
```else { /* Next move not possible */
if ( moveNumber == 7 )
end = 1;  /* No more possible moves... */
continue;
}```
Your program gives up at this point when
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.

11. 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

12. 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.

13. 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

14. 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

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);
}```
Which measures the difference from the center.
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```

15. knight_tour(movelist[i].row,
movelist[i].col)
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?

i know i don't know much but pls give a hand.

thnx