Toggle navigation
?
users online
Logout
Open hangout
Open chat for current file
% Joao Moura 109733 :- use_module(library(clpfd)). % para poder usar transpose/2 % Ficheiro dado. No Mooshak tera mais puzzles. % Atencao: nao deves copiar nunca os puzzles para o teu ficheiro de codigo % Segue-se o codigo % 4.1 Consultas % ------------------------------------------------------------------------------ % vizinhanca((L, C), Vizinhanca) % eh verdade se Vizinhanca eh uma lista ordenada de cima para baixo e da esquerda % para a direita, sem elementos repetidos, com as coordenadas das posicoes % imediatamente acima, imediatamente ah esquerda, imediatamente ah direita e % imediatamente abaixo da coordenada (L, C) % ------------------------------------------------------------------------------ vizinhanca((L, C), Vizinhanca):- Cima is L-1, Esquerda is C-1, Direita is C+1, Baixo is L+1, Vizinhanca = [(Cima,C),(L,Esquerda),(L,Direita),(Baixo,C)]. % ------------------------------------------------------------------------------ % vizinhancaAlargada((L, C), VizinhancaAlargada) % eh verdade se VizinhancaAlargada eh uma lista ordenada de cima para baixo e da % esquerda para a direita, sem elementos repetidos, com as coordenadas anteriores % e ainda as diagonais da coordenada (L, C) % ------------------------------------------------------------------------------ vizinhancaAlargada((L, C), VizinhancaAlargada):- Cima is L-1, Esquerda is C-1, Direita is C+1, Baixo is L+1, VizinhancaAlargada = [(Cima,Esquerda),(Cima,C),(Cima,Direita),(L,Esquerda), (L,Direita),(Baixo,Esquerda),(Baixo,C),(Baixo,Direita)]. % ------------------------------------------------------------------------------ % todasCelulas(Tabuleiro, TodasCelulas) % eh verdade se TodasCelulas eh uma lista ordenada de cima para baixo e da % esquerda para a direita, sem elementos repetidos, com todas as coordenadas do % tabuleiro Tabuleiro % ------------------------------------------------------------------------------ todasCelulas(Tabuleiro, TodasCelulas):- length(Tabuleiro,Linhas), nth1(1, Tabuleiro, Linha), length(Linha,Colunas), encontraPosicoes(Linhas, Colunas, TodasCelulas). encontraPosicoes(Linhas, Colunas, Posicoes):- findall((X, Y), (between(1, Linhas, X), between(1, Colunas, Y)), Posicoes). % ------------------------------------------------------------------------------ % todasCelulas(Tabuleiro, TodasCelulas, Objecto) % eh verdade se TodasCelulas eh uma lista ordenada de cima para baixo e da % esquerda para a direita, sem elementos repetidos, com todas as coordenadas do % tabuleiro Tabuleiro em que existe um objecto do tipo Objecto % ------------------------------------------------------------------------------ todasCelulas(Tabuleiro, TodasCelulas, Objecto):- findall((Linha, Coluna), (nth1(Linha, Tabuleiro, Lista), nth1(Coluna, Lista, Elemento), (Elemento == Objecto ; (var(Objecto), var(Elemento)))), TodasCelulas). % ------------------------------------------------------------------------------ % calculaObjectosTabuleiro(Tabuleiro, ContagemLinhas, ContagemColunas, Objecto) % eh verdade se Tabuleiro for um tabuleiro, Objecto for o tipo de objecto que se % procura, e ContagemLinhas e ContagemColunas forem, respectivamente, listas com % o numero desses objectos por linha e por coluna % ------------------------------------------------------------------------------ calculaObjectosTabuleiro(Tabuleiro, ContagemLinhas, ContagemColunas, Objecto) :- todasCelulas(Tabuleiro, TodasCelulas, Objecto), length(Tabuleiro, Comprimento), findall(0, between(1, Comprimento, _), ListaZeros), cOT_aux(TodasCelulas, ListaZeros, ContagemLinhas), transpose(Tabuleiro, Transposta), todasCelulas(Transposta, TodasCelulas2, Objecto), cOT_aux(TodasCelulas2, ListaZeros, ContagemColunas). cOT_aux([], Lista, Lista). cOT_aux([(L, _) | Resto], Lista, ListaResultante) :- nth1(L, Lista, Z, _), NovoElemento is Z + 1, atualizaElemento(L, Lista, NovoElemento, ListaTemp), !, cOT_aux(Resto, ListaTemp, ListaResultante). atualizaElemento(1, [_ | Resto], NovoElemento, [NovoElemento | Resto]). atualizaElemento(L, [Elem | Resto], NovoElemento, [Elem | RestoAtualizado]) :- L > 1, L1 is L - 1, atualizaElemento(L1, Resto, NovoElemento, RestoAtualizado). % ------------------------------------------------------------------------------ % celulaVazia(Tabuleiro, (L, C)) % eh verdade se Tabuleiro for um tabuleiro que nao tem nada ou tem relva nas % coordenadas (L, C). De notar que se as coordenadas nao fizerem parte do % tabuleiro, o predicado nao falha % ------------------------------------------------------------------------------ celulaVazia(Tabuleiro, (L, C)):- length(Tabuleiro,Comprimento), (L=<0; C=<0; Comprimento<L; Comprimento<C), !; (nth1(L, Tabuleiro, Linha), nth1(C, Linha, Objecto), (var(Objecto), !; Objecto == r)). % 4.2 Insercao de tendas e relva % ------------------------------------------------------------------------------ % insereObjectoCelula(Tabuleiro, TendaOuRelva, (L, C)) % eh verdade se Tabuleiro eh um tabuleiro e (L, C) sao as coordenadas onde % queremos inserir o objecto TendaOuRelva % ------------------------------------------------------------------------------ insereObjectoCelula(Tabuleiro, Objeto, (L, C)):- (nth1(L, Tabuleiro, Linha), nth1(C, Linha, Posicao), atomic(Posicao)), !; (substitui(Tabuleiro, L, Linha), substitui(Linha, C, Objeto)). substitui(Lista, Posicao, NovoElemento):- nth1(Posicao, Lista, _, ListaTemporaria), nth1(Posicao, NovaLista, NovoElemento, ListaTemporaria), Lista = NovaLista. % ------------------------------------------------------------------------------ % % ------------------------------------------------------------------------------ insereObjectoEntrePosicoes(_, _, (_, C1), (_, C2)):- C1 is C2 + 1, !. insereObjectoEntrePosicoes(Tabuleiro, TendaOuRelva, (L, C1), (L, C2)):- celulaVazia(Tabuleiro, (L, C1)), insereObjectoCelula(Tabuleiro, TendaOuRelva, (L, C1)), C1 \= C2 + 1, C is C1 + 1, insereObjectoEntrePosicoes(Tabuleiro, TendaOuRelva, (L, C), (L, C2)), !. insereObjectoEntrePosicoes(Tabuleiro, TendaOuRelva, (L, C1), (L, C2)):- C1 \= C2 + 1, C is C1 + 1, insereObjectoEntrePosicoes(Tabuleiro, TendaOuRelva, (L, C), (L, C2)). % 4.3 Estrategias % ------------------------------------------------------------------------------ % ------------------------------------------------------------------------------ relva((Tabuleiro,CLinhas,CColunas)):- calculaObjectosTabuleiro(Tabuleiro, ContagemLinhas, ContagemColunas, t), length(Tabuleiro, Tamanho), relva_aux(Tabuleiro,ContagemLinhas,CLinhas,1,Tamanho), transpose(Tabuleiro,Transposta), relva_aux(Transposta,ContagemColunas,CColunas,1,Tamanho). relva_aux(_,[],[],_,_). relva_aux(Tabuleiro, [L|R], [CC|Y], N, Tamanho):- L == CC, insereObjectoEntrePosicoes(Tabuleiro, r, (N, 1), (N, Tamanho)), K is N+1, relva_aux(Tabuleiro, R, Y, K, Tamanho), !. relva_aux(Tabuleiro, [_|R], [_|Y], N, Tamanho):- K is N+1, relva_aux(Tabuleiro, R, Y, K, Tamanho). % ------------------------------------------------------------------------------ % ------------------------------------------------------------------------------ inacessiveis(Tabuleiro):- todasCelulas(Tabuleiro, CelulasVazias, _), inacessiveisAux(Tabuleiro, CelulasVazias). inacessiveisAux(_, []). inacessiveisAux(Tabuleiro, [(L, C) | Resto]):- temArvoreNaVizinhanca(Tabuleiro, (L, C)), inacessiveisAux(Tabuleiro, Resto),!. inacessiveisAux(Tabuleiro, [(L,C) | Resto]):- insereObjectoCelula(Tabuleiro, r, (L, C)), inacessiveisAux(Tabuleiro, Resto). temArvoreNaVizinhanca(Tabuleiro, Posicao):- vizinhanca(Posicao, Vizinhanca), peloMenosUmaArvoreNaVizinhanca(Tabuleiro, Vizinhanca). peloMenosUmaArvoreNaVizinhanca(Tabuleiro, [Vizinha | _]):- ehArvore(Tabuleiro, Vizinha). peloMenosUmaArvoreNaVizinhanca(Tabuleiro, [_ | RestoVizinhanca]):- peloMenosUmaArvoreNaVizinhanca(Tabuleiro, RestoVizinhanca). ehArvore(Tabuleiro, (L, C)):- nth1(L, Tabuleiro, Linha), nth1(C, Linha, X), X == a. % ------------------------------------------------------------------------------ % ------------------------------------------------------------------------------ aproveita((Tabuleiro, Linhas, Colunas)) :- length(Tabuleiro, N), calculaObjectosTabuleiro(Tabuleiro, KLinhas, _, _), calculaObjectosTabuleiro(Tabuleiro, CLinhas, _, t), resolveLinhas(Tabuleiro, Linhas, CLinhas, KLinhas, N, 1), transpose(Tabuleiro, Transposto), calculaObjectosTabuleiro(Transposto, KKLinhas, _, _), calculaObjectosTabuleiro(Transposto, CCLinhas, _, t), resolveLinhas(Transposto, Colunas, CCLinhas, KKLinhas, N, 1). resolveLinhas(_, [], [], [], _, _):- !. resolveLinhas(Tabuleiro, [Linha|Linhas],[CLinha|Clinhas],[Klinha|Klinhas], N,L):- Maciel is CLinha + Klinha, Linha == Maciel, resolveLinha(Tabuleiro, N, L), L1 is L + 1, resolveLinhas(Tabuleiro, Linhas,Clinhas,Klinhas, N,L1). resolveLinhas(Tabuleiro, [_|Linhas],[_|Clinhas],[_|Klinhas], N,L):- L1 is L + 1, resolveLinhas(Tabuleiro, Linhas,Clinhas,Klinhas, N,L1). resolveLinha(Tabuleiro, N, L):- insereObjectoEntrePosicoes(Tabuleiro, t, (L, 1), (L, N)), !. % ------------------------------------------------------------------------------ % ------------------------------------------------------------------------------ limpaVizinhancas((Tabuleiro, _, _)):- todasCelulas(Tabuleiro, Tendas, t), maplist(limpaVizinhanca(Tabuleiro), Tendas). limpaVizinhanca(Tabuleiro, (L, C)):- length(Tabuleiro,Length), vizinhancaAlargada((L, C), Vizinhos), removeCoordenadasComZeros(Vizinhos, Length, ListaFiltrada), maplist(insereObjectoCelula(Tabuleiro, r), ListaFiltrada). invalida(Length,(L, C)):- (L =:= 0; C =:= 0; L =:= Length + 1; C =:= Length + 1). removeCoordenadasComZeros(ListaOriginal, Length, ListaFiltrada):- exclude(invalida(Length), ListaOriginal, ListaFiltrada). % ------------------------------------------------------------------------------ % ------------------------------------------------------------------------------ unicaHipotese((Tabuleiro, _, _)):- todasCelulas(Tabuleiro, Arvores, a), maplist(verificaUnicaHipotese(Tabuleiro), Arvores). verificaUnicaHipotese(Tabuleiro, (L, C)):- vizinhanca((L, C), Vizinhanca), length(Tabuleiro,Length), removeCoordenadasComZeros(Vizinhanca, Length, ListaFiltrada), countTendasVizinhanca(Tabuleiro, ListaFiltrada, Countendas), countVarVizinhanca(Tabuleiro, ListaFiltrada, Listvar), length(Listvar,Countvar), (Countendas =:= 0, Countvar =:= 1), nth1(1,Listvar,Position), insereObjectoCelula(Tabuleiro, t, Position),!. verificaUnicaHipotese(_, _). countTendasVizinhanca(_, [], 0). countTendasVizinhanca(Tabuleiro, [Vizinho | Resto], NewCount):- countTendasVizinhanca(Tabuleiro, Resto, Count), (vizinhoContemTenda(Tabuleiro, Vizinho)-> NewCount is Count + 1; NewCount is Count). countVarVizinhanca(_, [], []). countVarVizinhanca(Tabuleiro, [Vizinho | Resto], VarList):- countVarVizinhanca(Tabuleiro, Resto, CountList), (vizinhoContemEmpty(Tabuleiro, Vizinho) -> VarList = [(Vizinho)|CountList]; VarList = CountList). vizinhoContemTenda(Tabuleiro, (L, C)):- nth1(L, Tabuleiro, Linha), nth1(C, Linha, Posicao), Posicao == t. vizinhoContemEmpty(Tabuleiro, (L, C)):- nth1(L, Tabuleiro, Linha), nth1(C, Linha, ConteudoCelula), var(ConteudoCelula). % ------------------------------------------------------------------------------ % ------------------------------------------------------------------------------ valida([], []). valida([(L, C) | RestoArv], LTen):- vizinhanca((L, C), Vizinhanca), chooseCommonElement(LTen, Vizinhanca, CommonElement), delete(LTen, CommonElement, NewLTent), valida(RestoArv, NewLTent),!. chooseCommonElement(List1, List2, CommonElement):- member(CommonElement, List1), member(CommonElement, List2). % ------------------------------------------------------------------------------ % ------------------------------------------------------------------------------ resolve((Tabuleiro, Linhas, Colunas)):- inacessiveis(Tabuleiro), resolve_aux((Tabuleiro, Linhas, Colunas)), validaPuzzle(Tabuleiro, Linhas, Colunas). resolve_aux((Tabuleiro, Linhas, Colunas)):- aplicaEstrategias(Tabuleiro, Linhas, Colunas), todasCelulas(Tabuleiro, Tendas, t), todasCelulas(Tabuleiro, Arvores, a), length(Tendas,X), length(Arvores,Y), (X == Y -> valida_Masterclass(Tabuleiro, Linhas, Colunas)); (todasCelulas(Tabuleiro, CelulasVazias, _), member((L, C), CelulasVazias), insereObjectoCelula(Tabuleiro, t, (L, C)), valida_Masterclass(Tabuleiro, Linhas, Colunas), resolve_aux((Tabuleiro, Linhas, Colunas))). aplicaEstrategias(Tabuleiro, Linhas, Colunas) :- todasCelulas(Tabuleiro, VaziasIniciais, _), limpaVizinhancas((Tabuleiro, _, _)), relva((Tabuleiro, Linhas, Colunas)), aproveita( (Tabuleiro, Linhas, Colunas)), unicaHipotese((Tabuleiro, _, _)), todasCelulas(Tabuleiro, VaziasFinais, _), (VaziasIniciais == VaziasFinais;VaziasFinais == []; aplicaEstrategias(Tabuleiro, Linhas, Colunas)),!. validaPuzzle(Tabuleiro, Linhas, Colunas):- calculaObjectosTabuleiro(Tabuleiro, ContagemLinhas, ContagemColunas, t), Linhas == ContagemLinhas, Colunas == ContagemColunas, todasCelulas(Tabuleiro, LArv, a), todasCelulas(Tabuleiro, LTend, t), valida(LArv, LTend), !. valida_Masterclass(Tabuleiro, Linhas, Colunas):- calculaObjectosTabuleiro(Tabuleiro, ContagemLinhas, ContagemColunas, t), maplist(>=,Linhas,ContagemLinhas), maplist(>=,Colunas,ContagemColunas). puzzle(6-13, ([ [_, _, _, _, a, _], [a, _, _, _, _, a], [_, _, _, a, _, _], [_, _, _, _, a, _], [_, _, a, _, _, _], [_, _, a, _, _, _]], [2, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2])). puzzle(6-14, ([ [_, a, _, a, _, _], [a, _, _, _, _, _], [_, _, _, _, _, _], [_, _, a, a, _, _], [_, _, _, _, _, _], [_, a, _, _, a, _]], [3, 0, 1, 1, 1, 1], [2, 1, 1, 1, 2, 0])). puzzle(8-1, ([ [_, _, _, _, a, _, a, _], [a, _, _, _, _, _, _, a], [_, _, _, _, _, _, _, _], [_, a, _, _, a, _, _, _], [_, _, _, a, _, a, a, a], [a, _, _, _, _, _, _, _], [_, _, a, _, _, _, _, _], [_, _, _, a, _, _, _, _]], [4, 0, 1, 2, 1, 3, 0, 2], [2, 0, 2, 2, 2, 2, 1, 2])).