Question

Ao modificar o algoritmo em Prolog em Coloração de Mapas, disponível logo abaixo, para esse mapa apresentado, permitindo que as cidades A e B possam ter cores iguais. Quantas soluções existem?

/*

* Variáveis: A,B,C,D,E,F

Domínio:: {vermelho,verde,azul}

Restrições: A!=B, A!=C, B!=C, B!=D, C!=D, C!=E, C!=F, D!=E, E!=F

*/



/*

* Impomos as restriçõess: different(A,B) significa que a cor de A deve ser diferente da de B.

* */

coloring(A,B,C,D,E,F) :-
different(A,B),
different(A,C),
different(B,C),
different(B,D),
different(C,D),
different(C,E),
different(C,F),
different(D,E),
different(E,F).

/*

* Os fatos: vermelho é diferente de azul, que é diferente de verde , etc

* */

different(vermelho,azul).
different(azul,vermelho).
different(vermelho,verde).
different(verde,vermelho).
different(verde,azul).
different(azul,verde).


A - 18
B - 12
C - 16
D - 20
E - 14

Answer 1

Resposta: Letra - B
12

Explicação: A alteração que deve ser feita no algoritmo é de apenas retirar a restrição: different(A,B). Assim, o número de soluções é 12, fazendo novamente a consulta coloring(A,B,C,D,E,F).

Answer 2

Resposta:

Resposta: 6

Explicação:

Bastava perceber que as novas condições do problema são: A!=B, A!=C, A!=D, B!=C, C!=D, C!=E,  D!=E, E!=C.  Com isso, conseguimos forçar essas condições na regra de coloring(A,B,C,D,E), como mostrado no código logo abaixo. Logo, no total são 6 soluções.