/*
 * Opgaver til Prolog fra ugeseddel 13
 */

/*
 * 1996 juni opgave 3
 */

/* Opgave a) */

/* Én mulighed er følgende:
 * Hele opstillingen repræsenteres som en liste af længde 16. På den
 * første plads er positionen af hullet, på den anden pos. af brik 1,
 * osv.
 *
 * Er en brik på plads (x,y) (hvor (1,1) er øverste venstre hjørne)),
 * angives den position som en liste af længde 2 med indholdet [x,y]
 */

/* Opgave b) */

/* Med ovenstående def. fås: */

slutops([[4,4] | X]) :-
	lavbrikker(1, X).

lavbrikker(16, []) :- !.
lavbrikker(N, [[X,Y] | XS]) :-
	N < 16,
	X is (N-1) mod 4 + 1,
	Y is (N-1) // 4  + 1,
	N1 is N + 1,
	lavbrikker(N1, XS).

/* Opgave c) */

forskyd([GammelHul | GammelResten],
        [NytHul    | NyResten]) :-
	swap_element(GammelHul, GammelResten, NytHul, NyResten).

/*
 * swap_element(E, L, X, NL) tager på skift alle elementer, X,  i L
 * og erstater dette med E -- selve X og den nye liste NL returneres.
 */
swap_element(E, [X|XS],  X, [E|XS]) :-
	nabo(E,X).
swap_element(E, [X|XS], NX, [X|NL]) :-
	swap_element(E, XS, NX, NL).


nabo([X,Y1], [X, Y2]) :-
	Z is Y2 - Y1,
	abs(Z, 1).
nabo([X1,Y], [X2, Y]) :-
	Z is X2 - X1,
	abs(Z, 1).

abs(X, X) :-
	X >= 0, !.
abs(X, Y) :-
	Y is -X.
	
/* Opgave d) */

/* Vi kan her lave noget i retningen af flg. */
iter(S,S).
iter(T,S) :-
	asserta(besoegt(T)),
	forskyd(T,U),
	not(besoegt(U)),
	iter(U,S).

/*
 * For at undersøge, hvorvidt løsningen findes, skrives
 *
 * startops(X), andenops(Y), iter(X, Y).
 *
 * Såfremt vi også vi have at vide, *hvordan* man løser problemet
 * skal der tilføjes lidt information, hver gang forskyd og iter
 * bruges.
 *
 * -- Dette tager dog ubeskriveligt lang tid... (Men finder
 * stadigt en løsning i "endelig" tid!)
 */

not(X) :-
	call(X), !, fail.
not(_).

testops([[4,3],
	[1,1],[2,1],[3,1],[4,1],[1,2],
	[2,2],[3,2],[4,2],[1,3],[2,3],
	[3,3],[4,4],[1,4],[2,4],[3,4]]).