Some hints for solving this problem the way I was able to solve it, without greedy search

1. I used BFS search with heuristic (A* search). As a heuristic, I used the sum of the distances from the boxes to the nearest goals, taking into account that different boxes should be on different goals. It is better to distribute boxes among goals in some greedy way, so as not to spend a lot of time on this.
2. In the board states, DO NOT store the position of the player, store the places he can REACH. This will greatly reduce the number of states needed to be stored. You can store one board state in two 64-bit numbers as bit masks.
3. To find bad positions and stop further search on them, look for simple deadlocks (the box is in a corner and not on a target), dynamic deadlocks (the boxes block each other) and NOT COMPLEX corral deadlocks (the boxes are not on goals and block access to some board area, so they cannot be pushed out of there).
4. If you try to search for too complex corral deadlocks, the time spent on finding them will not be worth it. Try different settings of what difficulty of corral deadlocks to search for and when to stop the search. Store the found configurations of corral deadlocks (and the configurations in which no deadlock was found) in some sets so as not to determine them every time.
5. In addition to the forward search (pushing boxes from the starting positions to the goals), you can also use the backward search (pulling boxes from the goals to the starting positions) to reduce the depth of the search tree.
6. For the forward (backward) search, prevent situations when, for example, there are more (fewer) boxes near the wall than goals. This can greatly speed up the search for some boards.
7. To understand why your algorithm is working too long for a particular board, you can find and output long deadlock branches - a sequence of pushes/pulls in the search tree that starts from one of the board states that is in the found solution and that does not eventually lead to the solution. This way you can find bugs when the algorithm did not find one of the types of deadlocks and did not stop searching on them.

Good luck!

https://soucupb.github.io/Sokoban-Solver/

I will leave this here.
It is a visualizer to test your solution.
Maybe somebody will find this useful.

My max value is 13:
########
#@ $.$.#
#  $.$.#
#$ $.$.#
#. $.$.#
#$ $.$.#
#.   $.#
########

Has anybody found more?

Can somebody give me some hard test - my program works fine on all tests, which I can think out. BTW, here is some of them:

########
#.OOOOO#
#$O$O$O#
#OO$O$O#
#@O$O$O#
###***O#
#......#
########

########
#.O$OO.#
#O$..$O#
#$$..$O#
#O$..$$#
#@$O.$O#
#..$OO.#
########

########
#.O$OO.#
#O$..$O#
#$$..$O#
#O$..$$#
#@$..$O#
#.O$OO.#
########

########
#......#
###***O#
#@O$O$O#
#OO$O$O#
#$O$O$O#
#.OOOOO#
########

########
#.....O#
#$$$$$O#
#OO...O#
#$$$$$O#
#O.OO$.#
#.O$.$+#
########

########
#......#
###***O#
#@O$O$O#
#OO$O$O#
#OO$O$O#
#OOOOOO#
########

########
#.$.$OO#
#@OOOOO#
#O$$$$$#
#O.....#
#$$$$$$#
#......#
########

########
#.OOO.O#
#@$O##O#
#OOO*OO#
#.$O$O$#
#$$$$..#
#...OOO#
########

########
#OOOO.O#
#@OO##O#
#OOO*OO#
#.$O$OO#
#$$$$.O#
#...OOO#
########

#######
#@$OO.#
#$O$OO#
#.O.OO#
#######

P.S. space I've changed to O.

Edited by author 03.11.2009 20:42

Hi guys, i've tried to solve this problem with A*. I came with pull distance as heuristic and calculate the distance table with Floyd's algorithm. I also have put deadlock detector (for Simple and Frozen) on my code. Is there something i miss? Or do you have any other suggestion?

I am very happy if i can discuss with you guys. Thanks before for your help :)

I think the answer is probablye Yes...

Many thank to Oracle[Lviv NU]. His test data helped me a lot. But now my program solves all that tests as well as any test that I can imagine.
Can anyone give test cases that he consider to be hard.

Thanks!

visual C++ 2017 can't  use gets() too egg hurt

I think this is a no solution test

I output empty and pass this test...

if consider the position of player there are about 7.5*10^8(upper_bound),state, we can come up some idea
to compact the states,and use a huge array instead of hash_table to prevent the duplication of states this may far speed up your program

Edited by author 15.11.2016 13:02

Edited by author 15.11.2016 13:02

3 days overall. I'm your fan forever.

Edited by author 03.05.2016 14:58

The problem is rejudged, one author have lost AC. Thanks to Erop [USU]

I have a good test. Can you add it?

Hello, i am a newfag at this judge system, and i have some questions:

The output information must be minimalize, or only no longer than 10000 symbols?  Different and true solutions are all accepted?

What biggest number 'n' could be?

Edited by author 19.03.2010 03:26

i got ac, but my program can't pass some tests.. can you add these tests?

Edited by author 19.01.2008 01:06

char em[10][20];
int n = 0, m = 0;
...
while (gets(em[n++]) && em[n-1][0]);
--n;
m = (int) strlen(em[0]);
...

this code doesn't pass test 3 and gets WA, but if i insert this line
if (m != strlen(em[1])) while(true);
it gets Time Limit Exceeded !!! check it

Edited by author 16.01.2009 23:18

I always TLE in 9# and 10#.
How shuold I deal with it?

what's the test#7?
I tried many tests myself.
All is OK except time limit exceed.
Could you give me any tests?

Why in test 3 input is not table n on m?