Help need in Knight's Tour

[GSTARRAW]

I've been trying to solve this problem,but I failed.I stuck in runtime.I checked my codes and algorithm many times,but I can't figure where the problem is.So I need help!These are my code.
[

//-------------------backTrack.h---------------------------------------------------//
#ifndef BACKTRACK
#define BACKTRACK

#include "Application.h"
#include "Position.h"

class BackTrack
{
    public:
        BackTrack (const Application& app);
        void tryToSolve(Position pos);
    protected:
        Application app;
};


#endif

//------------------------backTrack.cpp--------------------------------------//
#include <string>
#include <iostream>
#include"backTrack.h"

using namespace std;

BackTrack::BackTrack (const Application& app)
{
    this -> app = app;
} // constructor


bool BackTrack::tryToSolve (Position pos)
{
    bool success = false;
    
    Application::Iterator itr(pos);
    while (!success && !itr.atEnd())
    {
        pos = itr++;
        if (app.valid (pos))
        {
            app.record (pos);
            if (app.done (pos))
                success = true;
            else
            {
                success = tryToSolve (pos);
                if (!success)
                    app.undo (pos);
            } // not done
        } // a valid position
    } // while
    return success;
} // method tryToSolve

//-----------------------------------position.h------------------------------//
#ifndef POSITION
#define POSITION

#include <string>

using namespace std;

class Position
{
    public:

        // Postcondition: this Position has been initialized.
        Position();


        // Postcondition: this Position has been initialized from
        //                row and column.
        Position (int row, int column);


        // Postcondition: this Position has been initialized from
        //                row and column.
        void setPosition (int row, int column);


        // Postcondition: this Position's row has been returned.
        int getRow() const;


        // Postcondition: this Position's column has been returned.
        int getColumn() const;

    protected:
        int row,
            column;

}; // class Position


#endif

//----------------------position.cpp-----------------------//
#include "position.h"

Position::Position() {}


Position::Position (int row, int column)
{
    this -> row = row;
    this -> column = column;
} // 2-parameter constructor


void Position::setPosition (int row, int column)
{
    this -> row = row;
    this -> column = column;
} // method setPosition


int Position::getRow() const
{
    return row;
} // method getRow()


int Position::getColumn() const
{
    return column;
} // method getColumn()


//-----------------------------application.h---------------------//
#ifndef APPLICATION
#define APPLICATION

#include <iostream>
#include "position.h"

using namespace std;

class Application
{
    friend ostream& operator<< (ostream& stream, Application& app);
 

    public:

        // Postcondition: the initial state for this Application has been
        //                generated -- from input or assignments -- and
        //                the start position has been returned.
        Position generateInitialState();


        // Postcondition: true has been returned if pos can be on the path
        //                to a goal.  Otherwise, false has been returned.
        bool valid (const Position& pos);


        // Precondition: pos represents a valid position.
        // Postcondition: pos has been recorded as a valid position.
        void record (const Position& pos);


        // Postcondition: true has been returned if pos is the final
        //                position for this application.  Otherwise, false
        //                has been returned.
        bool done (const Position& pos);


        // Postcondition: pos has been marked as not being on the path to
        //                a goal.
        void undo (const Position& pos);

   

        
    class Iterator
    {
        public:

            // Postcondition: this Iterator has been initialized to
            //                iterate from pos.
            Iterator (const Position& pos);


            // Postcondition: the next position for this Iterator has
            //                been returned.
            Position operator++ (int);


            // Postcondition: this Iterator cannot iterate any further.
            bool atEnd();

        protected:
        		void* fieldPtr;

        }; // class Iterator

}; // class Application


#endif

//------------------------kt.cpp----------------------------------//
#include <iostream>
#include"position.h"
#include"application.h"
#include<string>

const short ROWS = 8;

const short COLUMNS = 8;

short grid[ROWS][COLUMNS] =
{
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},    
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0}
}; // grid

int mc;


using namespace std;


Position Application::generateInitialState()
{
    const string START_PROMPT =
        "Please enter the start row and start column: ";

    int row,
        column;

    cout << START_PROMPT;
    cin >> row >> column;
    Position start(row,column);
    return start;
} // method generateInitialState


bool Application::valid (const Position& pos)
{
    if (pos.getRow() >= 0 && pos.getRow() < ROWS &&
            pos.getColumn() >= 0 && pos.getColumn() < COLUMNS && grid[pos.getRow()][pos.getColumn()]==0)
        return true;
    return false;
} // method valid


