Need help with Knight's Tour recursion a

Forum

Forum
Beginners
Need help with Knight's Tour recursion a

Need help with Knight's Tour recursion assignment

Hey there.

I am almost out of the woods when it comes to this semester, but I have one last assignment I need to finish for my C++ class and it is the Knight's tour recursion assignment. Rather than just cheat and look at other's versions of the assignment and copy those(pff stupid move), I'd rather post my own version of the assignment in the works and ask how I can make it work the way it should. So here is the code for the header file, implementation, and test code:


class knightsTour
{
public:
	knightsTour(int size = 8);
	void startTour(int x, int y);
    void move(int x, int y);
	void print();

private:
	int boardSize;
	int board[50][50];

};

#include <iostream>
#include <iomanip>
#include "knightsTour.h"

using namespace std;

knightsTour::knightsTour(int size)
{
	boardSize = size;
	for(int i = 0; i < boardSize; i++)
		for(int j = 0; j < boardSize; j++)
			board[i][j] = 0;
}

void knightsTour::startTour(int x, int y)
{
    board[x][y] = 1;
    move(x,y);
}

void knightsTour::move(int x, int y)
{
    int targetX;
    int targetY;

        //Move 1 right, 2 down
            targetX = x+1;
            targetY = y-2;

        if (((x >= 0) && (x < boardSize)) || ((y >= 0) && (y < boardSize))){
            board[x][y]++;
            move(targetX,targetY);
        }
        else{
        //Move 2 right, 1 down
            targetX = x+2;
            targetY = y-1;
        }
        if (((x >= 0) && (x < boardSize)) || ((y >= 0) && (y < boardSize))){
            board[x][y]++;
            move(targetX,targetY);
        }
        else{
        //Move 2 right, 1 up
            targetX = x+2;
            targetY = y+1;
        }
        if (((x >= 0) && (x < boardSize)) || ((y >= 0) && (y < boardSize))){
            board[x][y]++;
            move(targetX,targetY);
        }
        else{
        //Move 1 right, 2 up
            targetX = x+1;
            targetY = y+2;
        }
        if (((x >= 0) && (x < boardSize)) || ((y >= 0) && (y < boardSize))){
            board[x][y]++;
            move(targetX,targetY);
        }
        else{
        //Move 1 left, 2 up
            targetX = x-1;
            targetY = y+2;
        }
        if (((x >= 0) && (x < boardSize)) || ((y >= 0) && (y < boardSize))){
            board[x][y]++;
            move(targetX,targetY);
        }
        else{
        //Move 2 left, 1 up
            targetX = x-2;
            targetY = y+1;
        }
        if (((x >= 0) && (x < boardSize)) || ((y >= 0) && (y < boardSize))){
            board[x][y]++;
            move(targetX,targetY);
        }
        else{
        //Move 2 left, 1 down
            targetX = x-2;
            targetY = y-1;
        }
        if (((x >= 0) && (x < boardSize)) || ((y >= 0) && (y < boardSize))){
            board[x][y]++;
            move(targetX,targetY);
        }
        else{
        //Move 1 left, 2 down
            targetX = x-1;
            targetY = y-2;
        }
    }


