Ежедневный бит (е) C ++ # 58, Общая проблема интервью: N-Queens
Зная количество ферзей, решите задачу о N ферзях.
т.е. произвести все возможные размещения ферзей, где ферзи не атакуют друг друга (каждый ферзь находится в уникальном столбце, строке и диагонали).
Выведите результат в виде вектора решений, где каждое решение является вектором позиций столбцов ферзей.
Например, для приведенного выше результата будет: {{1,3,0,2}, {2,0,3,1}}.
Прежде чем продолжить чтение решения, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на проводник компилятора с парой тестов: https://compiler-explorer.com/z/EvK7hEsf4.
Решение
С точки зрения большого О, мы мало что можем сделать. Нам нужно перебрать все возможные решения, и если мы будем делать это по порядку, мы получим O(n!) (у первого ферзя есть n доступных позиций в столбцах, у второго — n- 1 и так далее).
Таким образом, проблема превращается в проблему эффективного выполнения этого. Проверить, занят ли столбец, легко можно с помощью вектора логических значений. Чтобы сделать то же самое с диагоналями, нам нужно сделать наблюдение.
Если мы возьмем разницу между индексом строки и столбца, диагонали получат одинаковые значения; следовательно, мы можем индексировать, используя это значение, и снова легко отслеживать занятые диагонали. И мы можем использовать очень похожую логику для ортогональных диагоналей, на этот раз используя сумму строки и столбца.
Мы можем обернуть эту логику в хелпер, из которого нам понадобится проверка (возможна ли комбинация строки и столбца) и два метода (не) пометить данную комбинацию строки и столбца как занятую.
struct State {
State(int n) : rows(n), cols(n), diag(2*n-1), adia(2*n-1) {}
std::vector<int> rows;
std::vector<bool> cols;
std::vector<bool> diag;
std::vector<bool> adia;
bool available(int row, int col) const {
return !cols[col] &&
!diag[row-col+rows.size()-1] &&
!adia[row+col];
}
void mark(int row, int col) {
rows[row] = col;
cols[col] = true;
diag[row-col+rows.size()-1] = true;
adia[row+col] = true;
}
void erase(int row, int col) {
cols[col] = false;
diag[row-col+rows.size()-1] = false;
adia[row+col] = false;
}
};
Остальная часть проблемы — это простой алгоритм поиска/возврата в глубину.
void solve(auto& state, int row, int n,
std::vector<std::vector<int>>& solutions) {
if (row == n) {
// all queens have their positions, record the solution
solutions.push_back(state.rows);
return;
}
// try to find a feasible column on this row
for (int c = 0; c < n; ++c) {
if (!state.available(row,c))
continue;
state.mark(row,c);
// recurse to the next row
solve(state, row+1, n, solutions);
state.erase(row,c);
}
}
Откройте решение в Compiler Explorer.
Эта проблема также является хорошей возможностью изучить разницу между динамическим и статическим подходами. В нашем решении мы принимаем размер задачи в качестве аргумента функции. Если мы переключим размер на константу времени компиляции, мы можем получить нетривиальную производительность.
Мы можем оставить нашу часть решения DFS такой же, но переключить состояние на статическое, используя std::array и std::bitset.
// Static state representation, using std::array and std::bitset
template <int n>
struct StaticState {
std::array<int,n> rows;
std::bitset<n> cols;
std::bitset<n> diag;
std::bitset<n> adia;
bool available(int row, int col) const {
return !cols[col] && !diag[row-col+rows.size()-1] && !adia[row+col];
}
void mark(int row, int col) {
rows[row] = col;
cols[col] = true;
diag[row-col+rows.size()-1] = true;
adia[row+col] = true;
}
void erase(int row, int col) {
cols[col] = false;
diag[row-col+rows.size()-1] = false;
adia[row+col] = false;
}
};
Это простое изменение обеспечивает ускорение примерно в 1,5 раза.
