Member Avatar for ds.eickhoff

I am new to this site, but is there anyone out there who could point me in a different direction. I am trying to get the "Knights Tour" to work. The issue that I am having is that it seems to print several number twice.

#include <iostream>
using namespace std;

int 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(int boardType[maxSize][maxSize], int size, int row, int column);
	void prBoard(int boardType[maxSize][maxSize], int size);
	bool knightRecur(int boardType[maxSize][maxSize], int size, int row, int column, int moves);
};//class knightTour

int main()
{
	knightTour check;
	int row, col, size;
    
	cout << "\nChapter7, Problem 7.24,Programmed By David Eickhoff\n";
	cout << "\nWelcome the the Knights Tour Simulation\n";
	cout<< "Please enter the size of board you want to try(with a max of "<< maxSize << ");"  << std::endl;
	cin >> size;
	cout<<"Enter the board location you wish to test" <<std::endl;
	cout<<std::endl;
	cout<<"Which row number will you like to start with: from 1- "<< size <<std::endl;
	cin>>row;
	row-=1;
	cout<<endl;
	cout<<"Which column number will you like to start with: from 1- "<< size <<std::endl;
	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(int 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(int 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)
{
	
	
	
	if(!knightTour::validMove(boardType, size, row, column))//checks to see if move is valid
		return false;
knightTour::prBoard(boardType, size);
	
	boardType[row][column] = moves;

	if (moves == (size * size))
		{ // then it has moved to ALL the spaces
			
			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(boardType[row][column] = 0 )
			//		return true;
		else 
			return false;

			
	
	}//else	

}//bool knightRecur
  • 2 Contributors
  • 1 Reply
  • 178 Views
  • 12 Hours Discussion Span
  • Latest Post Latest Post by gashtio
Member Avatar for gashtio

I didn't test it, but here are the problems I saw:

First, your bounds check is incorrect - if((row == size) || (row < 0) || (column > size) || (column < 0)) should be if((row >= size) || (row < 0) || (column >= size) || (column < 0)) Second, you aren't backtracking at all - you're just picking a single path and following it as far as possible. To correct that you have to replace all the [B]else[/B] if s in the "tries each possible move" block with just if s, and if all of them fail, return the current position's state to unused (0). In pseudocode that would be something like this:

function next_move(x, y, level)
    board[x][y] = level
    if(level == side*side)
        print solution
        return found
    
    for each possible move (u,v) from (x,y)
        next_move(u, v, level+1)

    board[x][y] = 0

Then just call next_move(startx, starty, 1) from the main procedure.


And last, using simple backtracking results in an exponential algorithm that will take ages even for the current maximum you've set (20). You should consider using Warnsdorf's heuristic (or simply put, the next square you choose is the one that has the least possible moves left) which will bring down the complexity to linear in the total number of squares.

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.