алгоритм — Knight’s Tour C ++ с использованием стека
В настоящее время я работаю над игрой на шахматной доске Knight Tour на c ++, используя Stack для хранения своего хода. Я сталкиваюсь со странным циклом, который не завершает программу. Кто-нибудь может мне помочь с кодом?
#include <iostream>
#include <stack>
#include <map>
#include <cstdlib>
using namespace std;
struct whereIam
{
int row, col;
};
struct L_shape_pattern
{
int Lrow[8]={1,1,2,2,-1,-1,-2,-2};
int Lcol[8]={2,-2,1,-1,2,-2,1,-1};};
bool check_if_valid(int row, int col)
{
if ((row >= 0 && col >= 0) && (row < 8 && col < 8))
{
// cout << "here in valid " <<endl;
return true ;
}
else
return false;
}
bool check_empty(bool board[8][8], whereIam position)
{
// if (board[position.row][position.col] == false)
// return false;
// else
// return true;
if (board[position.row][position.col] == true)
{
// cout << "here in check empty" <<endl;
return true;
}
else
return false;
}
bool isReady(whereIam &position,bool board[8][8])
{
// cout << "here" << endl;
int ready = 0;
for (int i = 0 ; i < 8 ; i ++)
{
for (int j = 0 ; j < 8 ; j++)
{
if(board[i][j] == false)
{
ready += 1;
}
}
}
cout << "ready: " <<ready << endl;
if (ready == 64)
{
cout << "done" << endl;
return true;
}
else
return false;
}
void findspot(whereIam &position,bool board[8][8], stack<whereIam> &sequence)
{
L_shape_pattern Lshape;
// stack<whereIam> initial;
stack<int> counter;for (int j = 0 ; j< 9 ;j++)
{
//nothing is assign here
if (check_if_valid(position.row+Lshape.Lrow[j],position.col+Lshape.Lcol[j]) /*&& check_empty(board,position)*/)
{
// cout << "here in valid in spot " <<endl;
whereIam hello;
hello.row = position.row+Lshape.Lrow[j];
hello.col = position.col+Lshape.Lcol[j];
// cout << hello.row << " " << hello.col << endl;
if (check_empty(board,hello))
{
// cout << "here in empty" <<endl;
// int possible_row = position.row+Lshape.Lrow[j];
// int possible_col = position.col+Lshape.Lcol[j];
// position.row = possible_row;
// position.col = possible_col;
position.row = hello.row;
position.col = hello.col;
sequence.push(position);
// initial.push(position);
// cout << position.row << " " << position.col << endl;
counter.push(j);
board[position.row][position.col] = false;
j = -1;
if (isReady(position,board) == true)
{
cout << "in if ready" << endl;
exit(0);
}}}
if (j == 8 )
{
// cout << "here in j = 8" <<endl;
board[position.row][position.col] = true;
// cout << " pop board " << position.row <<" " << position.col << endl;
sequence.pop();
position = sequence.top();
// increment to the position where it need to be backtracking and it increment by one
j = counter.top();
counter.pop();
if (isReady(position,board) == true)
{
cout << "in if ready" << endl;
exit(0);
}
}}}
//bool movetheKnight(whereIam &position,bool board[8][8], stack<whereIam> &sequence)
//{
//}
void open_all_spot( bool board[8][8])
{
for (int i = 0 ; i< 8 ; i++)
for (int j= 0 ; j <8 ; j++)
{
board[i][j] = true;
}
}
int main()
{
bool board[8][8];
open_all_spot(board);whereIam position;
stack<whereIam> sequence;
cout << "Enter the initial position" << endl;
cout << "row : " ;
cin >> position.row;
cout << "column:";
cin >> position.col;
sequence.push(position);
//assign the initial position to be occupied already
board[position.row][position.col] = false;
findspot(position,board,sequence);
cout << "here end all" << endl;
return 0;
}
Некоторую часть, которую я только что создал, для отладки и просмотра работы каждой функции, так что игнорируйте эту часть.
Цикл всегда продолжается и, кажется, никогда не заканчивается. Я пытался отслеживать данные в стеке, но мне это кажется разумным.
Любая помощь будет оценена.
Решение
Когда вы смотрите на эту часть вашего кода:
for ( int j = 0; j < 9; j++ ) {
if ( check_if_valid(position.row+Lshape.Lrow[j],position.col+Lshape.Lcol[j]) /*&& check_empty(board,position)*/) {
// code...
if ( checkEmpty( board, hello ) {
// code...
j = -1;
if ( isReady(position, board) == true ) { // == true not needed
// code...
}
}
}
if ( j == 8 ) {
// code...
j = counter.top()
// code...
if ( isReady(position, board) == true ) { // == true not needed
// code...
}
}
} // for loop
Подумайте о том, что происходит в 1улица вложенный оператор if внутри цикла for, когда условие возвращается true. Вы меняете j быть -1,
Опять в 2й оператор if внутри цикла if j==8 ты снова меняешься j быть counter.top(),
Такое поведение приведет к бесконечной рекурсии цикла for. Вот простой пример:
#include <iostream>
#include <iomanip>
int main() {
int counter = 0;
for ( int i = 0; i < 5; i++ ) {
if ( i == 4 ) {
i = 0;
}
++counter;
std::cout << "Count the recursion: "<< std::setw( 2 ) << counter << " " << i << '\n';
// just to stop the recursion
if ( counter == 10 ) break;
}
std::cout << "\nPress any key and enter to quit.\n";
std::cin.get();
return 0;
}
Вышеуказанная программа без последнего if Заявление будет имитировать то, что происходит в вашей программе. Я включил это только для того, чтобы остановить цикл, чтобы показать прогрессию вывода.
Я не знаю, намеренно ли вы хотите бесконечную рекурсию цикла for или нет; но если вам нужно, вам нужно проверить переменные счетчика в отладчике, чтобы убедиться, что они соответствуют значению, необходимому для выполнения оператора, участвующего в выходе из цикла, чтобы остановить рекурсию. Так же, как я показал в моем маленьком примере выше; без условия счетчика, равного 10, Цикл бы продолжался вечно.
В качестве примечания, если вы намерены иметь бесконечный цикл; обычно лучше структурировать их таким образом, чтобы было яснее, что вы намеревались сделать.
int counter = 0;
for ( ; ; ) {
++counter;
// do some work;
if ( counter == exit condition ) break;
}
или же
int counter = 0;
for ( ; ; ) {
// do some work;
if work above is valid
increment counter
else
break;
}
или вы можете использовать цикл while вместо
counter = some value
while ( true ) {
check counter for condition;
do some work
increment or set counter;
}
Другие решения
Других решений пока нет …