SWISH -- SWI-Prolog for SHaring

% p_4_reinas.pl
% El problema de las 4 reinas.
% José A. Alonso Jiménez <https://jaalonso.github.io>
% Sevilla, 25-mayo-2022
% ======================================================================

% Descripción del problema
% ========================

% Colocar 4 reinas en un tablero rectangular de dimensiones 4 por 4 de
% forma que no se encuentren más de una en la misma línea: horizontal,
% vertical o diagonal.

% Representación de los estados
% =============================

% Un ESTADO es un átomo de la lista de números que representa las
% ordenadas de las respectivas reinas. Por ejemplo, [3,1] representa que
% se ha colocado las reinas (1,1) y (2,3).

% estado_inicial(?E) se verifica si E es el estado inicial.
estado_inicial([]).

% estado_final(?E) se verifica si E es un estado final.
estado_final(E) :-
   length(E,4).

% sucesor(+E1,?E2) se verifica si E2 es un sucesor del estado E1.
sucesor(E,[Y|E]) :-
   member(Y,[1,2,3,4]),
   not(member(Y,E)),
   no_ataca(Y,E).

% no_ataca(Y,E) se verifica si E=[Y_n,...,Y_1], entonces la reina
% colocada en (n+1,Y) no ataca a las colocadas en (1,Y_1),...,(n,Y_n).
no_ataca(Y,E) :-
   no_ataca(Y,E,1).
no_ataca(_,[],_).
no_ataca(Y,[Y1|L],D) :-
   Y1-Y =\= D,
   Y-Y1 =\= D,
   D1 is D+1,
   no_ataca(Y,L,D1).

% Búsqueda en profundidad sin ciclos
% ==================================

% La solución es
%    ?- use_module(b_profundidad_sin_ciclos).
%    true.
%
%    ?- profundidad_sin_ciclos(S).
%    S = [[], [2], [4, 2], [1, 4, 2], [3, 1, 4, 2]]
%    ?- trace(estado_final,+call).
%    %         estado_final/1: [call]
%    true.
%
%    ?- profundidad_sin_ciclos(S).
%     T Call: estado_final([])
%     T Call: estado_final([1])
%     T Call: estado_final([3, 1])
%     T Call: estado_final([4, 1])
%     T Call: estado_final([2, 4, 1])
%     T Call: estado_final([2])
%     T Call: estado_final([4, 2])
%     T Call: estado_final([1, 4, 2])
%     T Call: estado_final([3, 1, 4, 2])
%    S = [[], [2], [4, 2], [1, 4, 2], [3, 1, 4, 2]]
%
%    ?- trace(estado_final,-call).
%    %         estado_final/1: Not tracing
%    true.