1. ## Knight's Tour - need help

Hi,

My program's suppose to move the knight around the chess board touching the each square only once. It's starting off at (0, 0) and there are eight possible moves for the knight depending on its position. The program tests each potential move and if that move is not off the board or it has been visited yet then that move is made. However my program's output only say that the knight make 8 moves. i tried out by hand and it's sure more than that. Pls help , what's wrong ?

thnx

Code:
```/* Knight's Tour */

#include <stdio.h>

int main()
{
int board[ 8 ][ 8 ] = { 0 };                 /* Chess board */
int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int totalMoves = 0;                      /* Total of all moves made */
int currentRow = 0, currentColumn = 0;   /* Current position of knight */
int moveNumber;                          /* Move type */
int i, j;                                /* Loop counters */
int newPos;                              /* Test next possible move for validity */
int tryNextMoveType = 0;                        /* Flag to see if try next move number */
int end = 0;

while ( end != 1 ) {

moveNumber = 0;

for ( i = 0; i <= 7; i++ ) {

tryNextMoveType = 0;

newPos = currentRow + vertical[ moveNumber ];
if ( newPos < 0 || newPos > 7 )
tryNextMoveType = 1;

newPos = currentColumn + horizontal[ moveNumber ];
if ( newPos < 0 || newPos > 7 )
tryNextMoveType = 1;

if ( board[ currentRow + vertical[ moveNumber ] ][ currentColumn + horizontal[ moveNumber ] ] == 1 )
tryNextMoveType = 1;

if ( tryNextMoveType == 0 ) {
currentRow += vertical[ moveNumber ];
currentColumn += horizontal[ moveNumber ];
board[ currentRow ][ currentColumn ] = 1;
++totalMoves;
break;
}
else
moveNumber++;

if ( i == 7 && tryNextMoveType == 1 ) /* No more possible moves */
end = 1;
}
}

printf( "Total moves made by the knight: %d", totalMoves );

return 0;
}```

2. What a swell code example. Why did you post it? Do you need help? Does it work? Do you want comments? Are you showing your coding prowess? What exactly?

Quzah.

3. Make your question more specific.

Anyway.. You will never know what happened after visiting your post -Thanks a lot.

4. I just want to know what's wrong with my program that keeps limiting the number of possible moves to eight, which should be more than that for sure.

thnx

5. I think the best way to do this is
to use recursion. I'll just use psudocode
as I don't want to solve it completly for
you.

int knight_tour(row, col, count)
if out_of_bounds(row, col) or position
is dirty then return failure.

else
make position dirty
check if count >= 64

call knight_tour with succesive
positions until one returns success.
if none returns success then
return failure.

6. thnx for the suggestion.

But can anyone tell me what is wrong with my original code that i keep getting the number of moves made is 8 which should be more than that?

thnx

7. Originally posted by Nutshell
I just want to know what's wrong with my program that keeps limiting the number of possible moves to eight, which should be more than that for sure.

thnx
In any position a knight has no more than 8 possible moves. Check it in chess Board.

8. I know. Sorry I think i have to make myself more clear. My program is suppose to move the knight so that it touches as many squares as possible ( max 64 ) while not re-visiting any square.

and my program doens't do that at the moment though i worked very hard to find out why. I need help.

Also, now, i don't even know if my program works or not. When i changed the currentRow to 3 and currentColumn to 4 in declaration i get 33 moves made by the knight. SO my another question can be: DOes my program achieve its purpose ?

thnx a lot

9. Eventually it's possible to have a sequence
of moves where the knight is trapped with only
used squares to hop onto. You automaticaly give up in that situation.

10. You will have to find a heuristic to make the
algorithm that I gave faster on a 8x8 board but I've been able to test it on a 5x5 board.
On 8x8 it just stands still

11. Now I got the point..
I have to study your code more for details.

But pseudo is

get_possible_positions();
check_if_not_traveled_and_empty();
do_it_intill_get_new_possition();

if (got_one) { go_there(); turn_on_flag; do_it_again(new_position); }

if(end_of_possible_positions) break;

Little complicated to explain within few lines... I guess you have got the idea.

I'm not sure if you can visit all over(64) the board this way (Without visiting second time)....

Yeah.. you can not do that if you include that rule.

12. Originally posted by Nick
Eventually it's possible to have a sequence
of moves where the knight is trapped with only
used squares to hop onto. You automaticaly give up in that situation.
isn't that good ? I mean, isn't that what my program's suppose to do ?

but when i tried it by hand on a piece of paper i can have more than eight moves if i start on row 0 and column 0. How come?

thnx

13. ## Is it your goal to create a chess engine?

Is it your goal to create a chess engine?
structure will help here.

But Class: Object is circling on my head.

14. sorry i havne't learnt up to that stage in my book yet...

15. SIgh. Now i took Zahid's advice and tried to re-write the program using recursive functions, which i'm not good at. Here is my code and it has compile errors and i bet it needs still need debugging even if it compiles successfully. Pls help out, before i learn how to do stuff myself i need somebody to give me examples. Pls help.

Code:
```/* Knight's Tour ( recursive version ) */

#include <stdio.h>

/* 'col' = column */

int knights_tour( int startingRow, int startingCol, int moveNumber ); /* 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()
{
printf( "***Knight's Tour***" );

knights_tour( 0, 0, 0 );

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 ][ 8 ] = { 0 };
/* 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;

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 + 1 ) + totalMoves;
}

}```