решение восьми ферзей для получения решения

Ниже моя попытка решить задачу о 8 ферзях, чтобы напечатать одно решение. (Расположите на шахматной доске 8 ферзей так, чтобы ни один из них не атаковал друг друга). Однако это решение размещает только 6 ферзей. Мне нужно другое мнение о том, где я делаю ошибку. Я делаю это скорее в стиле BFS, а не в обратном порядке.


java n-queens
person user3050784    schedule 02.12.2013    source источник
comment
пожалуйста, отформатируйте код правильно   -  person Math    schedule 02.12.2013
comment
Приветствую Кейси, на самом деле не привык к форматированию на этом сайте.   -  person user3050784    schedule 02.12.2013
comment
Трудно сказать, где ваша проблема, если вы даже не знаете. Пожалуйста, постарайтесь сфокусировать свой вопрос на конкретной проблеме.   -  person Paul Samsotha    schedule 02.12.2013
comment
Я получаю только 6 дам (шесть единиц). Я получаю только 0 в строках 5 и 6   -  person user3050784    schedule 02.12.2013
comment
пожалуйста, объясните логику вашего кода   -  person vandale    schedule 02.12.2013
comment
Я пытаюсь реализовать метод BFS.   -  person user3050784    schedule 02.12.2013
comment
В решении для печати, если вы выводите координаты, оно дважды повторяет 1,6 и 2,4 для найденных координат. Похоже, что в рекурсии есть какая-то логическая проблема, которая приводит к тому, что одно и то же место устанавливается в 0 и перепроверяется.   -  person Compass    schedule 03.12.2013
comment
Хм, спасибо, я понимаю проблему, но решить ее будет сложно.   -  person user3050784    schedule 03.12.2013

Ответы (1)


arrow_upward
0
arrow_downward

Кажется, ваш алгоритм работает со сбоями в какой-то момент. Запустив его, я обнаружил следующие проблемы:

  1. Вы постоянно устанавливаете visited[i][j] в 0 в своем цикле for в main. Это всегда сбрасывает посещения на 0, даже если выполняется рекурсивный вызов. На самом деле, когда вы объявляете как visited, так и board, они инициализируются массивами, полными 0. Таким образом, вы можете избавиться от обоих операторов set. Кроме того, поскольку вы сбрасываете массивы, ваша рекурсивная функция в конечном итоге устанавливает оба значения в 0, а затем снова находит их.

  2. Для отладки в операторе !hasQueen вы должны вывести координаты board[row][col], которые показывают вам найденные координаты. Окончательный список перед печатью сетки показывает, что 2,4 и 1,6 найдены и установлены дважды.

  3. Фактическая шахматная доска, которая выводится, заканчивается невозможным решением:

1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0

0 0 0 X 0 Y 0 0

0 0 0 Y 0 X 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

(извините, я не могу получить номера в формате)

И расклад X, и расклад Y не соответствуют правилам восьми ферзей.

Если вы запустите свою программу с закомментированным параметром 0, вы увидите, что она останавливается после нахождения 6 местоположений.

person Compass    schedule 02.12.2013
comment
Вы не думали прочитать запись в вики? en.wikipedia.org/wiki/Eight_queens_puzzle Похоже, поиск 4-й строки делает его недействительным с верхним левым решением ферзя. - person Compass; 03.12.2013