:- set_prolog_flag(verbose,silent).
:- prompt(_, '').
:- use_module(library(readutil)).
 
goal_check([]).
goal_check([[]|Xs]):-goal_check(Xs).
goal_check([[X,X,X,X]|Xs]):-goal_check(Xs).
 
move_check([X,X,X,Y],[X,X,X],[Y]):-X\=Y.
move_check([X,X,Y,Y2],[X,X],[Y,Y2]):-X\=Y.
move_check([X,Y,Y2,Y3],[X],[Y,Y2,Y3]):-X\=Y.
move_check([X,X,X],[X,X,X],[]).
move_check([X,X,Y],[X,X],[Y]):-X\=Y.
move_check([X,Y,Y2],[X],[Y,Y2]):-X\=Y.
move_check([X,X],[X,X],[]).
move_check([X,Y],[X],[Y]):-X\=Y.
move_check([X],[X],[]).
 
move_ok(_,[]).
move_ok([X|_],[X|_]).
 
move(Xs1,Res):-select(E1,Xs1,Xs2),
				move_check(E1,E1Move,E1Next),
				select(E2,Xs2,Xs),
				move_ok(E1Move,E2),
				append(E1Move,E2,E2Next),
				length(E2Next,Len),
				Len<5,
				msort([E1Next,E2Next|Xs],Res).
 
search_all_move(Data1,[Now1,Next]):-member([Old1,Now1],Data1),move(Now1,Next).
 
swap([Old1,Now1],[Now1,Old1]).
 
deduplication([],Data,Data):-!.
deduplication(_,[],[]):-!.
deduplication([[Now1,Old1]|Data1],[[_,Old1]|Data2],Res):-!,deduplication(Data1,Data2,Res).
deduplication([[Now1,Old1]|Data1],[[_,Now1]|Data2],Res):-!,deduplication(Data1,Data2,Res).
deduplication([Now1,_]|Data1],[[Now2,Next2]|Data2],Res):-Now1<Now2,!,
								deduplication(Data1,[[Now2,Next2]|Data2],Res).
deduplication([E1|Data1],[E2|Data2],[E2|Res]):-!,
								deduplication([E1|Data1],Data2,Res).
bfs(Data,Ans):-member([_|Ans],Data),maplist(goal_check,Ans),!.
bfs(Data1,Res):-setof(E1,search_all_move(Data1,E1),Data2),
				maplist(swap,Data1,Data1Swap),
				sort(Data1Swap,Data1Swap2),
				deduplication(Data1Swap2,Data2,Data3),
				sort(Data3,Data4),
				maplist(writeln,Data4),nl,
				bfs(Data4,Res1).
 
main:-
	process,
	halt.
 
process:-
	/* ウォーターソートパズルを解くコード、答えの出力は手抜き予定、書きかけ、堀江 */
	msort([[1,2,2,2],[2,1,1,1],[],[]],Test),
	bfs([[[],Test]],_),
	true.
 
:- main.

