Search code examples
prologpuzzleclpfd

PROLOG - Checking for correct placement


I have a puzzle that is a 3*3 grid with numbers 1-8 in them, with a blank spot (0) that I can move around. This is the final state of the puzzle:

1 2 3 
8 0 4 
7 6 5

This whole "state" is represented by state(1,2,3,8,0,4,7,6,5), by reading horizontally. I need a function to check to see which pieces are in the right spots.

I have:

h(state(A,B,C,D,E,F,G,H,I),Z) :-

Now Z is going to be the number of pieces in the correct spot.

A = 1
B = 2
C = 3
D = 8
E = 0
F = 4
G = 7
H = 6
I = 5

Is there any easy way to give an output for Z? Any help would be appreciated. Thanks.


Solution

  • this seems rather simple to do...

    h(state(A,B,C,D,E,F,G,H,I),Z) :-
        count_matching([A,B,C,D,E,F,G,H,I], [1,2,3,8,0,4,7,6,5], 0, Z).
    
    count_matching([], [], N, N).
    count_matching([A|As], [B|Bs], N, M) :-
        (   A == B
        ->  T is N + 1
        ;   T is N
        ),
        count_matching(As, Bs, T, M).
    

    SWI-Prolog aggregate library offers another easy way to solve your problem:

    :- [library(aggregate)].
    
    h(state(A,B,C,D,E,F,G,H,I),Z) :-
        aggregate_all(count,
          (nth1(Index, [1,2,3,8,0,4,7,6,5], Cell),
           nth1(Index, [A,B,C,D,E,F,G,H,I], Cell)), Z).
    

    Using aggregate_all is overkill: here a simpler program using the same schema (non deterministic access to elements via nth/3):

    h(state(A,B,C,D,E,F,G,H,I),Z) :-
        findall(_,
          (nth1(Index, [1,2,3,8,0,4,7,6,5], Cell),
           nth1(Index, [A,B,C,D,E,F,G,H,I], Cell)), L),
        length(L, Z).