In deze oefeningen zullen we een schuifpuzzel oplossen met iterative deepening depth-first search1. De volgende code implementeert dit principe.

solve(A, Solution) :- between(1, 25, I), solve(A, [A], I, Solution), !.

solve(_, _, 0, _)                   :- !, fail.
solve(State, Solution, _, Solution) :- goal(State), !.
solve(State, Visisted, D, Solution) :-
    successor(State, NextState),
    \+ member(NextState, Visisted),
    D1 is D-1,
    solve(NextState, [NextState|Visisted], D1, Solution).

De implementatie van successor/2 ontbreekt, die moet jij aanvullen.

Representatie

4 bij 4 schuifpuzzel met waarden van links naar rechts boven naar onder: 15, 2, 1, 12, 8, 5, 6, 11, 4, 9, 10, 7, 3, 14, 13

De status van de puzzel is voorgesteld door een rij van posities: [PosEmpty, Pos1, Pos2, Pos3 | ....]. Hierbij is elke positie in de lijst van de vorm Rij/Kolom. De waarde op index \(i\) geeft aan waar het cijfer \(i\) in de puzzel staat. De eerste waarde van de lijst (\(i=0\)) geeft aan waar het gat zit.

De afbeelding bij deze oefening zou voor worden gesteld als:

4/4,1/3,1/2,4/1,2/2,2/3,3/4,2/1,3/2,3/3,2/4,1/4,4/3,4/2,1/1

Het lege vak staat op 4/4, 1 staat op 1/3, 2 op 1/2, …

Geldige zetten

Jouw implementatie van successor/2 moet waar zijn als en slechts als het eerste argument kan omgezet worden in het tweede door middel van een schuifbeweging op de puzzel. Bij elke beweging verplaatst er hoogstens 1 vakje.

Gebruik

Om je code te testen kun je gebruik maken van deze database2, ze bevat de solve/2 van hierboven en een goal/1. solve(Bord,Stappen) unificeert Stappen met een lijst van borden die successor zijn van elkaar zodat het eerste bord de opgeloste puzzel is en het laatste bord het bord is dat als eerste argument werd meegegeven aan solve/2.

Nota: Iterative deepening depth-first search heeft een tijdscomplexiteit van \(O(b^d)\) waarbij \(b\) de vertakkingsfactor (het maximaal aantal oplossingen dat successor/2 kan geven) en \(d\) is de diepte van de eerste oplossing. In het slechtste geval zijn er voor een 3 bij 3 puzzel 31 schuifbewegingen nodig…

A* zoeken is een betere manier om dit probleem aan te pakken.