Knight's Tour по Java (рекурсивный) с использованием Graph и DFS

Я пытаюсь рассчитать все возможные ходы коня на поле 5х5:

Для этого я пытаюсь использовать класс DFS (Depth First Search) и класс Graph.

Я подумал, что это может быть слишком много кода (и, возможно, недостаточно), чтобы вставить эти целые классы в этом посте, поэтому я отображаю их здесь:

Graph.java

DepthFirstSearch.java

Graph.java использует Bag.java:

Bag.java

Поле будет выглядеть примерно так (с использованием идентификатора для каждого поля):

0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

Следующие атрибуты используются в методе CalculatePath, который должен рассчитать количество возможных туров, которые рыцарь может совершить из определенного квадрата, чтобы посетить каждый квадрат ровно один раз (для его решения потребуется минута или две).

Возможные шаги Найта определены (в основном классе) следующим образом (с использованием ребер графа G):

G.addEdge(0, 11);
G.addEdge(0, 7);

G.addEdge(1, 8);
G.addEdge(1, 10);
G.addEdge(1, 12);

G.addEdge(2, 5);
G.addEdge(2, 9);
G.addEdge(2, 11);
G.addEdge(2, 13);

G.addEdge(3, 6);
G.addEdge(3, 12);
G.addEdge(3, 14);

G.addEdge(4, 7);
G.addEdge(4, 13);

G.addEdge(5, 2);
G.addEdge(5, 12);
G.addEdge(5, 16);

G.addEdge(6, 15);
G.addEdge(6, 17);
G.addEdge(6, 3);
G.addEdge(6, 13);

G.addEdge(7, 0);
G.addEdge(7, 4);
G.addEdge(7, 10);
G.addEdge(7, 14);
G.addEdge(7, 16);
G.addEdge(7, 18);

G.addEdge(8, 1);
G.addEdge(8, 17);
G.addEdge(8, 19);
G.addEdge(8, 11);

G.addEdge(9, 2);
G.addEdge(9, 12);
G.addEdge(9, 18);

G.addEdge(10, 1);
G.addEdge(10, 21);
G.addEdge(10, 7);
G.addEdge(10, 17);

G.addEdge(11, 0);
G.addEdge(11, 2);
G.addEdge(11, 20);
G.addEdge(11, 22);
G.addEdge(11, 8);
G.addEdge(11, 18);

G.addEdge(12, 1);
G.addEdge(12, 3);
G.addEdge(12, 21);
G.addEdge(12, 23);
G.addEdge(12, 5);
G.addEdge(12, 9);
G.addEdge(12, 15);
G.addEdge(12, 19);

G.addEdge(13, 2);
G.addEdge(13, 4);
G.addEdge(13, 22);
G.addEdge(13, 24);
G.addEdge(13, 6);
G.addEdge(13, 16);

G.addEdge(14, 3);
G.addEdge(14, 23);
G.addEdge(14, 7);
G.addEdge(14, 17);

G.addEdge(15, 6);
G.addEdge(15, 12);
G.addEdge(15, 22);

G.addEdge(16, 5);
G.addEdge(16, 7);
G.addEdge(16, 13);
G.addEdge(16, 23);

G.addEdge(17, 6);
G.addEdge(17, 8);
G.addEdge(17, 10);
G.addEdge(17, 14);
G.addEdge(17, 20);
G.addEdge(17, 24);

G.addEdge(18, 7);
G.addEdge(18, 9);
G.addEdge(18, 11);
G.addEdge(18, 21);

G.addEdge(19, 8);
G.addEdge(19, 12);
G.addEdge(19, 22);

G.addEdge(20, 11);
G.addEdge(20, 17);

G.addEdge(21, 10);
G.addEdge(21, 12);
G.addEdge(21, 18);

G.addEdge(22, 11);
G.addEdge(22, 13);
G.addEdge(22, 15);
G.addEdge(22, 19);

G.addEdge(23, 12);
G.addEdge(23, 14);
G.addEdge(23, 16);

G.addEdge(24, 13);
G.addEdge(24, 17);

int currentSquare = 20;
calculatePath(currentSquare);
System.out.println("From square " + currentSquare + " there are " + tours + " possible tours.");

Вот что я пытался найти возможные туры:

  private static void calculatePath(int currentSquare) {
        boolean foundChoice = false;
        for (int point : G.adj(currentSquare)) {

            if (dfs.marked(currentSquare)) {
                foundChoice = true;
//              dfs.unmark(currentSquare);
                calculatePath(point);
            }
        }
        if (!foundChoice) {
            tours++;
            dfs.unmark(currentSquare);
        }
        System.out.println(currentSquare + " - tours: " + tours);
    }

Например, если я попытаюсь вызвать эту рекурсивную функцию calculatePath(20)Стоит вернуть все возможные туры (tours) из этого квадрата, используя каждый квадрат на поле.

Квадраты без опознавательных знаков - это квадраты, которые уже были достигнуты и больше не должны посещаться в том же туре.

Теперь проблема в том, что я не могу позволить CalculatePath пропустить уже посещенные квадраты (вывод показывает, что он идет с 20 до 17 и с 20 до 11, а затем останавливает рекурсивный метод).

Кроме того, метод пока не рассчитывает несколько туров. Я хочу сначала правильно рассчитать один путь и в итоге рассчитать все возможные туры.

Весь код, который я использую, защищен в этом посте - включая классы по ссылкам выше.

Источник

1 ответ

Есть еще:) ряд проблем с этим кодом, но похоже, что вы делаете успехи.

Ваш метод DepthFirstSearch.marked мне кажется неправильным Я бы подумал, что это должно вернуться true если он успешно изменил оценку с false в true, Здесь вы только возвращаете значение marked[w],

Ваш DepthFirstSearch Кажется, конструктор пытается пометить все смежные (и все их смежные точки). Это кажется странным - как вы ожидаете, что это будет работать? Обычный механизм DFS, позволяющий избегать циклов, - оставлять метку в каждом месте, к которому вы прикоснулись, во время рекурсии и удаления метки по завершении рекурсии. Здесь вы, кажется, отмечаете все квадраты в начале и затем снимаете их, когда вы завершили один раунд всех смежных областей, не найдя отмеченный.

Источник
Другие вопросы по тегам