Турецкий бактрекинг длится слишком долго

Как долго длится решение проблемы рыцарей с возвратом на доску 8x8? Потому что мой algo allready вычисляет как-то слишком долго, и кажется, будто он не заканчивается. Но когда я пытаюсь использовать плату 6x6 или 5x5, она заканчивается успешно.

код:

class KnightsTour{

private boolean[][] board;
private int count, places;
private static final Point[] moves = new Point[]{
 new Point(-2, -1),
 new Point(-2, 1),
 new Point(2, -1),
 new Point(2, 1),
 new Point(-1, -2),
 new Point(-1, 2),
 new Point(1, -2),
 new Point(1, 2)
};

public KnightsTour(int n) {
 board = new boolean[n][n];
 places = n*n;
 count = 0;
 }

public boolean ride(int x, int y) {


 board[x][y] = true;
 count++;

 if (count == places) {
 return true;
 }

 for (Point p : moves) {
 int nextX = x + p.x;
 int nextY = y + p.y;

 if (nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board.length || board[nextX][nextY]) {
 continue;
 } 
 if (ride(nextX, nextY)) {
 return true;
 }
 }

 board[x][y] = false;
 count--;

 return false;
}
}
1 ответ

Я столкнулся с той же проблемой. Все работает плавно до n = 7, и внезапно требуется вычисление для n=8. Я надеюсь, что это помогает кому-то :)

Проблема заключается в порядке, в котором вы проверяете ходы. Ты используешь:

xMove[8] = { -2, -2, 2, 2, -1, -1, 1, 1}

yMove[8] = { -1, 1, -1, 1, -2, 2, -2, 2}

Если вы построите эти векторы в 2D-плоскости, они будут беспорядочно размещены. Другими словами, они не упорядочены ни по часовой стрелке, ни против часовой стрелки. Рассмотрим это вместо этого:

xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }

yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }

Если вы рисуете эти векторы, они аккуратно расположены в круг против часовой стрелки. Так или иначе, это приводит к тому, что рекурсия выполняется очень быстро при больших значениях n. Имейте в виду, что все еще требуется навсегда вычисление для n=9 далее.

licensed under cc by-sa 3.0 with attribution.