Застрял в алгоритме для q епископов на n * n шахматной доске
Я использую C ++, но мой вопрос больше об алгоритмах, чем о реализации.
Проблема заключается в следующем:
Напишите программу, которая вводит два целых числа n и k, где n> = k. Ваша программа должна рассчитать количество различных способов размещения k слонов на шахматной доске nXn.
Моя основная идея — представить каждого слона как структуру со значением X и значением Y. Затем я помещаю слонов на доску, чтобы получить конфигурацию.
Я написал метод с именем moveToNextPlace, который позволяет мне переместить слона в следующее доступное место. Я возвращаю строку, чтобы помочь с отладкой.
struct bishop {
int y=0;
int x=0;
string moveToNextPlace (int n){
if (y<n-1) {y++; return "move to next y value";}
else if (x<n-1) {x++; return "move to next x value";}
else {reset(); return "reset";};
}
void setValuesLike (bishop b){
y=b.y;
x=b.x;
}
void reset (){
y=0;
x=0;
}
bool clashesWith (bishop b){
if (b.x==x && b.y==y){
return true;
}
if ( b.y-y == b.x-x ) return true; //if their slope is 1
return false;
}
};
Затем я устанавливаю плату в начальную конфигурацию, вызывая findSolutions с моими желаемыми настройками.
int findSolutions (int k, int n){ //k bishops on n*n board
bishop *b = new bishop [k];
for (int i=0; i<k; i++){
findAspot (b, n, i);
}
}
bool check (int num, bishop b[]){
for (int i=0 ; i<num; i++){
if (b[i].clashesWith (b[num])) return false;
}
return true;
}
void findAspot (bishop b[], int n, int num){ //n=boardsize
while (1){
if (check(num, b)){return;}
if (b[num].moveToNextPlace(n) == "reset") break;
}
b[num-1].moveToNextPlace(n);
findAspot (b, n, num-1);
b[num].setValuesLike ( b[num-1] );
findAspot (b, n, num);
}
Затем я хочу вернуться назад, пока у меня не будет общего числа решений, но я застрял в том, как найти следующее решение.
Я думал, что смогу написать findNextSolution, который будет вызываться в конце функции findSolutions, пока не достигнет цикла. Но я не знаю, какой алгоритм использовать, чтобы найти следующее решение.
Решение
У вас хорошее начало с вашей идеей сохранения позиций слона в массиве. Это компактное представление состояния платы.
Вы должны будете исправить свой метод проверки, сталкивается ли один епископ с другим. Имейте в виду, что два сталкивающихся епископа могут быть разделены вертикальным расстоянием dy и горизонтальное расстояние dx такой, что dx == -dy, Таким образом, вы хотите сравнить абсолютные значения: епископы конфликтуют, если abs(dx) == abs(dy),
Теперь перейдем к общей проблеме подсчета количества состояний совета, в которых k Епископы расположены без столкновений. Вы захотите определить функцию, которая возвращает целочисленное значение. Допустим, что эта функция выглядит
count(currentBishops, numRemaining)
где currentBishops возможно размещение епископов и numRemaining количество епископов, которых вы еще не разместили
Тогда решение проблемы
count([], k)
где [] означает, что ни один епископ еще не был размещен.
count Функция может быть реализована в соответствии со следующим псевдокодом.
count(currentBishops, numRemaining):
if numRemaining == 0:
return 1
sum = 0
for each possible board position (x, y):
if (x, y) does not clash with any bishop in currentBishops:
let nextBishops be currentBishops augmented with (x, y)
sum += count(nextBishops, numRemaining-1)
return sum
Чтобы избежать экспоненциального взрыва рекурсивных вызовов, вам нужно будет кэшировать результат каждой подзадачи. Эта техника называется мемоизации, и вы можете реализовать это следующим образом.
let memo be a map from (currentBishops, numRemaining) to an integer value
count(currentBishops, numRemaining):
if numRemaining == 0:
return 1
if memo contains (currentBishops, numRemaining):
return memo[(currentBishops, numRemaining)]
sum = 0
for each possible board position (x, y):
if (x, y) does not clash with any bishop in currentBishops:
let nextBishops be currentBishops augmented with (x, y)
sum += count(nextBishops, numRemaining-1)
memo[(currentBishops, numRemaining)] = sum
return sum
Отображение currentBishops должен быть тот, который не заботится о порядке, в котором вы разместили епископов. Вы можете сделать это, отсортировав позиции слона или сделав растровое изображение доски, когда вычисляете ключ для memo,
Другие решения