Рекурсивная проблема N-рыцарей
Я пытаюсь рекурсивно решить задачу n-knights на шахматной доске 8×8. Проблема n-рыцарей является вариацией n-проблема королев, где королевы сменяются рыцарями. Ни один кусок не может взять другой кусок.
Мой код до сих пор: http://pastebin.com/TVza3jVU.
Вход состоит из количества рыцарей, которые должны быть размещены на шахматной доске. Мой код печатает много правильных плат
Вывод выглядит так (пример):
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 1 0 6
1 1 0 1 0 1 0 0 7
0 1 2 3 4 5 6 7
nrBoards = 49
«1» обозначает рыцаря.
Моя проблема заключается в следующем:
0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 6
0 0 0 0 0 0 0 0 7
0 1 2 3 4 5 6 7
Это последняя доска, которую напечатает мой скрипт. Он никогда не поставит коня на [0] [0]. Я не могу понять, почему. Он также пропускает некоторые конфигурации. Что-то не так с моей рекурсией?
Решение
Из кода, который вы связали, кажется, что одна проблема заключается в вашей функции checkplace (). Вы не проверяете, находятся ли границы x + 2, x-2, y + 2, y-2 и т. Д. В интервале от 0 до 7.
int checkPlace(int y, int x, chessboard boards) {
if (boards.board[y - 2][x - 1] == 1) {
return 0;
}
if (boards.board[y - 1][x - 2] == 1) {
return 0;
}
if (boards.board[y - 2][x + 1] == 1) {
return 0;
}
if (boards.board[y - 1][x + 2] == 1) {
return 0;
}
if (boards.board[y + 1][x + 2] == 1) {
return 0;
}
if (boards.board[y + 1][x - 2] == 1) {
return 0;
}
if (boards.board[y + 2][x - 1] == 1) {
return 0;
}
if (boards.board[y + 2][x + 1] == 1) {
return 0;
}
return 1;
}
Вместо:
if ( x-1 >= 0 && y-2 >= 0 && boards.board[y - 2][x - 1] == 1) {
Точно так же и для других.
Другие решения
Других решений пока нет …