/************************************************************************/
/*                                                                      */
/* XSB System								*/
/* Copyright (C) SUNY at Stony Brook, 1986, 1993; ECRC, 1990		*/
/*                                                                      */
/* Everyone is granted permission to copy, modify and redistribute XSB  */
/* but only under the conditions described in the XSB Licence Agreement.*/
/* A copy of this license is supposed to have been given to you along	*/
/* with XSB so you can know your rights and responsibilities.		*/
/* It should be in a file named LICENSE.				*/
/* Among other things, this notice must be preserved on all copies.	*/
/*									*/
/************************************************************************/

/*======================================================================
  File			:  ham.P
  Author(s)		:  Some ECRC guy
  Modified by		:  Mauricio Ayala Rincon
  Last modification	:  October 24, 1995
========================================================================*/

/************************************************************************/
% Solucao ao problema das Rainhas:
%
%                         distribuicao de oito rainhas no tablero
%                         de xadrez, de maneira tal que nenhuma
%                         delas seja atacada por outra.
%                         O problema se geraliza para tableros de
%                         ordem n x n, n>0.
%
% A solucao e um exemplo tipico de manuseio de informacao negativa
% em programas logicos (programas normais).  Observe que para expre-
% ssar que duas damas nao ocupam a mesma diagonal o mais simples e
% dizer que as sumas e restas de suas coordenadas NAO sao iguais,
% respectivamente.
%
% Para restringir o espaco de busca uma lista de possiveis posicoes e
% passada ao procedimento de geracao da sequencia de posicoes solucao;
% se uma columna e selecionada da lista entao o valor deve ser eliminado
% da lista.  Assim que nao e mais necessario testar as restricoes verti-
% cais e horizontais.
/************************************************************************/

go :-	cputime(T1), ( go(8, _), fail; true ), 
	cputime(T2), T is T2 - T1, 
	write('Time used: '), write(T), write(' sec'), nl.

demo(N) :- cputime(T1), demo1(N), cputime(T2), T is T2 - T1,
	write('Time used: '),  write(T), write(' sec'), nl.

demo1(N) :- go(N, Soln), 
	 write(Soln), nl, fail.
demo1(N).

demo2(N) :- cputime(T1), demo3(N), cputime(T2), T is T2 - T1,
	write('Time used: '),  write(T), write(' sec'), nl.

demo3(N) :- go(N, Soln), 
	 write(Soln), nl.
demo3(N).

go( Size, Solucao ):-
	posicao_filas( Size, PosicaoList ), 
	solucionar( PosicaoList, 0, [], Solucao ).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% predicado basico de geracao de solucoes.

solucionar( [Posicao1|RestPosicao], Col, Atual, Final ):-
	Col1 is Col+1, 
	delete( [Posicao1|RestPosicao], Fila, NewPosicaoFilas ), 
	sem_conflito( Col1, Fila, Atual ), 
	solucionar( NewPosicaoFilas, Col1, [s( Col1, Fila ) | Atual], Final ).
solucionar( [], _, Final, Final ).


%%%%%%%%%%%%%%%%%%%%%%%%%%
% predicado de eliminacao. 

delete( [Y|L], X, [Y|M] ):-
	delete( L, X, M ).
delete( [X|L], X, L ).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% predicados de teste por diagonais.

igual_diagonal( X, Y, I, J ):-
	U is X+Y, 
	U is I+J.
igual_diagonal( X, Y, I, J ):-
	U is X-Y, 
	U is I-J.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% predicado de teste de conflitos (so se testam conflitos nas diagonais).
		
sem_conflito( X, Y, [s( I, J )|Rest] ):-
	not( igual_diagonal( X, Y, I, J ) ), 
	sem_conflito( X, Y, Rest ).
sem_conflito( _, _, [] ).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% predicado de geracao da lista de filas.

posicao_filas( N, R ) :- posicao_filas_extra( N, [], R ).

posicao_filas_extra( 0, L, L ).
posicao_filas_extra( N, K, L ) :- N > 0,
	N1 is N-1, 
	posicao_filas_extra( N1, [N|K], L ).