Knight Tour с использованием возврата

Я разрабатываю программу для рыцарского тура в C ++ с использованием backtracking
Вот мой код:

#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();
}

Проблема в том, что это приложение работает только для первых ходов, а мой стек опустошается до окончания игры.
Я не могу найти, где не так ?!

В чем может быть проблема?

0

Решение

Во-первых, я думаю, что вам нужно изменить строки:

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

Для того, чтобы:

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

В настоящее время вы переписываете последний ход и позицию каждый раз в цикле. То, что вы должны сделать, это начать с того места, где вы остановились, попробовав следующий ход с предыдущей позиции.

Кроме того, я заметил, что вы неправильно указали параметры для вызова set:

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

Так должно быть row затем col,

2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector