%% soukoban solver for erlang (c)Nakatani Shuyo / CybozuLabs,inc. %%%% -module(solver3). -export([start/2, ticker/2, solver/2]). -export([test/0, test2/0, test3/0]). -author('nakatani@labs.cybozu.co.jp'). -define(PLAYER, 64). % @: player, only one, inside of walls -define(WALL, 35). % #: wall, closed -define(SPACE, 32). % space -define(PARCEL, 43). % +: parcel, as many goals -define(GOAL, 46). % .: goal without parcel -define(PARCELonG, 42). % *: goal with parcel already %-define(debug, debug). -ifdef(debug). -define(INFOLOG(X,Y), error_logger:info_msg(X, Y)). -else. -define(INFOLOG(X,Y), void). -endif. % solver %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% solver(Server, {Map, X, Y, History, Steps, Goals} ) -> move(Map, queue_new({X, Y, 0}), {History, Steps, Goals, Server}). move(Map, Posilist, Pushargs) -> {_Posilist, Result} = queue_shift(Posilist), case Result of empty -> ok; {value, Posi} -> __Posilist = movestep(Map, Posi, [{0,-1}, {1,0}, {0,1}, {-1,0}], _Posilist, Pushargs), move(Map, __Posilist, Pushargs) end. movestep(_,_,[], Posilist, _) -> Posilist; movestep(Map, {X, Y, Steps}, [Move|Moves], Posilist, Pushargs) -> X1 = X + element(1, Move), Y1 = Y + element(2, Move), PASSED = queue_check(Posilist, {X1, Y1}), if PASSED -> movestep(Map, {X, Y, Steps}, Moves, Posilist, Pushargs); true -> C1 = cell(Map, X1, Y1), {Check1, _, _} = check1(C1), case Check1 of movable -> Posi = {X1, Y1, Steps+1}, movestep(Map, {X, Y, Steps}, Moves, queue_append(Posilist, Posi), Pushargs); parcel -> {Check2, _, _} = move3(Map, X1, Y1, Move), case Check2 of pushable -> Push = {X1, Y1, Move, Steps+1}, push(Push, Map, Pushargs), movestep(Map, {X, Y, Steps}, Moves, Posilist, Pushargs); cannot -> movestep(Map, {X, Y, Steps}, Moves, Posilist, Pushargs) end; deadend -> movestep(Map, {X, Y, Steps}, Moves, Posilist, Pushargs) end end. push({X, Y, Move, _Steps}, Map, {History, Steps, Goals, Server}) -> {_, D1, G1} = check1(cell(Map, X, Y)), {_, D2, G2} = move2(Map, X, Y, Move), Map2 = setcell(Map, X, Y, D1), Map3 = setcell(Map2, X+element(1, Move), Y+element(2, Move), D2), _Goals = Goals+G1+G2, Server ! {branch, Map3, X, Y, [{X, Y, Move}|History], Steps+_Steps, _Goals}. % check movable %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% check1(?SPACE) -> {movable, 0, 0}; % space check1(?GOAL) -> {movable, 0, 0}; % goal check1(?PARCEL) -> {parcel, ?SPACE, 0}; % parcel -> space check1(?PARCELonG) -> {parcel, ?GOAL, -1}; % parcel on goal -> goal check1(_) -> {deadend, 0, 0}. % wall or outside move2(Map, X1, Y1, Move) -> X2 = X1 + element(1, Move), Y2 = Y1 + element(2, Move), C2 = cell(Map, X2, Y2), check2(C2). move3(Map, X1, Y1, Move) -> move3(move2(Map, X1, Y1, Move), Map, X1 + element(1, Move), Y1 + element(2, Move), Move). move3({pushable, ?PARCEL, _}, Map, X1, Y1, Move) -> C1 = check3(Map,X1,Y1,Move,forward), CR1 = check3(Map,X1,Y1,Move,right), CR2 = check3(Map,X1,Y1,Move,rightforward), CL1 = check3(Map,X1,Y1,Move,left), CL2 = check3(Map,X1,Y1,Move,leftforward), case {C1,CR1,CR2,CL1,CL2} of {cannot,cannot,cannot,_,_} -> {cannot,0,0}; {cannot,_,_,cannot,cannot} -> {cannot,0,0}; _ -> {pushable,0,0} end; move3(Check, _, _, _, _) -> Check. check3(Map,X,Y,Move,forward) -> X2 = X + element(1, Move), Y2 = Y + element(2, Move), element(1, check2(cell(Map, X2, Y2))); check3(Map,X,Y,Move,right) -> X2 = X - element(2, Move), Y2 = Y + element(1, Move), element(1, check2(cell(Map, X2, Y2))); check3(Map,X,Y,Move,rightforward) -> X2 = X + element(1, Move) - element(2, Move), Y2 = Y + element(2, Move) + element(1, Move), element(1, check2(cell(Map, X2, Y2))); check3(Map,X,Y,Move,left) -> X2 = X + element(2, Move), Y2 = Y - element(1, Move), element(1, check2(cell(Map, X2, Y2))); check3(Map,X,Y,Move,leftforward) -> X2 = X + element(1, Move) + element(2, Move), Y2 = Y + element(2, Move) - element(1, Move), element(1, check2(cell(Map, X2, Y2))). check2(?SPACE) -> {pushable, ?PARCEL, 0}; % space -> check2(?GOAL) -> {pushable, ?PARCELonG, 1}; % goal -> parcel on goal check2(_) -> {cannot, 0, 0}. % wall or parcel or outside % map %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% check_map(Map) -> put(wall, 0), put(player, 0), put(parcel, 0), put(goal, 0), put(parcelong, 0), check_map_line(Map, 1), Player=get(player), Parcel=get(parcel), Goal=get(goal), if Parcel /= Goal -> throw({ng, "not equal number of goals as number of parcels"}); Player /= 1 -> throw({ng, "not only one player"}); true -> ok end, X=get(player_x), Y=get(player_y), PonG=get(parcelong), {Map, X, Y, Parcel+PonG, PonG}. check_map_line([], _) -> ok; check_map_line([LINE|REST], Y)-> check_map_char(LINE, 1, Y), check_map_line(REST, Y+1). check_map_char([], _, _) -> ok; check_map_char([CHAR|REST], X, Y) -> case CHAR of ?WALL -> put(wall, get(wall) + 1); ?PLAYER -> put(player, get(player) + 1), put(player_x, X), put(player_y, Y); ?GOAL -> put(goal, get(goal) + 1); ?PARCEL -> put(parcel, get(parcel) + 1); ?PARCELonG -> put(parcelong, get(parcelong) + 1); ?SPACE -> ok end, check_map_char(REST, X+1, Y). map2tuple(Map) -> list_to_tuple([list_to_tuple(X) || X <- Map]). cell(Map, X, Y) -> Xsize = size(element(1, Map)), if X<1 -> 0; Y<1 -> 0; Y>size(Map) -> 0; X>Xsize -> 0; true -> element(X, element(Y, Map)) end. setcell(Map, X, Y, C) -> L=element(Y, Map), setelement(Y, Map, setelement(X, L, C)). % manager %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% loop(Parcels, Maxsteps) -> receive {branch, _, _, _, _, Steps, _} when Steps>Maxsteps -> loop(Parcels, Maxsteps); {branch, _, _, _, History, Steps, Goals} when Parcels == Goals -> Solution = [{A,B,[movechar(C)]} || {A,B,C}<-History], io:format("solution: ~p steps (~p)~n", [Steps, lists:reverse(Solution)]), loop(Parcels, Steps-1); {branch, Map, X, Y, History, Steps, Goals} -> T = get(state), State = {Map, X, Y}, case ets:lookup(T, State) of [{_, PreSteps}] when Steps >= PreSteps -> pass; _ -> ets:insert(T, {State, Steps}), spawn(?MODULE, solver, [self(), {Map, X, Y, History, Steps, Goals}]), put(count, get(count)+1) end, loop(Parcels, Maxsteps); ticker -> io:format("branches: ~p, states: ~p, processes: ~p, mem: ~pKB~n", [get(count), ets:info(get(state), size), erlang:system_info(process_count), erlang:memory(total) div 1024]), loop(Parcels, Maxsteps) after 1000 -> io:format("branches: ~p, states: ~p, mem: ~pKB~n", [get(count), ets:info(get(state), size), erlang:memory(total) div 1024]), %T = get(state),io:format("~p~n", [ets:tab2list(T)]), finish end. movechar({ 0,-1}) -> 94; % '^' movechar({ 0, 1}) -> 118; % 'v' movechar({-1, 0}) -> 60; %'<' movechar({ 1, 0}) -> 62. %'>' % misc. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ticker(Server, T) -> receive _ -> finish after T-> Server ! ticker, ticker(Server, T) end. queue_new(Posi)-> queue_append({queue:new(), []}, Posi). queue_check({_, T}, {X, Y})-> lists:any(fun({XX,YY}) -> XX==X andalso YY==Y end, T). queue_append({Q, T}, {X, Y, Steps})-> Q2 = queue:in({X, Y, Steps}, Q), {Q2, [{X, Y}|T]}. queue_shift({Q, T})-> {Result, Q2} = queue:out(Q), {{Q2, T}, Result}. % initialize & start %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% start(_Map, Maxsteps) -> {Map, X, Y, Parcels, Goals} = check_map(_Map), Map2 = map2tuple(Map), self() ! {branch, setcell(Map2, X, Y, ?SPACE), X, Y, [], 0, Goals}, put(count, 0), put(state, ets:new(solverstate, [set])), T = spawn(?MODULE, ticker, [self(), 2000]), T ! loop(Parcels, Maxsteps). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % ####### % #. + @# % ####### test() -> start(["#######","#. + @#","#######"], 10). % ###### % #@ .# % # +++# % # . .# % ######" test2() -> start(["######","#@ .#","# +++#","# . .#","######"], 30). % ######### % # # % # ##+## # % # @ + # % ##+...# # % ## # # % #### ### % ######### test3() -> start(["#########","# #","# ##+## #","# @ + #","##+...# #","## # #","#### ###","#########"], 80).