:- 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,_]|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,[[Old1,Ans]]):-member([Old1|Ans],Data),maplist(goal_check,Ans),!.
bfs(Data1,[[Old1,Now1]|Res1]):-setof(E1,search_all_move(Data1,E1),Data2),
				sort(Data2,Data3),
				maplist(swap,Data1,Data1Swap),
				sort(Data1Swap,Data1Swap2),
				deduplication(Data1Swap2,Data3,Data4),
				deduplication(Data1,Data4,Data5),
				bfs(Data5,Res1),
				[[Now1,_]|_]=Res1,
				member([Old1,Now1],Data1),
				!.
 
main:-
	process,
	halt.
 
process:-
	/*ビーカーを並べ替えていいと言う条件での ウォーターソートパズルを解くコード、答えの出力は手抜き状態、堀江 伸一*/
	msort([[1,2,2,2],[2,1,1,1],[],[]],Test),
	bfs([[[],Test]],Ans),
	maplist(writeln,Ans),
	true.
 
:- main.

Oi0gc2V0X3Byb2xvZ19mbGFnKHZlcmJvc2Usc2lsZW50KS4KOi0gcHJvbXB0KF8sICcnKS4KOi0gdXNlX21vZHVsZShsaWJyYXJ5KHJlYWR1dGlsKSkuCgpnb2FsX2NoZWNrKFtdKS4KZ29hbF9jaGVjayhbW118WHNdKTotZ29hbF9jaGVjayhYcykuCmdvYWxfY2hlY2soW1tYLFgsWCxYXXxYc10pOi1nb2FsX2NoZWNrKFhzKS4KCm1vdmVfY2hlY2soW1gsWCxYLFldLFtYLFgsWF0sW1ldKTotWFw9WS4KbW92ZV9jaGVjayhbWCxYLFksWTJdLFtYLFhdLFtZLFkyXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWSxZMixZM10sW1hdLFtZLFkyLFkzXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWCxYXSxbWCxYLFhdLFtdKS4KbW92ZV9jaGVjayhbWCxYLFldLFtYLFhdLFtZXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWSxZMl0sW1hdLFtZLFkyXSk6LVhcPVkuCm1vdmVfY2hlY2soW1gsWF0sW1gsWF0sW10pLgptb3ZlX2NoZWNrKFtYLFldLFtYXSxbWV0pOi1YXD1ZLgptb3ZlX2NoZWNrKFtYXSxbWF0sW10pLgoKbW92ZV9vayhfLFtdKS4KbW92ZV9vayhbWHxfXSxbWHxfXSkuCgptb3ZlKFhzMSxSZXMpOi1zZWxlY3QoRTEsWHMxLFhzMiksCgkJCQltb3ZlX2NoZWNrKEUxLEUxTW92ZSxFMU5leHQpLAoJCQkJc2VsZWN0KEUyLFhzMixYcyksCgkJCQltb3ZlX29rKEUxTW92ZSxFMiksCgkJCQlhcHBlbmQoRTFNb3ZlLEUyLEUyTmV4dCksCgkJCQlsZW5ndGgoRTJOZXh0LExlbiksCgkJCQlMZW48NSwKCQkJCW1zb3J0KFtFMU5leHQsRTJOZXh0fFhzXSxSZXMpLgoJCQkJCQpzZWFyY2hfYWxsX21vdmUoRGF0YTEsW05vdzEsTmV4dF0pOi1tZW1iZXIoW09sZDEsTm93MV0sRGF0YTEpLG1vdmUoTm93MSxOZXh0KS4KCnN3YXAoW09sZDEsTm93MV0sW05vdzEsT2xkMV0pLgoKZGVkdXBsaWNhdGlvbihbXSxEYXRhLERhdGEpOi0hLgpkZWR1cGxpY2F0aW9uKF8sW10sW10pOi0hLgpkZWR1cGxpY2F0aW9uKFtbTm93MSxPbGQxXXxEYXRhMV0sW1tfLE9sZDFdfERhdGEyXSxSZXMpOi0hLGRlZHVwbGljYXRpb24oRGF0YTEsRGF0YTIsUmVzKS4KZGVkdXBsaWNhdGlvbihbTm93MSxfXXxEYXRhMV0sW1tOb3cyLE5leHQyXXxEYXRhMl0sUmVzKTotTm93MTxOb3cyLCEsCgkJCQkJCQkJZGVkdXBsaWNhdGlvbihEYXRhMSxbW05vdzIsTmV4dDJdfERhdGEyXSxSZXMpLgpkZWR1cGxpY2F0aW9uKFtFMXxEYXRhMV0sW0UyfERhdGEyXSxbRTJ8UmVzXSk6LSEsCgkJCQkJCQkJZGVkdXBsaWNhdGlvbihbRTF8RGF0YTFdLERhdGEyLFJlcykuCmJmcyhEYXRhLFtbT2xkMSxBbnNdXSk6LW1lbWJlcihbT2xkMXxBbnNdLERhdGEpLG1hcGxpc3QoZ29hbF9jaGVjayxBbnMpLCEuCmJmcyhEYXRhMSxbW09sZDEsTm93MV18UmVzMV0pOi1zZXRvZihFMSxzZWFyY2hfYWxsX21vdmUoRGF0YTEsRTEpLERhdGEyKSwKCQkJCXNvcnQoRGF0YTIsRGF0YTMpLAoJCQkJbWFwbGlzdChzd2FwLERhdGExLERhdGExU3dhcCksCgkJCQlzb3J0KERhdGExU3dhcCxEYXRhMVN3YXAyKSwKCQkJCWRlZHVwbGljYXRpb24oRGF0YTFTd2FwMixEYXRhMyxEYXRhNCksCgkJCQlkZWR1cGxpY2F0aW9uKERhdGExLERhdGE0LERhdGE1KSwKCQkJCWJmcyhEYXRhNSxSZXMxKSwKCQkJCVtbTm93MSxfXXxfXT1SZXMxLAoJCQkJbWVtYmVyKFtPbGQxLE5vdzFdLERhdGExKSwKCQkJCSEuCgptYWluOi0KCXByb2Nlc3MsCgloYWx0LgoKcHJvY2VzczotCgkvKuODk+ODvOOCq+ODvOOCkuS4puOBueabv+OBiOOBpuOBhOOBhOOBqOiogOOBhuadoeS7tuOBp+OBriDjgqbjgqnjg7zjgr/jg7zjgr3jg7zjg4jjg5Hjgrrjg6vjgpLop6PjgY/jgrPjg7zjg4njgIHnrZTjgYjjga7lh7rlipvjga/miYvmipzjgY3nirbmhYvjgIHloIDmsZ8g5Ly45LiAKi8KCW1zb3J0KFtbMSwyLDIsMl0sWzIsMSwxLDFdLFtdLFtdXSxUZXN0KSwKCWJmcyhbW1tdLFRlc3RdXSxBbnMpLAoJbWFwbGlzdCh3cml0ZWxuLEFucyksCgl0cnVlLgoKOi0gbWFpbi4=