Knight Tour using backtracking

Question

I am developing a program for knight tour in c++ using backtracking Here is my code:

#include <iostream>
#include <iomanip>
using namespace std;

template <class T>
class Stack
{
public:
    Stack(int len = 100)
    {
        length = len;
        sp = -1;
        a = new T [length];
    }

    int getLength()
    {
        return length;
    }

    void push(T v)
    {
        if(isFull())
        {
            throw std::exception("Stack Overflow!");
            return;
        }
        a[++sp] = v;
    }
    bool isFull()
    {
        if(sp < getLength()-1)
            return false;
        return true;
    }
    T pop()
    {
        if(isEmpty())
        {
            throw std::exception("Stack Underflow!");
        }
        return a[sp--];
    }
    bool isEmpty()
    {
        if(sp == -1)
            return true;
        return false;
    }
    T getTop()
    {
        if(isEmpty())
        {
            throw std::exception("Stack Underflow!");
        }
        return a[sp];
    }

private:
    T * a;
    int sp;
    int length;

};

class MoveStk
{
public:
    MoveStk()
    {
        set(0,0,0);
    }

    MoveStk(int r , int c , int d)
    {
        set(r,c,d);
    }

    void set(int r , int c , int d)
    {
        row = r;
        col = c;
        dir = d;
    }

    void get(int& r , int & c , int & d)
    {
        r = row;
        c = col;
        d = dir;
    }

private:
    int row , col , dir;
};

class Position
{
public:
    int x , y;
    Position(int i = 0 , int j = 0)
    {
        x = i;
        y = j;
    }
};


bool move(Position pos[],int posLen,int ** chess ,int n, int col, int row , int&newRow , int & newCol , int moveNo )
{
    if (row+pos[moveNo].x>=0 && row+pos[moveNo].x<n && col+pos[moveNo].y>=0 && col+pos[moveNo].y<n && chess[row+pos[moveNo].x][col+pos[moveNo].y] == 0 )
    {
        newRow = row+pos[moveNo].x;
        newCol = col+pos[moveNo].y;
        return true;
    }
    return false;
}

int main()
{

    int n = 8;

    //create stack
    Stack<MoveStk> myStack(100);



    //create dynamic array
    int ** chess = new int* [n];
    for (int i = 0; i < n; i++)
        chess[i] = new int[n];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            chess[i][j] = 0;

    //setup moves
    Position pos[8];

    pos[0] = Position(-2,1);
    pos[1] = Position(-2,-1);
    pos[2] = Position(2,1);
    pos[3] = Position(2,-1);
    pos[4] = Position(-1,-2);
    pos[5] = Position(-1,2);
    pos[6] = Position(1,2);
    pos[7] = Position(1,-2);


    //input for start (must be optional) :
    int row = 4;
    int col = 3;


    int count = 1 , moveChoose = 0;
    int newCol , newRow;

    MoveStk temp(row,col,0);//adding first move to stack
    myStack.push(temp);

    chess[row][col] = count;

    while(count<=(n*n) && !myStack.isEmpty())
    {
        temp = myStack.getTop();
        temp.set(row,col,moveChoose);

        while(moveChoose<8 && !move(pos,8,chess,n,col,row,newRow,newCol,moveChoose))//avalin khoone azad baray karkat
        {
            moveChoose++;
        }

        if(moveChoose != 8)//there is somewhere we can go
        {
            myStack.pop();
            temp.set(col,row,moveChoose+1);//adding next possible move for returning back
            myStack.push(temp);
            chess[newRow][newCol] = ++count;
            temp.set(newRow,newCol,0);
            myStack.push(temp);
        }
        else//we must return
        {
            myStack.pop();
            chess[newRow][newCol] = 0;
            count--;
        }

    }

    printArray(chess);

    cin.ignore();
    cin.get();
}

The problem is , this app only works for first moves and my stack gets empty before ending game. I can't find where is wrong?!

What can the problem be?

Answer 1

First, I think you need to change the lines:

while(count<=(n*n) && !myStack.isEmpty())
{
    temp = myStack.getTop();
    temp.set(row,col,moveChoose);

To:

while(count<=(n*n) && !myStack.isEmpty())
{
    temp = myStack.getTop();
    temp.get(row,col,moveChoose);

As it currently stands, you are over-writing the last move and position every time through the loop. What you should be doing is start from where you left off by trying the next move from the previous position.

Also, I noticed you had the parameters wrong to the set call later:

        temp.set(col,row,moveChoose+1);//adding next possible move for returning back

It should be row then col.