| |
/*
Filename: knight2.cpp
Author : Nuno Alves (nca@bu.edu)
The purpose of this program is to output a solution for the knights tour
problem in a 8x8 chessboard. One requirement of the assignment was to
solve it using a stack, instead of recursivity.
Here's the problem: From an arbitrary starting position, move a standard
Knight chess piece around a chess board visiting all other squares on the
board exactly once.
Note: The program works perfectly... For the 8x8 board, and with first piece
at location (7,0), it takes about 1 minute.
*/
#include <iostream>
#include <iomanip>
using namespace std;
const int size = 8; //number of rows/columns of the board
//position class will contain the objects that correspond to the
//moves of the bishop in the board
//
// position(int x=0, int y=0) -> object constructor
// int getrow() const -> gets the row value of the object
// int getcol() const -> gets the col value of the object
// int getlast_mov() const -> gets the last bishop movement
// void setlast_mov(int l_mov) -> sets the last bishop movement
class position {
public:
position(int x=0, int y=0) {row = x; col = y;}
int getrow() const {return row;}
int getcol() const {return col;}
int getlast_mov() const {return last_mov;}
void setlast_mov(int l_mov){last_mov=l_mov;}
private:
int row;
int col;
int last_mov;
};
template< class T >
class Stack {
public:
Stack( int SIZE = size*size ); // default constructor (stack size 10)
~Stack() { delete [] stackPtr; } // destructor
bool push( const T& ); // push an element onto the stack
bool pop( T& ); // pop an element off the stack
int getsize() const {return SIZE;}
bool isEmpty() const { return top == -1; } // utility
bool isFull() const { return top == SIZE - 1; } // functions
private:
int SIZE; // # of elements in the stack
int top; // location of the top element
T *stackPtr; // pointer to the stack
};
// Constructor with default size size*size
template< class T >
Stack< T >::Stack( int s )
{
SIZE = s > 0 ? s : size*size;
top = -1; // Stack is initially empty
stackPtr = new T[ SIZE ]; // allocate space for elements
}
// Push an element onto the stack
// return 1 if successful, 0 otherwise
template< class T >
bool Stack< T >::push( const T &pushValue )
{
if ( !isFull() ) {
stackPtr[ ++top ] = pushValue; // place item in Stack
return true; // push successful
}
return false; // push unsuccessful
}
// Pop an element off the stack
template< class T >
bool Stack< T >::pop( T &popValue )
{
if ( !isEmpty() ) {
popValue = stackPtr[ top-- ]; // remove item from Stack
return true; // pop successful
}
return false; // pop unsuccessful
}
void print_board(int[][size]);
bool can_move(int,int,int,int,int[][size]);
void move_b(int,int,int,int,int[][size],int);
position update_stack(int x_pos, int y_pos, int last_mov);
void main(){
int x_pos,y_pos;
//reseting the board
int board[size][size]={0};
//this array will contain the table for all 8 possible
//bishop moves. For example, move 0 is x=x+1 & y=y+2.
//Each two digits is a move (array row).
//(+1,+2) is move 0
//(+2,+1) is move 1
//...and so on
int move[8][2]={1,2, 2,1, 2,-1, 1,-2, -1,-2, -2,-1, -2,1, -1,2};
do
{
cout<<"\nEnter an initial position for the knight's tour: ";
cin>>x_pos>>y_pos;
} while ((x_pos<0)||(x_pos>=size)||(y_pos<0)||(y_pos>=size));
int last_mov=0;
//knights object created with the initial position
//and with the last_movement (0-7) variable updated
position knights(x_pos,y_pos);
knights.setlast_mov(last_mov);
move_b(x_pos,y_pos,0,0,board,0); //moves it into the board
Stack <position> knight_stack(size*size); //initializes stack
knight_stack.push(knights); //pushes initial value into the stack
bool exit_loop=false; //exit the loop variable
//keep looping while the stack is empty (no solution was found) or
//until the stack is full (a solution was found).
//
//note: the stack contains exactly the number of possible board
//squares. If its a 4x4 board then the maximum stack size is 16.
while ((knight_stack.isEmpty()==false) && (knight_stack.isFull()==false))
{
exit_loop=false;
//the last_mov is the last movemenent of the knight. If it is
//equal to 1, then the last movement of the knight was (according
//to the move[][] array) it was x=x+2 and y=y+1.
for (;exit_loop==false;last_mov++)
{
// if the current move array offers a valid move:
// 1 - move the knight in the board
// 2 - get the new position of x and y
// 3 - push the element into the stack
// 4 - exits the loop and resets the last_mov variable,
// so the next knight jump starts at move 0.
if (last_mov<8)
{
if (can_move(x_pos,y_pos,move[last_mov][0],move[last_mov][1],board))
{
move_b(x_pos,y_pos,move[last_mov][0],move[last_mov][1],board,0);
x_pos=x_pos+move[last_mov][0];
y_pos=y_pos+move[last_mov][1];
knight_stack.push(update_stack(x_pos,y_pos,last_mov));
last_mov=-1;
exit_loop=true;
}
}
//if the current move array isnt a valid move:
//1 - pop the last element of the stack
//2 - checks to see which was the knigths last move
//3 - removes the last position from the board
//4 - gets a new x and y position
//5 - and increments the last movement (so we can see
// if the next move is a possible one)
else
{
knight_stack.pop(knights);
last_mov=knights.getlast_mov();
x_pos=knights.getrow();
y_pos=knights.getcol();
move_b(x_pos,y_pos,move[last_mov][0],move[last_mov][1],board,1);
x_pos=x_pos-move[last_mov][0];
y_pos=y_pos-move[last_mov][1];
last_mov++;
exit_loop=true;
}
}
} //end of testing loop
//if the stack is empty, then it means that there are no solutions
//on the other hand if the stack is full... then we have a solution
if (knight_stack.isEmpty()==true)
cout<<"There are no solutions for the proposed problem... \n";
if (knight_stack.isFull()==true)
print_board(board);
}//end of main
//this function creates a new object from the function inputs and
//returns it (the object). This is used when a new value is to
//be inserted into the stack.
position update_stack(int x_pos, int y_pos, int last_mov)
{
position knights(x_pos,y_pos);
knights.setlast_mov(last_mov);
return (knights);
}
//print_board function prints out the board to the screen
void print_board(int board[][size])
{
cout<<"Here is one possible solution for the knights tour:\n";
for (int i=0;i!=size;i++)
{
for (int k=0;k!=size;k++)
{
cout<<setw(3)<<board[i][k];
}
cout<<"\n";
}
}
//can_move function reports if the bishop can move from
//one location to another.
bool can_move(int x,int y,int delta_x,int delta_y,int board[][size])
{
//checks if displacement is out of boundries
if (((x+delta_x)>=size)||((x+delta_x)<0)||((y+delta_y)<0)||((y+delta_y)>=size))
return(false);
//checks if position has already been taken
if (board[x+delta_x][y+delta_y]!=0)
return(false);
return(true);
}
//move function moves the bishop to the new position and
//updates the gameboard. If erase is 1, then we are in 'erase the last
//movement' mode. If erase is 0, then we are in 'move piece' mode.
void move_b(int x,int y,int delta_x,int delta_y,int board[][size],int erase){
//erase the last movement
if (erase==1)
{
//goes back to the older place
board[x-delta_x][y-delta_y]=board[x][y]-1;
//remove last position from stack
//and puts a 0 (which mean unvisited) in the current location
board[x][y]=0;
}
else
{
//add one more visited place
board[x+delta_x][y+delta_y]=board[x][y]+1;
}
//adds this position to stack
position knights(x+delta_x,y+delta_y);
}
|