1

I am trying to generate pieces on a board at specific positions. One requirement is no two pieces can occupy the same position. So the board as a list, cannot contain duplicate entries for it's position value.

I failed to remove the duplicates in generation part, otherwise it correctly fails on duplicates if I ask it explicitly.

role(k).
role(r).

color(w).
color(b).

piece(X-Y) :- color(X), role(Y).

piese(X-Y) :- piece(X), pos_(Y).

piese_pos(X, Y) :- X=_-_-Y.

board(Ps) :- maplist(piese_pos, Ps, Ls), is_set(Ls), maplist(piese, Ps).

pos_(a-1).
pos_(a-2).
/*
When I ask board board(X). This is one of the enumerations:
X = [w-k-(a-1), b-k-(a-2), w-r-(a-2)] ;
as you can see a-2 is duplicated.

But if I ask for a duplicate explicitly, it returns false as correct.
[11]  ?- board([w-k-(a-1), b-r-(a-1)]).
false.

[11]  ?- board([w-k-(a-1), b-r-(a-2)]).
true.
*/

% https://stackoverflow.com/a/9007359/3994249
is_set(Lst) :-
  setof(X, member(X, Lst), Set),
  length(Lst, N),
  length(Set, N).
eguneys
  • 6,028
  • 7
  • 31
  • 63

4 Answers4

1

The board rule appears to generate "false" solutions because no values have been bound yet when the is_set check takes place. When you pass in a result that has actual values, is_set will be false as expected. To see this happening, run only the first two conditions of board/1:

?- maplist(piese_pos, Ps, Ls), is_set(Ls).
Ps = [_2962-_2964-_2950],
Ls = [_2950] ;
Ps = [_2962-_2964-_2950, _4224-_4226-_4212],
Ls = [_2950, _4212] ;
Ps = [_2962-_2964-_2950, _4224-_4226-_4212, _5550-_5552-_5538],
Ls = [_2950, _4212, _5538] ;
Ps = [_2962-_2964-_2950, _4224-_4226-_4212, _5550-_5552-_5538, _6932-_6934-_6920],
Ls = [_2950, _4212, _5538, _6920] ;
...

While this appears to be generating the "structure" of the answer, no values are being bound yet and the is_set call will always succeed here on empty variable positions. Switching the order of the predicates produces the results you may be looking for but will highlight the another issue:

?- maplist(piese_pos, Ps, Ls), maplist(piese, Ps), is_set(Ls).
Ps = [w-k-(a-1)],
Ls = [a-1] ;
Ps = [w-k-(a-2)],
Ls = [a-2] ;
Ps = [w-r-(a-1)],
...
Ps = [b-r-(a-2), b-r-(a-1)],
Ls = [a-2, a-1] ;
... (no response)

After enumerating all expected solutions with both of the positions currently defined, it will loop endlessly as the first maplist will continue unbounded, generating duplicate positions in an ever growing list. Adding condition to cut the search at that point may be what you want, or a different approach first enumerating positions then placing pieces in them could be easier.

rayscan
  • 301
  • 2
  • 6
1

Assuming that every position on the board must have a piece, you can generate boards with the following code:

board(Ps) :-
    setof(P, pos_(P), Ls),     
    maplist(piese_pos, Ps, Ls),
    maplist(piese, Ps).

Example:

?- board(Ps).
Ps = [w-k-(a-1), w-k-(a-2)] ;
Ps = [w-k-(a-1), w-r-(a-2)] ;
Ps = [w-k-(a-1), b-k-(a-2)] ;
Ps = [w-k-(a-1), b-r-(a-2)] ;
Ps = [w-r-(a-1), w-k-(a-2)] ;
Ps = [w-r-(a-1), w-r-(a-2)] ;
Ps = [w-r-(a-1), b-k-(a-2)] ;
Ps = [w-r-(a-1), b-r-(a-2)] ;
Ps = [b-k-(a-1), w-k-(a-2)] ;
Ps = [b-k-(a-1), w-r-(a-2)] ;
Ps = [b-k-(a-1), b-k-(a-2)] ;
Ps = [b-k-(a-1), b-r-(a-2)] ;
Ps = [b-r-(a-1), w-k-(a-2)] ;
Ps = [b-r-(a-1), w-r-(a-2)] ;
Ps = [b-r-(a-1), b-k-(a-2)] ;
Ps = [b-r-(a-1), b-r-(a-2)].

