Member Avatar for 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.

#include <iostream.h>

const maxSize=20;
int boardType[maxSize][maxSize];

class knightTour {
  //Handles logic problem of Knight's tour
  //Maximum board size 20x20
public:
	void initialize(int boardType[maxSize][maxSize], int size);
	bool validMove(const boardType[maxSize][maxSize], int size, int row, int column);
	void prBoard(const boardType[maxSize][maxSize], int size);
	bool knightRecur(int boardType[maxSize][maxSize], int size, int row, int column, int moves);
};//class knightTour

void main(){
	knightTour check;
	int row, col, size;
  
	cout<< "Enter in a board size." << endl;
	cin >> size;
	cout<<"Enter the board location you wish to test:"<<endl;
	cout<<"Board row number: "<<endl;
	cin>>row;
	row-=1;
	cout<<endl;
	cout<<"Board column number: ";
	cin>>col;
	col-=1;
	cout<<endl;

	check.initialize(boardType, size);
	check.knightRecur(boardType, size, row, col, 1);

}

void knightTour::initialize(int boardType[maxSize][maxSize], int size)
{
	for (int row=0; row < size; row++)
	{
		for (int column=0; column < size; column++)
			boardType[row][column] = 0;
	}
}

bool knightTour::validMove(const boardType[maxSize][maxSize], int size, int row, int column)
{//checks to see if a move is valid
	if((row  >= size) || (row  < 0) || (column  >= size) || (column  < 0))
		return false;//checks to see if move falls off the board
	if(boardType[row][column] == 0)
		return true;//if position is marked with 0, the move is okay.
	else
		return false;//spot is already taken
}//bool validMove

void knightTour::prBoard(const boardType[maxSize][maxSize], int size)
{	
// outputs a board with knight moves
// Pre: size <= MAXSIZE
	int temp, col, row;

	// output top of grid
	cout <<"\n+";
	for (temp = 0; temp < size; ++temp)
		cout <<"----+";
	cout <<endl;

	for (row = 0; row < size; ++row) 
	{
		for (col = 0; col < size; ++col)	 // do one row
			if (boardType[row][col] != 0)	// print the move number
				cout <<"| " << boardType[row][col] << " ";
			else
				cout <<"|   ";
    	cout <<"|\n+";		// grid between rows
		for (temp=  0; temp < size; ++temp)
			cout <<"----+";
		cout <<endl;
	} // for
	cout <<endl;
}//void prBoard


bool knightTour::knightRecur(int boardType[maxSize][maxSize], int size, int row, int column, int moves)
{
	knightTour game;
	game.prBoard(boardType, size);
	
	
	if(!game.validMove(boardType, size, row, column))//checks to see if move is valid
		return false;

	boardType[row][column] = moves;

	if (moves == (size * size))
		{ // then it has moved to ALL the spaces
			game.prBoard(boardType, size);	
			return true;
		}//if

	else // recursion
		{ // tries each possible move for the knight 			
			if (knightRecur(boardType, size, row+2, column+1, moves+1))
				return true;
			else if (knightRecur(boardType, size, row+2, column-1, moves+1))	
				return true;
			else if (knightRecur(boardType, size, row-2, column+1, moves+1))
				return true;
			else if (knightRecur(boardType, size, row-2, column-1, moves+1))
				return true;
			else if (knightRecur(boardType, size, row+1, column+2, moves+1))
				return true;
			else if (knightRecur(boardType, size, row+1, column-2, moves+1))
				return true;
			else if (knightRecur(boardType, size, row-1, column+2, moves+1))
				return true;
			else if (knightRecur(boardType, size, row-1, column-2, moves+1))
				return true;
			else // if no moves work then go back recursively		
				return false;
	
	}//else	

}//bool knightRecur
  • 3 Contributors
  • 3 Replies
  • 2K Views
  • 4 Years Discussion Span
  • Latest Post Latest Post by RehabReda

Dani AI

Generated

You are seeing duplicate move numbers because the board is a single shared object across all recursive calls. Arrays decay to pointers in C/C++, so when you pass the board you are passing a reference to the same memory. As noted, you must undo the move when backtracking. A simple, reliable pattern is: check bounds/unvisited, place the move, recurse, and if it fails, remove the move before trying the next option. Also, return a bool so you can stop as soon as a full tour is found and print only once.

// 0 means unvisited. step starts at 1.
bool tour(int r, int c, int step, int N, int board[8][8]) {
    if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] != 0) return false;

    board[r][c] = step;                  // place move
    if (step == N * N) return true;      // solved

    static const int dr[8] = { 2, 1,-1,-2,-2,-1, 1, 2 };
    static const int dc[8] = { 1, 2, 2, 1,-1,-2,-2,-1 };
    for (int k = 0; k < 8; ++k) {
        if (tour(r + dr[k], c + dc[k], step + 1, N, board))
            return true;                 // bubble success up
    }

    board[r][c] = 0;                     // undo on backtrack
    return false;
}

If adding board[row][col] = 0 caused an infinite loop for you, common culprits are: printing the board inside the recursion (you will print on every backtrack), not short-circuiting after a solution is found (keep exploring and overwrite), or clearing the wrong cell (undo the same cell you set). Quick checks: base case should be step == N*N; guard checks must happen before placing the move; and only print when tour(...) returns true.

For : if you need the minimum number of knight moves between two squares, use BFS on the 8x8 grid rather than backtracking. BFS with a dist[8][8] array finds the shortest path in O(64) time. If you still use DFS, mark the cell you enter at function start (Visited[r][c] = true) and unmark it before returning, or you will revisit nodes and blow up the search.

Recommended Answers

All 3 Replies

Member Avatar for 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".

Member Avatar for 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 :(

Member Avatar for 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 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;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.