void Application::record (const Position& pos)
{   
    mc++;
    grid[pos.getRow()][pos.getColumn()] = mc;
} // method record


bool Application::done (const Position& pos)
{
    return mc==64;
} // method done


void Application::undo (const Position& pos)
{
    mc--;
    grid[pos.getRow()][pos.getColumn()] = 0;
} // method undo


ostream &operator<< (ostream &stream, Application& app)
{
    cout << endl;

    for (int row = 0; row < ROWS; row++)
    {
        for (int column = 0; column < COLUMNS; column++)
            cout << grid [row][column] << ' ';
        cout << endl;
    } // outer for
    return stream;
} // operator <<


struct itrFields
{
    int row,
        column,
        direction;
};


Application::Iterator::Iterator (const Position& pos)
{
    itrFields* itrPtr = new itrFields;
    itrPtr -> row = pos.getRow();
    itrPtr -> column = pos.getColumn();
    itrPtr -> direction = 0;
    fieldPtr = itrPtr;
} // constructor


Position Application::Iterator::operator++ (int)
{
    itrFields* itrPtr = (itrFields*)fieldPtr;
    int nextRow = itrPtr -> row,
        nextColumn = itrPtr -> column;
    switch (itrPtr -> direction++)
    {
        case 0: nextRow = itrPtr -> row - 2;
                nextColumn=itrPtr->column+1;
                break;
        case 1: nextRow=itrPtr->row-1;
                nextColumn = itrPtr -> column +2; 
                break;
        case 2: nextRow = itrPtr -> row + 1;
                nextColumn=itrPtr->column+2;
                break;
        case 3: nextRow=itrPtr->row+2;  
                nextColumn = itrPtr -> column +1;     
        case 4: nextRow = itrPtr -> row +2;
                nextColumn=itrPtr->column-1;
                break;
        case 5: nextRow=itrPtr->row+1;
                nextColumn = itrPtr -> column -2; 
                break;
        case 6: nextRow = itrPtr -> row -1;
                nextColumn=itrPtr->column-2;
                break;
        case 7: nextRow=itrPtr->row-2;  
                nextColumn = itrPtr -> column -1;     
                break;
    } // switch;
    Position next (nextRow, nextColumn);
    return next;
} // operator++ (int)


bool Application::Iterator::atEnd()
{
    return ((itrFields*)fieldPtr) -> direction >7;
} // method atEnd

//-------------------main.cpp-------------------------//
#include <iostream>
#include <string>
#include "backTrack.h"
#include "application.h"
#include "position.h"

using namespace std;

int main()
{
    Application app;
    Position start = app.generateInitialState();   
    BackTrack b (app);
    app.record (start);
    b.tryToSolve (start);           
    cout<<app<<endl;
    cin.get();
    return 0;
} // main

[zhelih]

Code is too big, it is hard to read. Say what you tried to do. And tried to debug it.

[GSTARRAW]

Code is too big, it is hard to read. Say what you tried to do. And tried to debug it.

I found no problem in my algorithm,it just can't print out the result.And my CUP occuption rate is high while at runtime as well ths memory.

[vijayan121]

> And my CPU occuption rate is high while at runtime as well the memory.
yes, using just backtracking alone can get computationally horrendous.
Warnsdorff's algorithm (goal programming) is easy to program and is very efficient. (does not work for very large boards).

Backtracking algorithms (in which the knight is allowed to move as far as possible until it comes to a blind alley, at which point it backs up some number of steps and then tries a different path) can be used to find knight's tours, but such methods can be very slow. Warnsdorff (1823) proposed an algorithm that finds a path without any backtracking by computing ratings for "successor" steps at each position. Here, successors of a position are those squares that have not yet been visited and can be reached by a single move from the given position. The rating is highest for the successor whose number of successors is least. In this way, squares tending to be isolated are visited first and therefore prevented from being isolated (Roth). The time needed for this algorithm grows roughly linearly with the number of squares of the chessboard, but unfortunately computer implementation show that this algorithm runs into blind alleys for chessboards bigger than 76 x 76, despite the fact that it works well on smaller boards (Roth).
Recently, Conrad et al. (1994) discovered another linear time algorithm and proved that it solves the Hamiltonian path problem for all n >= 5. The Conrad et al. algorithm works by decomposition of the chessboard into smaller chessboards (not necessarily square) for which explicit solutions are known. This algorithm is rather complicated because it has to deal with many special cases, but has been implemented in Mathematica by A. Roth.

-- http://mathworld.wolfram.com/KnightsTour.html