ifndef position
#ifndef POSITION
#define POSITION
class Position
{
protected:
int row,column;
public:
Position();
Position (int row, int column);
int getRow() const;
int getColumn() const;
int getnum_of_queen() const;
void setPosition(int newRow,int newColumn);
}; // class Position
#endif
#ifndef BACKTRACK
#define BACKTRACK
#include "Application.h"; #include "Position.h";
class BackTrack
{
public:
BackTrack (const Application& app);
bool tryToSolve (Position pos);
protected:
Application app; }; // class BackTrack
#endif
#ifndef APPLICATION
#define APPLICATION
#include
#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;
// Postcondition: pos has been marked as not being on the path to
// a goal.
void undo (const Position& pos);
class Iterator
{
protected:
void* fieldPtr;
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();
}; // class Iterator
}; // class Application
#endif
///主要部分
#include "Application.h" #include "Position.h" #include
#include
#include
const short QUEEN= 9; const short ROWS = 8; const short COLUMNS = 8; const short TRIED = 2; short ChessBoard[8][8]; short NUM_OF_QUEEN=0;
//int newRow=0;
Position start;
using namespace std;
struct itrFields
{
int row,column,direction_x,direction_y;
};//itrFields
Position Application::generateInitialState()
{
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
ChessBoard[i][j]=0;
cout<>row>>column;
start.setPosition (row-1, column-1);
cout<8||pos.getRow()+1<1||pos.getColumn()+1>8||
pos.getColumn()+1<1)
flag=false;
if(flag)
for(int i=0;i<8;i++)
{
if(i==pos.getColumn()) continue;
if(ChessBoard[pos.getRow()][i]==9) {flag=false;break;}
}//检查横行是否有皇后
if(flag)
for(int j=0;j<8;j++)
{
if(j==pos.getRow()) continue;
if(ChessBoard[j][pos.getColumn()]==9) {flag=false;break;}
}//检查竖行是否有皇后
if(flag)
for(int r=0;r<8;r++)
{
for(int c=0;c<8;c++)
{
if(r==pos.getRow()&&c==pos.getColumn()) continue;
if(abs(r-pos.getRow())==abs(c-pos.getColumn()))
{
if(ChessBoard[r][c]==9) {flag=false;break;}
}
}
if(!flag) break;
}//检查左斜，右斜有没有皇后
// if(flag) newRow++;
return flag;
}
//标记皇后
void Application::record(const Position& pos) {
ChessBoard[pos.getRow()][pos.getColumn()]=QUEEN;
NUM_OF_QUEEN++;
}
// 判断八个皇后是否已经都摆上
bool Application::done () const
{
// cout<row=pos.getRow();
itrPtr->column=pos.getColumn();
itrPtr->direction_x=pos.getRow();
itrPtr->direction_y=0;
fieldPtr=itrPtr;
}//constructor
Position Application::Iterator::operator ++(int)
{
itrFields* itrPtr=(itrFields*)fieldPtr;
int nextRow = itrPtr -> row,
nextColumn = itrPtr -> column;
switch(itrPtr->direction_x)
{
case 0:nextRow=0;break;
case 1:nextRow=1;break;
case 2:nextRow=2;break;
case 3:nextRow=3;break;
case 4:nextRow=4;break;
case 5:nextRow=5;break;
case 6:nextRow=6;break;
case 7:nextRow=7;break;
}
switch(itrPtr -> direction_y++)
{
case 0:nextColumn=0;break;
case 1:nextColumn=1;break;
case 2:nextColumn=2;break;
case 3:nextColumn=3;break;
case 4:nextColumn=4;break;
case 5:nextColumn=5;break;
case 6:nextColumn=6;break;
case 7:nextColumn=7;break;
}
//cout<direction_x>7||
((itrFields*)fieldPtr)->direction_y>7)
return true;
return false;
}
#include "Position.h"
Position::Position()
{
row = 0;
column = 0;
} // default constructor
Position::Position (int row, int column)
{
this -> row = row;
this -> column = column; } // constructor
void Position::setPosition(int newRow,int newColumn)
{
this->row=newRow;
this->column=newColumn; }
int Position::getRow() const {
return row;
} // method getRow()
int Position::getColumn() const
{
return column;
} // method getColumn()
#include
#include
#include "BackTrack.h" #include "Application.h" #include "Position.h"
using namespace std;
int main()
{
Application app;
BackTrack b(app);
cout<<"初始化棋盘:\n";
Position start=app.generateInitialState();
if(!app.valid(start))
cout<<"您的输入有误～"< 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 ())
success = true;
else
{
success = tryToSolve (pos);
//if(!success) cout<<1;
if (!success)
{
app.undo(pos);
}
} // not done
}
} // while
return success;
} // method tryToSolve
浙公网安备 33021202002483