
Jan 8th, 2002, 05:23 AM
#1
Thread Starter
Hyperactive Member
Problem with recursive solution of "Knight's Tour".
Hi,
I am working with the problem 'Knight's tour' and my program's meant to move the knight to as many squares as possible on a chess board while not revisiting any squares. Can anoyone be kind enough to make my code work or simply post a better and simpler solution. I mean, i cna't learning anything without seeing examples, and i'm really stuck. I also tried the iterative version and still could'nt get it to work. Pls help.
thnx in advance
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;
}
}

Jan 8th, 2002, 06:14 AM
#2
transcendental analytic
1. the board is local
2. moveNumber never gets incremented
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p xx==0=""True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

Jan 8th, 2002, 06:24 AM
#3
Thread Starter
Hyperactive Member
for the 'board', can i fix the problem by adding a 'board' argument in the knights_tour function? but what do u mean moveNumber is never incremented, why?
i am very new to c can you pls post a sample knights_tour function if possible?
how about this code?
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;
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 , board) + totalMoves;
}
}
Last edited by iflash; Jan 8th, 2002 at 06:32 AM.

Jan 8th, 2002, 08:24 AM
#4
Black Cat
Is this homework out of the Dietel & Dietel book? I've "helped" someone with this before and have several of the solutions, but I did it OO/C++ with a Knight class, and they didn't do OO in their class yet...
Josh
Get these: Mozilla Opera OpenBSD
I have books for sale: "MCSD in a Nutshell" and "VB Distributed Exam Cram"  PM me for details. Will also trade for a decent ATX Pentium 2 MB/CPU/RAM combo.

Jan 8th, 2002, 11:59 AM
#5
transcendental analytic
You can pass around board if you want, you can go functional all the way if you want but C++ is meant for object orientation. Don't you see what moveNumber not being incrementing means? I suppose you had an idea to start with otherways you wouldn't have come this far, maybe you've left this project for a good while like a half year or so?
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p xx==0=""True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

Jan 8th, 2002, 10:58 PM
#6
Thread Starter
Hyperactive Member
Yes this problem is from the deitel book of C: How to Program.
IF possible i really need help with a recursive solution, i've already worked out the iterative solution yesterday.
thnx

Jan 9th, 2002, 09:40 AM
#7
Black Cat
Which is the recursive part? Its been a while, and I don't have the book anymore.
Josh
Get these: Mozilla Opera OpenBSD
I have books for sale: "MCSD in a Nutshell" and "VB Distributed Exam Cram"  PM me for details. Will also trade for a decent ATX Pentium 2 MB/CPU/RAM combo.

Jan 9th, 2002, 10:07 AM
#8
transcendental analytic
last line, recursion means: call itself
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p xx==0=""True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
Survey posted by VBForums.
