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.
ds.eickhoff Newbie Poster
#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
- forum1 Reply
- 99 Views
- 12 Hours Discussion Span
- comment Latest Post by gashtio
gashtio 25
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.