%% Programa que juega al gato
%%
%% Una posicion se representa mediante una matriz M de 3x3, por ejemplo:
%%    [[sp,x,sp],[o,x,sp],[sp,o,sp]]
%% Un elemento en sp significa que nadie ha jugado todavia ahi.
%%
%% Uso
%% ***
%%
%% Si le toca jugar a x en la posicion M:
%% ?- jugada_ganadora(x,o,M,R).
%% Determina que las posiciones R que incluyen una jugada adicional de x
%% en donde x tiene ganada la partida.
%% Si no existe una jugada ganadora, la respuesta es no.
%%
%% Dada la posicion M, le toca jugar a x, pero no puede ganar, donde
%% puede jugar para no perder?
%% 
%% ?- jugada(x,o,M,R), not(jugada_ganadora(o,x,R,)).

%% Queries interesantes:
%% si la primera jugada va al centro, donde se puede jugar para no perder?
%% ?- jugada(o,[[sp, sp, sp], [sp, x, sp], [sp, sp, sp]],R),
%%    not(jugada_ganadora(x,o,R,_)).
%% solo 4 soluciones: las esquinas.
%% si la primera jugada no va al centro, tiene o ganado el juego?
%% ?- jugada_ganadora(o,x,[[sp, sp, sp], [x, sp, sp], [sp, sp, sp]],M).
%% No

%% traspuesta(M,T): la matriz traspuesta de M es T.
traspuesta([[]|_],[]).
traspuesta(M,[C|T]) :- separar(M,C,MT),traspuesta(MT,T).

%% separar(M,C,R): la primera columna de la matriz M es C y R es una matriz
%% que contiene el resto de las columnas de M (excluyendo la primera).
separar([[X|F]|M],[X|C],[F|MT]) :- separar(M,C,MT).
separar([],[],[]).

%% ganofil(X,M) existe una fila de M en donde X completo la fila
%% (X= x o bien o).
ganofil(X,M) :- member([X,X,X],M).

%% gano(X,M) existe una fila, una columna o una diagonal en donde X gano
gano(X,M) :- ganofil(X,M).
gano(X,M) :- traspuesta(M,T),ganofil(X,T).
gano(X,M) :- M=[[X,_,_],[_,X,_],[_,_,X]].
gano(X,M) :- M=[[_,_,X],[_,X,_],[X,_,_]].

%% jugada(X,M,R): R es una nueva posicion que se obtiene cuando X
%% realiza una jugada en la posicion M.  Significa cambiar un sp por X
%% (x o bien o).
jugada(X,[F|M],[G|M]) :- eleccion_fila(X,F,G).
jugada(X,[F|M],[F|R]) :- jugada(X,M,R).

%% eleccion_fila(X,F,G): G es la nueva fila que se obtiene cuando X realiza
%% una jugada en F.  Significa cambiar un sp por X.
eleccion_fila(X,[sp|F],[X|F]).
eleccion_fila(X,[Y|F],[Y|G]) :- eleccion_fila(X,F,G).

%% En la posicion M, si X juega tal que la nueva posicion es R, X le gana a Y.
jugada_ganadora(X,Y,M,R) :- not(gano(Y,M)), jugada(X,M,R), pos_ganadora(X,Y,R).

%% pos_ganadora(X,Y,R): la posicion R es ganadora para X que juega con Y.
pos_ganadora(X,_,R) :- gano(X,R).
pos_ganadora(X,Y,R) :- not(salvacion(Y,X,R)).

%% salvacion(Y,X,R): Y tiene salvacion en la posicion R jugando contra X
%% (es decir no pierde).
salvacion(Y,_,R) :- not(jugada(Y,R,_)).
salvacion(Y,X,R) :- jugada(Y,R,S),not(jugada_ganadora(X,Y,S,_)).


%% Incorrecto:
%% pos_ganadora(X,_,R) :- gano(X,R).
%% pos_ganadora(X,Y,R) :-
%%     not(jugada_ganadora(Y,X,R,_)),
%%     elegir(Y,R,S),
%%     jugada_ganadora(X,Y,S,_).