% $Id: parqueens.pl,v 1.1 2006/12/04 18:58:55 nunomorgadinho Exp $

:- initialization(init).

% include the pm2 interface lib
:- include('lib').

size(8).

determine(Size):-
  argument_counter(2),
  argument_list(Args),
  append([SizeString|_], [], Args),
  write_to_chars(Chars, SizeString),
  number_chars(Size, Chars).
  
determine(Size):-
  size(Size),
  write('Going for size of '),write(Size),write('.'),nl.

start_prolog_workers(0):- !. % on master dont start
start_prolog_workers(VP):-
  % thread_create(+Goal, +VP, -Id)
  thread_create(_, VP, _),
  VP1 is VP - 1,
  start_prolog_workers(VP1).

stop_prolog_workers(0):- !. % on master dont stop
stop_prolog_workers(VP):-
  thread_send_message(vid(VP,0), unlock),
  VP1 is VP - 1,
  stop_prolog_workers(VP1).

test_prolog_workers(0):- !. % on master dont do it
test_prolog_workers(VP):-
  thread_send_message(vid(VP,0), teste),
  VP1 is VP - 1,
  test_prolog_workers(VP1).

read_test(0):- !. % on master dont do it
read_test(VP):-
  thread_get_message(X),
  VP1 is VP - 1,
  read_test(VP1).

% thread 0
init:-
  pm2_is_master,!,
  pm2_max_rank(MaxRank),
  
  determine(N),
    
  % Start_Prolog(0, 0) on each node
  start_prolog_workers(MaxRank),

  column(N, I),          % coluna ate' onde se gera config valida
  % gerar configuracao possivel ate' ah coluna i 
  findall(ParcialSolution, mkmaxlist(I, N, ParcialSolution), G),
  length(G, GL),

  send_job_worker(G, GL, N, MaxRank),
  read_results(GL, NumSolutions),
  write(NumSolutions),nl,
  
%  test_prolog_workers(MaxRank),      %%% for t(0) uncomment
%  read_test(MaxRank),                %%% for t(0) uncomment

  stop_prolog_workers(MaxRank),
  
  finish_listeners.

% thread != 0
init:-
  spawn(sleep, ['1']),
  worker_work.

init.

% -------------------------------------------------------------------

worker_work:-
        % entretanto o unlock e' feito quando for recebida uma msg
        !, thread_get_message_loop,
        worker_work.

worker_work:-
  write('worker_work falhou'),nl,!,fail.

% tirar todas as mensagens da queue
thread_get_message_loop:-
  pm2_self(Rank),
  thread_get_message(Termo),
  !, trick(Termo, X), !,
%  write('Worker '),write(Rank),write(' -> '),
%  write(Termo), write(','), write(X), nl,
  thread_send_message(vid(0,0), X),
  thread_get_message_loop.

% -------------------------------------------------------------------

read_results(X, N):-
  read_results(X, 0, N).

read_results(0, N, N):-!.
read_results(X, Acc, N):-
        thread_get_message(Msg),
        Msg == 1,
        Acc1 is Acc + 1,
%        write('Master -> '),write(Msg),nl,
        X1 is X - 1,
        !, read_results(X1, Acc1, N).

read_results(X, Acc, N):-
%        write('Master -> '),write(Msg),nl,
        X1 is X - 1,
        !, read_results(X1, Acc, N).

% -----------------------------------------------------------------------

trick(teste, ok).

trick(q(N, List), NumSolutions):-
  pm2_self(Rank),
  findall(L, solution_queens(List, N, L), G),
  length(G, NumSolutions).
  
send_job_worker([], 0, _, _):- !.

send_job_worker(L, C, N, 0):-
  pm2_max_rank(MaxRank),
  !, send_job_worker(L, C, N, MaxRank).

send_job_worker([H|Tail], Counter, N, Rank):-
%  write(Rank),write('=>'),write(H),nl,
  thread_send_message(vid(Rank,0), q(N, H)),
  Counter1 is Counter - 1,
  NextRank is Rank - 1,
  send_job_worker(Tail, Counter1, N, NextRank).


% -----------------------------------------------------------------------

column(N, X):-
  X is N - 4.


% como é que vou gerar as configurações sem ser
% permutações?
% gerar logo todas as permutações no master até ah coluna i
% com o findall

init_antigo:-
  for(X, 1, 16),
  go(X).
  

go(N):-
  findall(Y, teste(N, Y), G),
  length(G, GL),
  write(N),write(': '),write(GL),write(' total solutions.'),nl,fail.

teste(N, L):-
  column(N, I),          % coluna ate' onde se gera config valida
  % gerar configuracao possivel ate' ah coluna i 
  mkmaxlist(I, N, ParcialSolution).
  
  % dada uma permutacao gera uma configuracao valida
  % para o problema das N rainhas
  %solution_queens(ParcialSolution, N, L).

% solution_queens(+ParcialSolution, -Solution)
solution_queens([], _, _):- fail.
solution_queens(L, N, PossibleSolution):-
  % primeiro ver quantas rainhas ainda faltam colocar
  column(N, I),
  MissingQueens is N - I,
  % fazer o append das variaveis das possiveis colocacoes que faltam
  % criar primeiro uma lista de variaveis do tamanho MissingQueens
  mkemptylist(MissingQueens, EL),
  append(L, EL, NL),
  
  % calcular todas as permutacoes dos elementos nas posicoes que
  % restam, i.e., i ate' N
  % criar uma lista de tamanho MissingQueens e gerar permutacoes
  mkmaxlist(MissingQueens, N, PossibleParcialSolution),
  
  cross_lists(NL, PossibleParcialSolution, PossibleSolution),
  % ver se e' solucao
  queens(N, PossibleSolution).

cross_lists([], _, []):-!.
cross_lists(_, [], []):-!.
cross_lists([X|Xs], [Y|Ys], [Y|R]):-
  var(X),
  nonvar(Y),
  cross_lists(Xs, Ys, R).
cross_lists([X|Xs], [Y|Ys], [X|R]):-
  nonvar(X),
  cross_lists(Xs, [Y|Ys], R).



% gera uma lista de tamanho Size com elementos de 1 ate' N
% mkmaxlist(+Size, +N, -List)
mkmaxlist(S, N, [X|R]):-
  S > 0, 
  for(X, 1, N),
  S1 is S - 1,
  mkmaxlist(S1, N, R).
mkmaxlist(0, _, []).
  
mkemptylist(N, [_|R]):-
  N > 0,
  M is N - 1,
  !, mkemptylist(M, R).
mkemptylist(_, []).


% queens(+BoardSize, -ResultBoard)
queens(N, Qs):-
  range(1,N,Ns),
  permutation(Ns,Qs),
  safe(Qs).

safe([Q|Qs]):- safe(Qs), \+ attack(Q,Qs).
safe([]).

attack(X,Xs):- attack(X,1,Xs).
attack(X,N,[Y|_]):- X is Y + N.
attack(X,N,[Y|_]):- X is Y - N.
attack(X,N,[_|Ys]):- N1 is N + 1, attack(X,N1,Ys).


range(N,N,[N]):- !.

range(M,N,[M|Ns]):-
	M < N,
	M1 is M+1,
	range(M1,N,Ns).




