NQueensDLS.cpp

#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

int maxDepthQueens = 3;
vector<int> boardQueensDLS;

bool isSafeQueensDLS(int row, int col) {
    for (int i = 0; i < row; ++i) {
        if (boardQueensDLS[i] == col) return false;
        if (abs(boardQueensDLS[i] - col) == abs(i - row)) return false;
    }
    return true;
}

bool dlsQueens(int row, int n) {
    if (row == n) return true;
    if (row > maxDepthQueens) return false;

    for (int col = 0; col < n; ++col) {
        if (isSafeQueensDLS(row, col)) {
            boardQueensDLS[row] = col;
            if (dlsQueens(row + 1, n)) return true;
        }
    }
    return false;
}

void printBoardQueensDLS(int n) {
    cout << "Partial solution within depth " << maxDepthQueens << ":\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << (boardQueensDLS[i] == j ? "Q " : ". ");
        }
        cout << '\n';
    }
}

int main() {
    cout << "Enter value of N: ";
    int n;
    cin >> n;
    boardQueensDLS.assign(n, 0);

    if (dlsQueens(0, n)) printBoardQueensDLS(n);
    else cout << "No solution found within depth " << maxDepthQueens << ".\n";
    return 0;
}