Решения LeetCode (161 часть серии)
Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как Этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ
Проблема летакода # 51 (HARD): N-Queens
Описание:
( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++
N-Queens Головоломка – проблема размещения n Queens на n x n Шахматная доска такая, что ни одно две королевы атакуют друг друга.
Учитывая целое число n , вернуть Все различные решения для N-Queens Puzzle Отказ
Каждое решение содержит отчетливую конфигурацию платы в размещении N-Queens, где 'Q' и '.' Оба указывают на королеву и пустое пространство, соответственно.
Примеры:
| Вход: | |
| Выход: | [[«.Q ..», «… Q», «Q …», “.. Q.”], [“.. Q.”, “Q …”, ” …Q”,”. Q..”]] |
| Объяснение: | Существует два различных решения для головоломки 4 Queens, как показано выше |
| Визуальный |
| Вход: | |
| Выход: | [[“Q”]] |
Ограничения:
1
Идея:
( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++
Наивный подход здесь попытается все возможное сочетание мест, но есть (N ^ 2)!/(N ^ 2 – n)! Разные комбинации, которые до ~ 1E17 Когда N . Вместо этого нам нужно убедиться, что мы только попытаемся разместить королевы, где это возможно, чтобы сделать это, основанным на инструкциях. Казалось бы, это позвонит для Глубина первый поиск ( DFS ) Подход с рекурсивный Функция помощника ( Place ), так что мы проводим только работоспособные комбинации, не теряя время на известных мертвых концах.
Во-первых, мы должны учитывать, как будут размещены королевы. Поскольку каждая строка может иметь только одну королеву, наш базовый процесс будет в место королева, а затем решайте следующий ряд. На каждой строке нам придется повторять возможные варианты, проверять ячейку для действительности, то место Королева на доска Отказ Как только рекурсия возврат S, мы можем backtrack и итерацию до следующей клетки в ряд.
Поскольку королева имеет четыре оси атаки, нам нужно проверить три оставшихся оси (кроме горизонтальной строки, которую наша итерация естественным образом позаботится) для действительности. Есть N Возможные столбцы и 2 * N – 1 Возможные диагонали левой нисходящей и правой нисходящей диагонали. С ограничением 1, Каждая из двух диагональных состояний представляет собой до 17 бит «Стоимость данных и вертикальное состояние до 9 бит Итак, мы можем использовать Битовое манипуляция хранить эти состояния эффективно.
Так что для каждого рекурсивного звонка к место Королева, мы должны пройти вдоль государства доска в виде только трех целых чисел ( Vert, Ldiag, Rdiag ). Затем мы можем использовать Bitmasks Чтобы проверить достоверность клетки, прежде чем пытаться восстановить следующую строку.
С нашего доска это N ^ 2 Матрица, мы можем использовать обратно здесь до хорошего эффекта. Если мы успешно доберемся до конца доски без провала, мы должны толкать копию доски с помощью строк в качестве строк на наш массив ответов ( ANS ). ( Примечание : Можно опустить дополнительное пространство только размеру стека рекурсии, O (n) процедурно создавая результаты непосредственно в анс , но это не представляет много экономии космического пространства по сравнению с дополнительной обработкой, которую он требует.)
- Сложность времени: O (n!) который представляет максимальное количество размещенных королев
- Космическая сложность: O (N ^ 2) для доски
Код JavaScript:
( Перейти к : Описание проблемы Идея решения
var solveNQueens = function(N) {
let ans = [],
board = Array.from({length: N}, () => new Array(N).fill('.'))
const place = (i, vert, ldiag, rdiag) => {
if (i === N) {
let res = new Array(N)
for (let row = 0; row < N; row++)
res[row] = board[row].join("")
ans.push(res)
return
}
for (let j = 0; j < N; j++) {
let vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j)
if (vert & vmask || ldiag & lmask || rdiag & rmask) continue
board[i][j] = 'Q'
place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
board[i][j] = '.'
}
}
place(0,0,0,0)
return ans
};
Код Python:
( Перейти к : Описание проблемы Идея решения
class Solution:
def solveNQueens(self, N: int) -> List[List[str]]:
ans = []
board = [['.'] * N for _ in range(N)]
def place(i: int, vert: int, ldiag: int, rdiag:int) -> None:
if i == N:
ans.append(["".join(row) for row in board])
return
for j in range(N):
vmask, lmask, rmask = 1 << j, 1 << (i+j), 1 << (N-i-1+j)
if vert & vmask or ldiag & lmask or rdiag & rmask: continue
board[i][j] = 'Q'
place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
board[i][j] = '.'
place(0,0,0,0)
return ans
Java код:
( Перейти к : Описание проблемы Идея решения
class Solution {
List> ans;
char[][] board;
public List> solveNQueens(int N) {
ans = new ArrayList<>();
board = new char[N][N];
for (char[] row : board) Arrays.fill(row, '.');
place(0,0,0,0);
return ans;
}
private void place(int i, int vert, int ldiag, int rdiag) {
int N = board.length;
if (i == N) {
List res = new ArrayList<>();
for (char[] row : board) res.add(new String(row));
ans.add(res);
return;
}
for (int j = 0; j < N; j++) {
int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
if ((vert & vmask) + (ldiag & lmask) + (rdiag & rmask) > 0) continue;
board[i][j] = 'Q';
place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask);
board[i][j] = '.';
}
}
}
C ++ код:
( Перейти к : Описание проблемы Идея решения
class Solution {
public:
vector> solveNQueens(int N) {
ans.clear();
board.resize(N, string(N, '.'));
place(0,0,0,0);
return ans;
}
private:
vector> ans;
vector board;
void place(int i, int vert, int ldiag, int rdiag) {
int N = board.size();
if (i == N) {
vector res;
for (auto row : board) res.push_back(row);
ans.push_back(res);
return;
}
for (int j = 0; j < N; j++) {
int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
if (vert & vmask || ldiag & lmask || rdiag & rmask) continue;
board[i][j] = 'Q';
place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask);
board[i][j] = '.';
}
}
};
Решения LeetCode (161 часть серии)
Оригинал: “https://dev.to/seanpgallivan/solution-n-queens-5hdb”