Search code examples
prologclpfd

Manipulating Prolog code output

I am trying to run code on this page: https://swish.swi-prolog.org/example/clpfd_queens.pl in swipl on a Linux terminal. 

:- use_module(library(clpfd)).

n_queens(N, Qs) :-
    length(Qs, N),
    Qs ins 1..N,
    safe_queens(Qs).

safe_queens([]).
safe_queens([Q|Qs]) :-
    safe_queens(Qs, Q, 1),
    safe_queens(Qs).

safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
    Q0 #\= Q,
    abs(Q0 - Q) #\= D0,
    D1 #= D0 + 1,
    safe_queens(Qs, Q0, D1).

Following command works: 

?- n_queens(4, Qs), labeling([ff], Qs).

But not just n_queens(4, Qs): 

?- n_queens(4, Qs).
Qs = [_G1470, _G1473, _G1476, _G1479],
_G1470 in 1..4,
abs(_G1470-_G1479)#\=3,
_G1470#\=_G1479,
abs(_G1470-_G1476)#\=2,
_G1470#\=_G1476,
abs(_G1470-_G1473)#\=1,
_G1470#\=_G1473,
_G1479 in 1..4,
abs(_G1476-_G1479)#\=1,
_G1476#\=_G1479,
abs(_G1473-_G1479)#\=2,
_G1473#\=_G1479,
_G1476 in 1..4,
abs(_G1473-_G1476)#\=1,
_G1473#\=_G1476,
_G1473 in 1..4.

Why is labeling part needed here? Can one get proper output without labeling part?

For larger numbers, one gets only initial part of the solution: 

?- n_queens(20, Qs), labeling([ff], Qs).
Qs = [1, 3, 5, 14, 17, 4, 16, 7, 12|...] ;
Qs = [1, 3, 5, 18, 16, 4, 10, 7, 14|...] ;
...

How can one get full list output for larger numbers? Also, how can one get all numbers together, without having to press spacebar for each solution? Thanks for your help.

Solution

  • n_queens/2 does not solves the N-queens problem for N queens: it constructs the constraint programming problem: it constructs N variables (the columns of the queens), and adds constraints between these queens: for instance that two queens can not be placed on the same row, nor on the same diagonal. We see this if we rewrite the problem output to more convenient output:

    A in 1..4,
abs(A-D)#\=3,
A#\=D,
abs(A-C)#\=2,
A#\=C,
abs(A-B)#\=1,
A#\=B,
D in 1..4,
abs(C-D)#\=1,
C#\=D,
abs(B-D)#\=2,
B#\=D,
C in 1..4,
abs(B-C)#\=1,
B#\=C,
B in 1..4.

    So we see four queens (A, B, C and D). Each of the queens should be in the domain 1..4, furthermore we see non equal constraints like A #\= D to prevent the first queen A sharing a column with the last queen D. We finally see constraints like abs(A-C) #\= 2 to prevent the first queen A and the third queen C to differ two columns (diagnal attack).

    Next labeling/2 will actually solve the problem: it performs relaxation (reducing the domains) as well as branching (picking a value or a subrange of values for variables) and backtracking in case the constraints fail. It will continue until it finds a solution, and we can use Prolog's backtracking mechanism to let labeling/2 come up with more solutions.

    labeling thus is given a list of variables and aims to label them: assign them a value out of the range such that all constraints are satisfied.

    Therefore the problem construction part is usually very fast compared to the actually solving part: it is easy to generate O(N) variables and O(N2) constraints, but it can take an exponential amount of time O(DN) to come up with a solution satisfying all constraints.

    Also, how can one get all numbers together, without having to press spacebar for each solution?

    You can use the meta-predicate findall/3 for that:

    all_n_queens(N,LL) :-
    findall(L,(n_queens(N,L), labeling([ff], L)),LL).

    Which generates:

    ?- all_n_queens(5,LL).
LL = [[1, 3, 5, 2, 4], [1, 4, 2, 5, 3], [2, 4, 1, 3, 5], [2, 5, 3, 1, 4], [3, 1, 4, 2|...], [3, 5, 2|...], [4, 1|...], [4|...], [...|...]|...].

    How can one get full list output for larger numbers?

    You can set the answer_write_options flag:

    ?- set_prolog_flag(answer_write_options,[max_depth(0)]).
true.

?- all_n_queens(5,LL).
LL = [[1,3,5,2,4],[1,4,2,5,3],[2,4,1,3,5],[2,5,3,1,4],[3,1,4,2,5],[3,5,2,4,1],[4,1,3,5,2],[4,2,5,3,1],[5,2,4,1,3],[5,3,1,4,2]].