Otherwise, you can use this other definition:

board(Ps) :-
    setof(P, pos_(P), S),
    set_subset(S, Ls),
    maplist(piese_pos, Ps, Ls),
    maplist(piese, Ps).

set_subset([], []).
set_subset([X|Xs], S) :-
    set_subset(Xs, T),
    (   S = T
    ;   S = [X|T] ).

Example:

?- board(Ps).
Ps = [] ;
Ps = [w-k-(a-1)] ;
Ps = [w-r-(a-1)] ;
Ps = [b-k-(a-1)] ;
Ps = [b-r-(a-1)] ;
Ps = [w-k-(a-2)] ;
Ps = [w-r-(a-2)] ;
Ps = [b-k-(a-2)] ;
Ps = [b-r-(a-2)] ;
Ps = [w-k-(a-1), w-k-(a-2)] ;
Ps = [w-k-(a-1), w-r-(a-2)] ;
Ps = [w-k-(a-1), b-k-(a-2)] ;
Ps = [w-k-(a-1), b-r-(a-2)] ;
Ps = [w-r-(a-1), w-k-(a-2)] ;
Ps = [w-r-(a-1), w-r-(a-2)] ;
Ps = [w-r-(a-1), b-k-(a-2)] ;
Ps = [w-r-(a-1), b-r-(a-2)] ;
Ps = [b-k-(a-1), w-k-(a-2)] ;
Ps = [b-k-(a-1), w-r-(a-2)] ;
Ps = [b-k-(a-1), b-k-(a-2)] ;
Ps = [b-k-(a-1), b-r-(a-2)] ;
Ps = [b-r-(a-1), w-k-(a-2)] ;
Ps = [b-r-(a-1), w-r-(a-2)] ;
Ps = [b-r-(a-1), b-k-(a-2)] ;
Ps = [b-r-(a-1), b-r-(a-2)].
slago
  • 5,025
  • 2
  • 10
  • 23
0

tldr: is_set(Ls), maplist(piese, Ps) checks unbound variables before they have values. After that, duplicate values can get in. Do these two things the other way around.

The problem is shown in this trace of your code generating a board of length 2:

  • At the top arrow the board must have two things in it, they are shown as variables with no human given name, and no value so they get automatic names of _840 and _846.

  • At the pair of arrows, the maplist call has got the right pattern of [A-B-C, X-Y-Z] for the board contents, with automatic names for the variables to hold each part.

  • At the last arrow, unknown variables for the positions have been stripped off and handed to is_set. Still with no values, two unground variables are a set, so they get past the check.

Showing the trace of generating the board

After that, you put values in the variables, no more checks are done.

Change:

board(Ps) :- maplist(piese_pos, Ps, Ls), is_set(Ls), maplist(piese, Ps).

to:

board(Ps) :- maplist(piese_pos, Ps, Ls), maplist(piese, Ps), is_set(Ls).

Then piese searches for values before is_set checks for duplicates.

Logically there may be no difference, but practically Prolog systems can't do everything at once and must do some things first and some later.

TessellatingHeckler
  • 27,511
  • 4
  • 48
  • 87
0

Here's a simple version, that is pure logical. https://stackoverflow.com/a/8523825/3994249

board([]).
board([P]) :- pos(P).
board([_-Pos,_-Pos2]) :- pos(Pos), pos(Pos2), dif(Pos, Pos2).
board([X,Y|Rest]) :- board([X|Rest]), board([Y|Rest]), board([X,Y]).
eguneys
  • 6,028
  • 7
  • 31
  • 63