void knightsTour::print()
{
	for(int i = 0; i < boardSize; i++)
	{
		for(int j = 0; j < boardSize; j++)
			cout<<setw(4)<<board[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl<<endl;
}

//Chapter 6: Programing Exercise 18

#include <iostream>
#include "knightsTour.h"

using namespace std;

int main()
{
    int size = 0;
    int xStart;
    int yStart;

    cout << "Enter the board size: ";
    cin >> size;
    knightsTour knight(size);

    while(true)
    {
    cout << "Enter the knight's starting row position: ";
    cin >> xStart;

    cout << "Enter the knight's starting column position: ";
    cin >> yStart;

    if(((xStart > size) || (xStart < 0)) || ((yStart > size) || (yStart < 0)))
        cout << "ERROR: Starting positions coordinates must be less than " << size << "and greater than zero."  << endl;
    else
        knight.startTour(xStart, yStart);
        knight.print();
        break;
    }

}

So what the program is supposed to do is to allow the user to specify a chessboard size(doesnt have to be the standard chessboard size) and specify a starting point for the knight. The program is then supposed to create a path for the knight with squares labeled with the number of a move it makes. If an illegal move is made, then the program is to switch to another move and determine if it would be legal from the 8 possible moves a knight can make. The move switching sequence would be counterclockwise. So on a 5x5 board, with the knight starting on the uppermost left square, the knight's tour should go like this:

1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 28 3 12 23

This was from an example given to me by the professor. The program is supposed to print out a result similar to this one.

However, when I run my program, this is what I get:

Enter the board size: 5
Enter the knight's starting row position: 0
Enter the knight's starting column position: 0
   8    0    0    0    0
   0    0    0    0    0
   0    0    0    0    0
   0    0    0    0    0
   0    0    0    0    0



Process returned 0 (0x0)   execution time : 3.275 s
Press any key to continue.

So I'd like to know what exactly is causing this. This is rather confusing and rather than allow my brain to be twisted up in knots trying to figure out the root of the problem, I need some guidance. I don't know perhaps I could be making things more complicated with the way I am trying to do things here. Or I could indeed be on the right track, but I can't guarantee that unless I get the feedback I need.

cire (8284)

Ask yourself why there is an else on line 34. Then, ask yourself what the termination condition for move should be. At what point do you stop moving? What happens when move returns from a recursive call and the termination condition has not been met?

Terminus Est (21)

The if statements are meant to check if the move made does not exceed the board's size. If the if statement is true, then a value is assigned to the index that increases with each move and then the next move is made. The else statements represent move attempts. If the if statement returns false, then the else statement assigns a different possible move based on the 8 possible directions a knight can move.

But why shouldn't an else be on Line 34?

The moves should stop if there are no more legal moves that can be made but I don't know. Perhaps the way I am trying to do all this is all wrong but I am not sure why that is if so.

cire (8284)

The moves should stop if there are no more legal moves that can be made but I don't know.

There is that, but how do you indicate whether you were successful at completing the knight's tour (and are therefore finished completely) or failed at completing the knights tour (and need to continue in order to find a valid sequence of moves.)

But why shouldn't an else be on Line 34?

See above.

Terminus Est (21)

I don't really yet have such a method of doing this and I don't know how and where I should implement that. I was thinking somehow making the entire process stop on a successful move when the number of the knight's final position is exactly the same as the number of squares in the board. But I do not know how to implement that as I said.

Besides I am getting the feeling I am totally going about on this program the wrong way. To see how the move function was really working, I did a cout statement at the end of it printing out the board[x][y] array and when I ran it, I got this huge number salad consisting of a number that keeps increasing, followed by seven zeroes, yet at the end of the number salad, the number decreases all the way down to 8. This is a small snippet of how this looks like(I can't print the whole output as it would exceed the max length required for posts):

16401 0 0 0 0 0 0 0 16408 0 0 0 0 0 0 0 16415 2345 0 0 0 0 0 0 0 164
22 0 0 0 0 0 0 0 16429 0 0 0 0 0 0 0 16436 0 0 0 0 0 0 0 16443 0 0 0 0 0 0 0 164
50 0 0 0 0 0 0 0 16457 0 0 0 0 0 0 0 16464 2352 336 0 0 0 0 0 0 0 16471 0 0 0 0
0 0 0 16478 0 0 0 0 0 0 0 16485 0 0 0 0 0 0 0 16492 0 0 0 0 0 0 0 16499 0 0 0 0
0 0 0 16506 0 0 0 0 0 0 0 16513 2359 0 0 0 0 0 0 0 16520 0 0 0 0 0 0 0 16527 0 0
 0 0 0 0 0 16534 0 0 0 0 0 0 0 16541 0 0 0 0 0 0 0 16548 0 0 0 0 0 0 0 16555 0 0
 0 0 0 0 0 16562 2366 0 0 0 0 0 0 0 16569 0 0 0 0 0 0 0 16576 0 0 0 0 0 0 0 1658
3 0 0 0 0 0 0 0 16590 0 0 0 0 0 0 0 16597 0 0 0 0 0 0 0 16604 0 0 0 0 0 0 0 1661
1 2373 0 0 0 0 0 0 0 16618 0 0 0 0 0 0 0 16625 0 0 0 0 0 0 0 16632 0 0 0 0 0 0 0
 16639 0 0 0 0 0 0 0 16646 0 0 0 0 0 0 0 16653 0 0 0 0 0 0 0 16660 2380 0 0 0 0
0 0 0 16667 0 0 0 0 0 0 0 16674 0 0 0 0 0 0 0 16681 0 0 0 0 0 0 0 16688 0 0 0 0
0 0 0 16695 0 0 0 0 0 0 0 16702 0 0 0 0 0 0 0 16709 2387 0 0 0 0 0 0 0 16716 0 0
 0 0 0 0 0 16723 0 0 0 0 0 0 0 16730 0 0 0 0 0 0 0 16737 0 0 0 0 0 0 0 16744 0 0
 0 0 0 0 0 16751 0 0 0 0 0 0 0 16758 2394 0 0 0 0 0 0 0 16765 0 0 0 0 0 0 0 1677
2 0 0 0 0 0 0 0 16779 0 0 0 0 0 0 0 16786 0 0 0 0 0 0 0 16793 0 0 0 0 0 0 0 1680
0 0 0 0 0 0 0 0 16807 2401 343 49 8

Have you taken a closer look at my program and ran it yet?

This program is seriously frustrating to me and so far I am getting no helpful hint whatsoever.

Terminus Est (21)

Also, here's some pseudocode that the professor gave the class to assist us in this project.

move(x, y)
IF (x,y) is not a valid point to move into THEN
     return;
ENDIF
record (x,y) as the next point
if (all positions are covered)
       print the solution
       return;
 
From current position (x, y)
     for each potential target position  //there are 8 possibilities
          invoke move(targetx, targety)
 
erase Knight's visit to (x,y)
return

Before I started to work on this program, I tried to understand this algorithm but I could not make sense of it, so I went with the method I showed in the top post. Now I am thinking about trying out the algorithm in the pseudocode. But I don't quite get it. First of all, what exactly is supposed to be returned in the return statements?

heebleworp (66)

Look at what knightsTour::move() does (let x==0 and y==0 to start):

1) targetX set to 1
2) targetY set to -2
3) if test is valid (x>=0 and x < boardSize) //why are we checking x OR y instead of targetX AND targetY?
4) board[0][0] set to 2
5) pass targetX and targetY to move() //targetY is out of bounds but we aren't checking
6) //things just get worse

May be other problems, haven't checked. Note that when you print output and get goofy numbers/characters that usually indicates memory mismanagement of some kind, in this case leaving array bounds. Depending on the system and situation the program may even crash.

First of all, what exactly is supposed to be returned in the return statements?

Depends on how your function is written but probably nothing. Also maybe some additional comments in the pseudocode will help:

move(x, y) //you don't have to limit yourself to passing only two variables to move(), not strictly necessary though
IF (x,y) is not a valid point to move into THEN //does (x,y) lie in the board, or has it already been moved into?
     return;
ENDIF
record (x,y) as the next point //a third passed variable could be helpful here (again not strictly necessary)
if (all positions are covered) //and here
       print the solution
       return;
 
From current position (x, y)
     for each potential target position  //there are 8 possibilities
          invoke move(targetx, targety)
 
erase Knights visit to (x,y) //only get here if invoke move(targetx, targety) fails to come up with a solution for all possibilities
//to erase, reverts what you did to record (x,y) as the next point
return

Topic archived. No new replies allowed.