Oi0gc2V0X3Byb2xvZ19mbGFnKHZlcmJvc2Usc2lsZW50KS4KOi0gcHJvbXB0KF8sICcnKS4KOi0gdXNlX21vZHVsZShsaWJyYXJ5KHJlYWR1dGlsKSkuCgpnb2FsX2NoZWNrKFtdKS4KZ29hbF9jaGVjayhbW118WHNdKTotZ29hbF9jaGVjayhYcykuCmdvYWxfY2hlY2soW1tYLFgsWCxYXXxYc10pOi1nb2FsX2NoZWNrKFhzKS4KCm1vdmVfY2hlY2soW1gsWCxYLFldLFtYLFgsWF0sW1ldKTotWFw9WS4KbW92ZV9jaGVjayhbWCxYLFksWTJdLFtYLFhdLFtZLFkyXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWSxZMixZM10sW1hdLFtZLFkyLFkzXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWCxYXSxbWCxYLFhdLFtdKS4KbW92ZV9jaGVjayhbWCxYLFldLFtYLFhdLFtZXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWSxZMl0sW1hdLFtZLFkyXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWF0sW1gsWF0sW10pLgptb3ZlX2NoZWNrKFtYLFldLFtYXSxbWV0pOi1YXD1ZLgptb3ZlX2NoZWNrKFtYXSxbWF0sW10pLgoKbW92ZV9vayhfLFtdKS4KbW92ZV9vayhbWHxfXSxbWHxfXSkuCgptb3ZlKFhzMSxSZXMpOi1zZWxlY3QoRTEsWHMxLFhzMiksCgkJCQltb3ZlX2NoZWNrKEUxLEUxTW92ZSxFMU5leHQpLAoJCQkJc2VsZWN0KEUyLFhzMixYcyksCgkJCQltb3ZlX29rKEUxTW92ZSxFMiksCgkJCQlhcHBlbmQoRTFNb3ZlLEUyLEUyTmV4dCksCgkJCQlsZW5ndGgoRTJOZXh0LExlbiksCgkJCQlMZW48NSwKCQkJCW1zb3J0KFtFMU5leHQsRTJOZXh0fFhzXSxSZXMpLgoJCQkJCQpzZWFyY2hfYWxsX21vdmUoRGF0YTEsW05vdzEsTmV4dF0pOi1tZW1iZXIoW09sZDEsTm93MV0sRGF0YTEpLG1vdmUoTm93MSxOZXh0KS4KCnN3YXAoW09sZDEsTm93MV0sW05vdzEsT2xkMV0pLgoKZGVkdXBsaWNhdGlvbihbXSxEYXRhLERhdGEpOi0hLgpkZWR1cGxpY2F0aW9uKF8sW10sW10pOi0hLgpkZWR1cGxpY2F0aW9uKFtbTm93MSxPbGQxXXxEYXRhMV0sW1tfLE9sZDFdfERhdGEyXSxSZXMpOi0hLGRlZHVwbGljYXRpb24oRGF0YTEsRGF0YTIsUmVzKS4KZGVkdXBsaWNhdGlvbihbW05vdzEsT2xkMV18RGF0YTFdLFtbXyxOb3cxXXxEYXRhMl0sUmVzKTotISxkZWR1cGxpY2F0aW9uKERhdGExLERhdGEyLFJlcykuCmRlZHVwbGljYXRpb24oW05vdzEsX118RGF0YTFdLFtbTm93MixOZXh0Ml18RGF0YTJdLFJlcyk6LU5vdzE8Tm93MiwhLAoJCQkJCQkJCWRlZHVwbGljYXRpb24oRGF0YTEsW1tOb3cyLE5leHQyXXxEYXRhMl0sUmVzKS4KZGVkdXBsaWNhdGlvbihbRTF8RGF0YTFdLFtFMnxEYXRhMl0sW0UyfFJlc10pOi0hLAoJCQkJCQkJCWRlZHVwbGljYXRpb24oW0UxfERhdGExXSxEYXRhMixSZXMpLgpiZnMoRGF0YSxBbnMpOi1tZW1iZXIoW198QW5zXSxEYXRhKSxtYXBsaXN0KGdvYWxfY2hlY2ssQW5zKSwhLgpiZnMoRGF0YTEsUmVzKTotc2V0b2YoRTEsc2VhcmNoX2FsbF9tb3ZlKERhdGExLEUxKSxEYXRhMiksCgkJCQltYXBsaXN0KHN3YXAsRGF0YTEsRGF0YTFTd2FwKSwKCQkJCXNvcnQoRGF0YTFTd2FwLERhdGExU3dhcDIpLAoJCQkJZGVkdXBsaWNhdGlvbihEYXRhMVN3YXAyLERhdGEyLERhdGEzKSwKCQkJCXNvcnQoRGF0YTMsRGF0YTQpLAoJCQkJbWFwbGlzdCh3cml0ZWxuLERhdGE0KSxubCwKCQkJCWJmcyhEYXRhNCxSZXMxKS4KCm1haW46LQoJcHJvY2VzcywKCWhhbHQuCgpwcm9jZXNzOi0KCS8qIOOCpuOCqeODvOOCv+ODvOOCveODvOODiOODkeOCuuODq+OCkuino+OBj+OCs+ODvOODieOAgeetlOOBiOOBruWHuuWKm+OBr+aJi+aKnOOBjeS6iOWumuOAgeabuOOBjeOBi+OBkeOAgeWggOaxnyAqLwoJbXNvcnQoW1sxLDIsMiwyXSxbMiwxLDEsMV0sW10sW11dLFRlc3QpLAoJYmZzKFtbW10sVGVzdF1dLF8pLAoJdHJ1ZS4KCjotIG1haW4u