### tom's blog

By tom, history, 4 years ago,

Hello Codeforces community,

Here is a problem: http://www.spoj.com/problems/SOLVING/

How would you solve it? I don't want to skew your view, so I just leave the question without mentioning my (apparently too slow) solution.

Thanks, tom

• +9

 » 4 years ago, # |   +12
•  » » 4 years ago, # ^ |   0 Hm?
 » 4 years ago, # |   +5 Did you try using A-Star algorithm? I think search space is too big even for this algorithm but you can give it a try. Since optimal solution is not required you may use non-consistent heuristic to speed up the search.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes. My algorithm looks as follows: for every tile i from 1 to n*n-1 go to tile i "bring" tile i near (manhattan distance <= 2) to the place it should be at run A* to put it there My heuristic is simple sum of manhattan distances between current point and destination point for tiles <= i.It works well except two last rows. Sometimes it takes a lot of time to finish them.
 » 4 years ago, # | ← Rev. 2 →   0 My bad XDDDD, ignore, its stupid
•  » » 4 years ago, # ^ |   0 Look at the constraints, board can be up to 10x10