Knight’s Tour Brute Force Recursion
Я пытаюсь написать программу, которая позволяет пользователю вводить любые координаты на шахматной доске и завершать тур коня, используя рекурсию методом грубой силы. Я получаю бесконечный цикл, и я понятия не имею, почему. Это на C ++, и я должен написать это только с помощью грубой рекурсии. После ввода начальной позиции для рыцаря, мое окно вывода консоли печатает текущую доску после каждого хода (только временно, в целях устранения неполадок), но согласно моему выводу номер хода застрял в 1, и программа не пытается любые другие ходы. Любая помощь приветствуется.
#include "stdafx.h"#include <iostream>
#include <iomanip>
using namespace std;
void printBoard();
bool moveKnight(int col, int row, int movNum);int totalMoves = 0;
int board[7][7] = { { 0 } };int main()
{
cout << "Welcome to the Knight's Tour Program! Enter a starting place for the knight on a chess board to get started.\n";
int col;
int row;
int a;
int b;
while (1 == 1)
{
col = 0;
row = 0;
cout << "Enter column (0-7): ";
cin >> col;
cout << "Enter row (0-7): ";
cin >> row;
if (row < 0 || row > 7 || col < 0 || col > 7)
{
cout << "Invalid knight placement. Please try again.\n";
}
else
{
break;
}
}
int movNum = 1;
board[col][row] = movNum;
totalMoves++;
moveKnight(col, row, movNum);
if (moveKnight(col, row, movNum == true))
{
cout << "Tour finished! Total moves: " << totalMoves << endl;
printBoard();
cout << "\n\n";
}
system("pause");
return 0;
}void printBoard()
{
cout << "Current board\n";
for (int i = 0; i < 8; i++)
{
for (int x = 0; x < 8; x++)
{
cout << setw(3) << board[i][x] << " ";
if (x == 7)
{
cout << "\n\n";
}
}
}
cout << "\n";
}bool moveKnight(int col, int row, int movNum)
{
printBoard(); //just for troubleshooting
cout << "\n" << totalMoves << endl;
if (moveKnight(col, row, movNum) == false)
{
board[col][row] = 0; //if there are no available moves then set the current space to 0 and move back a spot
}
if (movNum == 64)
{
return true; //if tour complete return true
}
if (totalMoves % 10000 == 0)
{
printBoard(); //printBoard() every 10000 moves
}
if (col >= 0 && col <= 7 && row >= 0 && row <= 7 && board[row][col] == 0) //check if space is on board and if it is unoccupied
{
board[col][row] = movNum;
totalMoves++;
if (moveKnight(col + 1, row - 2, movNum + 1) != false)
moveKnight(col + 1, row - 2, movNum + 1);
else if (moveKnight(col + 2, row - 1, movNum + 1) != false)
moveKnight(col + 2, row - 1, movNum + 1);
else if (moveKnight(col + 2, row + 1, movNum + 1) != false)
moveKnight(col + 2, row + 1, movNum + 1);
else if (moveKnight(col + 1, row + 2, movNum + 1) != false)
moveKnight(col + 1, row + 2, movNum + 1);
else if (moveKnight(col - 1, row + 2, movNum + 1) != false)
moveKnight(col - 1, row + 2, movNum + 1);
else if (moveKnight(col - 2, row + 1, movNum + 1) != false)
moveKnight(col - 2, row + 1, movNum + 1);
else if (moveKnight(col - 2, row - 1, movNum + 1) != false)
moveKnight(col - 2, row - 1, movNum + 1);
else if (moveKnight(col - 1, row - 2, movNum + 1) != false)
moveKnight(col - 1, row - 2, movNum + 1);
else
return false;
}
}
Решение
Если вы посмотрите в moveKnight() функция, обратите внимание, что линия if (moveKnight(col, row, movNum) == false) выполняет рекурсивный вызов функции независимо от того, какие входы.
Всякий раз, когда вы используете рекурсивную функцию, она должна иметь то, что называется базовым случаем, когда рекурсивного вызова не происходит. В противном случае рекурсивные вызовы будут продолжаться до тех пор, пока стек не переполнится, так как одно выполнение функции запустит другое, которое запустит другое и т. Д.
Кстати, куча операторов if в функции не имеет смысла, так как вы вызываете функцию и проверяете вывод, и если она истинна, то вы вызываете функцию во второй раз с точно такими же аргументами. Кроме того, если вы хотите бесконечный цикл, который вы разорвете позже, нет необходимости что-то вроде while(1 == 1), использование while(1) или же while(true),
Другие решения
int board[7][7] = { { 0 } };
Шахматная доска 8 х 8, поэтому вам нужно 8 элементов в массиве (от 0 до 7 включительно, это 8)
if (moveKnight(col, row, movNum == true))
У вас есть синтаксический код ошибки, компилятор расскажет вам обо всем этом. В Visual Studio убедитесь, что уровень предупреждения установлен на 4. Затем убедитесь, что программа скомпилирована с нулевыми ошибками и нулевыми предупреждениями.
Я бы порекомендовал написать программу, которая не требует ввода данных пользователем. Это облегчит отладку программы и исправление логики.
Ниже приведена простая рекурсия, которая перемещает рыцаря, пока он не застрянет в конце. Вам нужно будет еще улучшить логику, чтобы она охватывала все квадраты.
Убедитесь, что рекурсивная функция может быть нарушена. Это обсуждается более подробно в другом ответе.
int board[8][8] = { 0 };
void printBoard()
{
cout << "Current board\n";
for(int i = 0; i < 8; i++)
{
for(int x = 0; x < 8; x++)
cout << board[i][x] << " ";
cout << "\n";
}
cout << "\n";
}
int test(int &row, int &col, int move_row, int move_col)
{
int r = row + move_row;
int c = col + move_col;
if(r >= 0 && r < 8 && c >= 0 && c < 8 && !board[r][c])
{
row = r;
col = c;
return 1;
}
return 0;
}
bool move_knight(int &row, int &col)
{
board[row][col] = 1;
printBoard();
system("pause");
if(!test(row, col, 1, 2))
if(!test(row, col, 1, -2))
if(!test(row, col, -1, 2))
if(!test(row, col, -1, -2))
if(!test(row, col, 2, 1))
if(!test(row, col, 2, -1))
if(!test(row, col, -2, 1))
if(!test(row, col, -2, -1))
return false;
move_knight(row, col);
return true;
}
int main()
{
int col = 0;
int row = 0;
move_knight(col, row);
system("pause");
return 0;
}