% This program solves the dominant queens 
% problem for the NxN board using brute force method.
% The user chooses the board size (N) and the number of queens (numQueens).
% It starts by placing one queen (on all places) and checking the 
% number of attacked positions. Then it places two queens
% (tries all possibilities) and checks the attacked positions,
% and so on until the solution is found.
% The solution is found when all positions on the board
% are attacked.
% To find all solutions comment out 3 lines at the end.
% This version finds only the first solution.

clear
clc

N = 4;
A = zeros(N);

% attackedPositions = zeros(N);
positions = 1 : N^2;
solutions = [];
no_solutions = [];
%for numQueens = 1 : N   % i represents the number of queens on the board in the current step
% uncomment the previous line and comment out the next line and the program
% will find the solutions for all number of queens.
numQueens = 2;
    Q = nchoosek(positions, numQueens);    
    possibilities = numel(Q) / numQueens;
    for i = 1 : possibilities
       temp = Q(i, :);
       A(temp) = 1;
       B = attackedPositions(A, N);
        if sum(sum(B)) == N^2
            solutions(:, :, end+1) = A;
        else
            no_solutions(:, :, end+1) = A;
        end
        A = zeros(N);
        if (numel(solutions)>0)     % to find all solutions
            break;                  % comment out these
        end                         % three lines.
    end    
%end
solutions(:,:,1) = [];
no_solutions(:, :, 1) = [];
solutions