N-Queens LeetCode Həlli

Problem bəyanat

N-Queens LeetCode Həlli – The n-queens puzzle yerləşdirmə problemidir n kraliçalar a n x n şahmat taxtası elədir ki, iki kraliça bir-birinə hücum etmir.

Bir tam verilir n, qayıt üçün bütün fərqli həllər n-queens tapmacası. Cavabı geri qaytara bilərsiniz hər hansı bir sifariş.

Hər bir həll n-queens'in yerləşdirilməsinin fərqli lövhə konfiqurasiyasını ehtiva edir, burada 'Q' və '.' hər ikisi müvafiq olaraq kraliça və boş yerə işarə edir.

misal

Test işi 1:

Input:

n = 4

Çıxış:

[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q.. ”]]

Pin

Explanation:

Yuxarıda göstərildiyi kimi 4-queens tapmacasının iki fərqli həlli var.

Yanaşma:

1. Hər cərgədə 1 kraliça var

2. Hər bir sıra üçün kraliçanın yerləşdirilməsi üçün etibarlı sütunları izləyin. # (ağıllı şəkildə QEYD)

3. DFS, birinci sətirdən başlayın, hər etibarlı sütunu sınayın və arxa yol zəruridirsə.

Qeyd edək ki, biz sol/sağ diaqonalları indekslər kimi aşağıdakı şəkildə kodlaya bilərik

Hər hansı (r, c) üçün

yuxarıdan soldan aşağıya doğru diaqonal indeks r – c, ∈ (-n, n)

onun aşağıdan soldan yuxarıya doğru diaqonal indeks r + c, ∈ [0, 2n)

Hər biri (r, c) r-ci sıra, c-ci sütun və yuxarıda kodlanmış iki diaqonal indeksi götürür.

Beləliklə, həmin cərgənin/sütun/diaqonalın alınıb-alınmadığını göstərmək üçün 4 dəstdən istifadə edə bilərik, əgər varsa, kraliça (r, c) nöqtəsinə yerləşdirilə bilməz.

Bundan əlavə, dfs vasitəsilə sətir-sətirlə axtarış etsək, # sıra dəstini saxlamaqdan, yalnız 3 dəstlə (sütun və 2 diaqonal) qaça bilərik.

Hər bir dəst sütunun/diaqonal müəyyən edilmiş indekslə götürülmüşdür.

N-Queens üçün kod

Java Proqramı

class Solution {
    private Set<Integer> col = new HashSet<Integer>();
    private Set<Integer> diag1 = new HashSet<Integer>();
    private Set<Integer> diag2 = new HashSet<Integer>();
    
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(res,new ArrayList<String>(), 0, n);
        return res;
    }
    private void dfs(List<List<String>> res, List<String> list, int row, int n){
        if (row == n){
            res.add(new ArrayList<String>(list));
            return;
        }
        for (int i = 0; i < n; i++){
            if (col.contains(i) || diag1.contains(row + i) || diag2.contains(row - i)) continue;
            
            char[] charArray = new char[n];
            Arrays.fill(charArray, '.');
            charArray[i] = 'Q';
            String rowString = new String(charArray);
            
            list.add(rowString);
            col.add(i);
            diag1.add(row + i);
            diag2.add(row - i);
            
            dfs(res, list, row + 1, n);
            
            list.remove(list.size() - 1);
            col.remove(i);
            diag1.remove(row + i);
            diag2.remove(row - i);
        }
    }
}

C ++ Proqramı

class Solution {
public:
    std::vector<std::vector<std::string> > solveNQueens(int n) {
        std::vector<std::vector<std::string> > res;
        std::vector<std::string> nQueens(n, std::string(n, '.'));
        solveNQueens(res, nQueens, 0, n);
        return res;
    }
private:
    void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) {
        if (row == n) {
            res.push_back(nQueens);
            return;
        }
        for (int col = 0; col != n; ++col)
            if (isValid(nQueens, row, col, n)) {
                nQueens[row][col] = 'Q';
                solveNQueens(res, nQueens, row + 1, n);
                nQueens[row][col] = '.';
            }
    }
    bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) {
        //check if the column had a queen before.
        for (int i = 0; i != row; ++i)
            if (nQueens[i][col] == 'Q')
                return false;
        //check if the 45° diagonal had a queen before.
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
            if (nQueens[i][j] == 'Q')
                return false;
        //check if the 135° diagonal had a queen before.
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
            if (nQueens[i][j] == 'Q')
                return false;
        return true;
    }
};

N-Queens LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O(N**N).

Kosmik Mürəkkəblik: O(N**2)