trouble with knights tour (recursion)

[blackdove]

I'm new to recursion and object oriented programming, but we have been assigned the knight's tour problem. This is where the knight's piece has to travel to every space on a chess board and land on each spot only once. I pretty much have my program done, except i'm having a small problem. My program runs fine, but when the board prints out, some of the spaces have the same "move" number in them. I can't figure out why this is happening. I'm thinking there may be a small problem in my recursion but i'm not really sure. I attached my code to the post(atleast i think i did). If anyone would take the time to go over it, I would greatly appreciate it. Thanks in advance for any help you can give.

[Alvein]

After some step-into's, I see your program backtracks well, but the "dead-ends" are not removed. Though it can move forward, the previous cells are not cleared, so it show duplicated numbers in the board.

Let's say the algorithm is ok, but the problem is C++ and the way you expect things work. You want to pass the whole board as a parameter. Though in a pseudo-code level this could create a new instance of the board on every recursive call (making possible to restore a previous instance with backtracking), in C/C++ you're not passing the board but a reference (pointer) to it. That means you're using only one instance, so the board won't be restored to a previous state when the program moves back. :sad:

Try boardType[row][column] = 0 in the last else just before "go back recursively".

[blackdove]

thanks for the reply.
Yes, i had noticed that and actually tried entering that line, but when i do it seems to go into an infinite loop and just keeps printing out the board.
I even tried entering the line where a validMove = false, but that only returned an empty board. I'm so lost :(

[RehabReda]

i have also a problem with this i am using backtracking but i don't know it doesn't work right it take alot of time it is an ACM problem here is the code please if anyone have any idea what is wrong in this code please inform

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Square
{
	int Row, IColumn;
	char Column;
}Source, Target;
int count1;
bool Visited[9][9];
vector<int> MinNumberOfKnightMoves;

int NRow[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int NColumn[] = {-1, 1, -2, 2, -2, 2, -1, 1};

bool isValid(int Row, int Column)
{
	return (Row > 0 && Row < 9 && Column > 0 && Column < 9);
}

void KnightMoves(int NumberOfMoves, int Row, int Column)
{
	

		if(NumberOfMoves==64)
			return;
		if(Row == Target.Row && Column == Target.IColumn)
		{
			MinNumberOfKnightMoves.push_back(NumberOfMoves);

			return;
		}
		
		
		
			for(int i = 0; i < 8; i ++)
			{
				if(isValid( Row + NRow[i], Column + NColumn[i]) && !Visited[ Row + NRow[i]][Column + NColumn[i]])
				{
				Visited[Row][Column] = true;
				
				KnightMoves(NumberOfMoves + 1, Row + NRow[i], Column + NColumn[i]);
				
				Visited[Row][Column] = false;
				}
			
		}
	
}

int main()
{
	
	string square;
	
	while(cin >> square)
	{	count1 =0;
		Source.Column = square[0];
		Source.IColumn = square[0] - 'a' + 1;
		Source.Row = square[1] - '0';
		
		cin >> square;
		
		Target.Column = square[0];
		Target.IColumn = square[0] - 'a' + 1;
		Target.Row = square[1] - '0';
		
		for(int i = 0; i < 9; i ++)
			for(int j = 0; j < 9; j ++)
				Visited[i][j] = false;
		
		KnightMoves(0, Source.Row, Source.IColumn);
		sort(MinNumberOfKnightMoves.begin(), MinNumberOfKnightMoves.end());
		
		cout << "To get from " << Source.Column << Source.Row << " to " 
		<< Target.Column << Target.Row <<" takes "
		<< MinNumberOfKnightMoves[0] << " knight moves." << endl;
		
		MinNumberOfKnightMoves.clear();
	}
	return 0;
}