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