function b = EA_constrained_MC(pit_prob,visited,breezes,stenches,safe,...
    wumpus_dead)
%
% On input:
%     pit_prob (float): prob of a pit in any cell
%     visited (4x4 array): 1 if cell visited; else 0
%     breezes (4x4 array): -1 if unknown; 0 if no breeze; 1 if breeze
%     stenches (4x4 array): -1 if unknown; 0 if no stench; 1 if stench
%     safe (4x4 array): -1 if unknown; 0 if not safe; 1 if safe

CLEAR = 0;
WUMPUS = 3;
PIT = 1;
GOLD = 2;
BOTH = 4;

b = -ones(4,4);

% pits==-1 means unknown; 0 means no pit; 1 means pit
pits = -ones(4,4);

% wumpus>=0  means possible wumpus;  -1 means no wumpus
if wumpus_dead==1
    wumpus = -ones(4,4);
else
    wumpus = zeros(4,4);
end

% wumpus
if wumpus_dead==0
    for r = 1:4
        for c = 1:4
            if safe(r,c)==1
                wumpus(r,c) = -1;
            end
            if stenches(r,c)==0
                neis = BR_Wumpus_neighbors(c,4-r+1);
                num_neis = length(neis(:,1));
                for n = 1:num_neis
                    rr = 4 - neis(n,2) + 1;
                    cc = neis(n,1);
                    wumpus(rr,cc) = -1;
                end
            elseif stenches(r,c)==1
                neis = BR_Wumpus_neighbors(c,4-r+1);
                num_neis = length(neis(:,1));
                for n = 1:num_neis
                    rr = 4 - neis(n,2) + 1;
                    cc = neis(n,1);
                    if wumpus(rr,cc)>=0
                        wumpus(rr,cc) = wumpus(rr,cc) + 1;
                    end
                end
            end
        end
    end
    [rows,cols] = find(wumpus>0);
    if ~isempty(rows)
        num_cells = length(rows);
        max_count = max(wumpus(:));
        for c = 1:num_cells
            if wumpus(rows(c),cols(c))<max_count
                wumpus(rows(c),cols(c)) = -1;
            end
        end
        [rowsn,colsn] = find(wumpus==0);
        num_rowsn = length(rowsn);
        for c = 1:num_rowsn
            wumpus(rowsn(c),colsn(c)) = -1;
        end
    end
end

% breezes
for r = 1:4
    for c = 1:4
        c_pits(r,c).map = -ones(4,4);
    end
end

for r = 1:4
    for c = 1:4
        if safe(r,c)==1|visited(r,c)==1
            for rr = 1:4
                for cc = 1:4
                   c_pits(r,c).map(r,c) = 0;
                end
            end
        end
        if breezes(r,c)==0
            neis = BR_Wumpus_neighbors(c,4-r+1);
            num_neis = length(neis(:,1));
            for n = 1:num_neis
                rr = 4 - neis(n,2) + 1;
                cc = neis(n,1);
                c_pits(r,c).map(rr,cc) = 0;
            end
        elseif breezes(r,c)==1
            neis = BR_Wumpus_neighbors(c,4-r+1);
            num_neis = length(neis(:,1));
            for n = 1:num_neis
                rr = 4 - neis(n,2) + 1;
                cc = neis(n,1);
                if safe(rr,cc)~=1
                    c_pits(r,c).map(rr,cc) = 1;
                end
            end
        end
    end
end
for r1 = 1:4
    for c1 = 1:4
        for rm = 1:4
            for cm = 1:4
                if c_pits(r1,c1).map(rm,cm)==0
                    for r2 = 1:4
                        for c2 = 1:4
                            c_pits(r2,c2).map(rm,cm) = 0;
                        end
                    end
                end
            end
        end
    end
end

% Set board for visited and safe places
for r = 1:4
    for c = 1:4
        if safe(r,c)==1|visited(r,c)==1
            b(r,c) = 0;
        end
    end
end

% eliminate wumpus site if singleton pit required
for r = 1:4
    for c = 1:4
        [rows,cols] = find(c_pits(r,c).map>0);
        if length(rows)==1
            wumpus(rows,cols) = -1;
        end
    end
end

