Почему мой код Knight's Tour застрял в бесконечном цикле? С# ⇐ C#

[Anonymous]

Я пытаюсь решить задачу «Путешествие коня» на C# на шахматной доске 8x8, где конь должен посетить каждую позицию ровно один раз. Алгоритм начинается с фиксированной позиции и пытается сделать правильные ходы. Однако моя программа зацикливается, и я не могу понять, почему.
Вот соответствующий код:

Код: Выделить всё

public static bool springer_tour((int, int) start)
{
int[,] moveTries = new int[SIZE, SIZE];
(int, int) current_position = start;
moves.Add(start);
(int, int) next_valid_square;

do
{
next_valid_square = find_next_valid_field(current_position, moveTries);
if (!next_valid_square.Equals((-1, -1)))
{
current_position = next_valid_square; // Next valid move
moves.Add(current_position);
}
else
{
if (moveTries[current_position.Item1, current_position.Item2] >= 8)
{
moveTries[current_position.Item1, current_position.Item2] = 0;
moves.RemoveAt(moves.Count - 1);
if (moves.Count == 0)
{
Console.WriteLine("No Solution!");
return false;
}
current_position = moves[moves.Count - 1];
}
}
}
while (moves.Count < (SIZE * SIZE));
return true;
}

Метод find_next_valid_field выглядит следующим образом:

Код: Выделить всё

public static (int, int) find_next_valid_field((int, int) current_position, int[,] board)
{
int tries = board[current_position.Item1, current_position.Item2];
if (tries >= 8)
{
return (-1, -1);
}

(int, int)[] potential_moves =
{
(current_position.Item1 + 1, current_position.Item2 - 2),
(current_position.Item1 + 2, current_position.Item2 - 1),
(current_position.Item1 + 2, current_position.Item2 + 1),
(current_position.Item1 + 1, current_position.Item2 + 2),
(current_position.Item1 - 1, current_position.Item2 + 2),
(current_position.Item1 - 2, current_position.Item2 + 1),
(current_position.Item1 - 2, current_position.Item2 - 1),
(current_position.Item1 - 1, current_position.Item2 - 2)
};

// search for valid move
for (int i = tries; i < potential_moves.Length; i++)
{
(int, int) new_pos = potential_moves[i];
board[current_position.Item1, current_position.Item2]++;
if (new_pos.Item1 >= 0 && new_pos.Item1 < SIZE &&
new_pos.Item2 >= 0 && new_pos.Item2 < SIZE &&
board[new_pos.Item1, new_pos.Item2] == 0) // Field has to be unvisited
{
return new_pos; //return valid move
}
}

return (-1, -1); // no valid move found
}

Похоже, что когда конь застревает и не может найти правильный ход, код входит в бесконечный цикл. Метод find_next_valid_field возвращает (-1, -1), когда больше нет доступных ходов, и в этом случае я пытаюсь вернуться назад. Однако что-то в этом процессе работает не так, как ожидалось.
Я подозреваю, что проблема может быть связана с тем, как я отслеживаю количество попыток для каждого хода в массиве moveTries или с тем, как я проверяю допустимые ходы.
Есть идеи, почему программа застревает в бесконечном цикле? Как лучше поступить в случаях, когда не найдено ни одного допустимого хода?

Подробнее здесь: https://stackoverflow.com/questions/791 ... op-c-sharp