if max(stenches(:))<1    % no stench
    for r = 1:4
        for c = 1:4
            [rows,cols] = find(c_pits(r,c).map>0);
            if ~isempty(rows)
                num_cells = length(rows);
                probs = zeros(2^num_cells-1,1);
                for k = 1:2^num_cells-1
                    bits = BR_int2bits(k,num_cells);
                    zero_count = length(find(bits==0));
                    ones_count = length(find(bits==1));
                    probs(k) = (pit_prob^ones_count)*((1-pit_prob)^zero_count);
                end
                probs = probs/sum(probs);
                [probs_s,indexes_s] = sort(probs);
                rand_val = rand;
                choice = 0;
                for k = 1:2^num_cells-1
                    if rand_val<sum(probs_s(1:k))
                        choice = indexes_s(k);
                        break;
                    end
                end
                bits = BR_int2bits(choice,num_cells);
                for k = 1:num_cells
                    if bits(k)==1
                        b(rows(k),cols(k)) = PIT;
                    end
                end
            end
        end
    end
    [rows,cols] = find(wumpus==0);
    if ~isempty(rows)
        k = randi(length(rows));
        b(rows(k),cols(k)) = WUMPUS;
    end
elseif length(find(wumpus(:)>0))==1
    [roww,colw] = find(wumpus>0);
    b(roww,colw) = WUMPUS;
    for r = 1:4
        for c = 1:4
            c_pits(r,c).map(roww,colw) = 0;
        end
    end
    for r = 1:4
        for c = 1:4
            [rows,cols] = find(c_pits(r,c).map>0);
            if ~isempty(rows)
                num_cells = length(rows);
                probs = zeros(2^num_cells-1,1);
                for k = 1:2^num_cells-1
                    bits = BR_int2bits(k,num_cells);
                    zero_count = length(find(bits==0));
                    ones_count = length(find(bits==1));
                    probs(k) = (pit_prob^ones_count)*(pit_prob^zero_count);
                end
                probs = probs/sum(probs);
                [probs_s,indexes_s] = sort(probs);
                rand_val = rand;
                choice = 0;
                for k = 1:2^(num_cells-1)
                    if rand_val<sum(probs_s(1:k))
                        choice = k;
                        break;
                    end
                end
                for k = 1:num_cells
                    if bits(k)==1
                        b(rows(k),cols(k)) = PIT;
                    end
                end
            end
        end
    end
elseif length(find(wumpus(:)>0))>1
    [rowsw,colsw] = find(wumpus>0);
    k = randi(length(rowsw));
    b(rowsw(k),colsw(k)) = WUMPUS;
    for r = 1:4
        for c = 1:4
            c_pits(r,c).map(rowsw(k),colsw(k)) = 0;
        end
    end
    for r = 1:4
        for c = 1:4
            [rows,cols] = find(c_pits(r,c).map>0);
            if ~isempty(rows)
                num_cells = length(rows);
                probs = zeros(2^num_cells-1,1);
                for k = 1:2^num_cells-1
                    bits = BR_int2bits(k,num_cells);
                    zero_count = length(find(bits==0));
                    ones_count = length(find(bits==1));
                    probs(k) = (pit_prob^ones_count)*(pit_prob^zero_count);
                end
                probs = probs/sum(probs);
                [probs_s,indexes_s] = sort(probs);
                rand_val = rand;
                choice = 0;
                for k = 1:2^(num_cells-1)
                    if rand_val<sum(probs_s(1:k))
                        choice = k;
                        break;
                    end
                end
                for k = 1:num_cells
                    if bits(k)==1
                        b(rows(k),cols(k)) = PIT;
                    end
                end
            end
        end
    end
end
[rows,cols] = find(b==-1|b==0|b==WUMPUS);
k = randi(length(rows));
rg = rows(k);
cg = cols(k);
if b(rg,cg)==WUMPUS
    b(rg,cg) = BOTH;
else
    b(rg,cg) = GOLD;
end
[rows,cols] = find(b<0);
for k = 1:length(rows)
    b(rows(k),cols(k)) = CLEAR;
end
pits = c_pits(1,1).map;
for r = 1:4
    for c = 1:4
        pits = c_pits(r,c).map.*pits;
    end
end
[roww,colw] = find(b==WUMPUS|b==BOTH);
pits(roww,colw) = 0;
[rowg,colg] = find(b==GOLD|b==BOTH);
pits(rowg,colg) = 0;
for r = 1:4
    for c = 1:4
        if pits(r,c)~=0
            if rand<pit_prob
                b(r,c) = PIT;
            end
        end
    end
end
tch = 0;
